文章目录
二叉搜索树（ Binary Search Tree，BST ）是一种特殊的二叉树，它可以是空树，也可以是满足以下性质的一颗二叉树：
因此，二叉搜索树的中序遍历结果是一个有序序列。这个特性使得二叉搜索树在搜索、插入和删除操作时具有高效性能。
📝二叉搜索树的结构示意图
⭕ 对如下二叉搜索树进行操作
🔎假设要查询key值是否存在于二叉树中
1️⃣若树为空，则直接新增节点，作为该树的根节点
2️⃣若树不为空，则按二叉搜索树查询规则找到插入位置，再建立与父节点的链接关系。
二叉搜索树的删除某个节点后，要想继续保持二叉搜索树的特性，需要进行一些调整。这里分三种情况。
假设将要删除node节点
1️⃣ 若node没有子树，即node为叶子节点，那么直接删除即可。
2️⃣ 若node左右子树有一边为空一边非空，则需“托孤”，即把非空一边的子树托付给node父节点。
3️⃣ 若node左右子树都存在，则需在左子树中找到最大节点（或在右子树中找到最小节点）来替代node，然后在左子树（或右子树）中删除node。
观察二叉搜索树的中序遍历序列，可见进行上述操作后，中序遍历序列依然有序，二叉搜索树保持其特性。
💡替换node后，在左子树（或右子树）中删除node，这样做还有一个好处：
因为node是与左子树中最大节点（或右子树中最小节点）替换后，所以替换后的node一定没有右子树（或左子树），因此在这种情况下删除node，必然是删除节点的1️⃣或2️⃣情况，避免了重复3️⃣情况删除而进入死循环。
#include <iostream>
#include <algorithm>
using namespace std;
// 二叉搜索树的节点
template <class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Self;
Self* _pleft;
Self* _pright;
K _key;
BSTreeNode(const K& key)
:_key(key)
,_pleft(nullptr)
,_pright(nullptr)
{}
};
// 二叉搜索树
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
typedef BSTreeNode<K>* pNode;
public:
// constructor
BSTree()
:_root(nullptr)
{}
// destructor
~BSTree()
{
_destroy(_root);
}
// 中序遍历
void Inorder()
{
_inorder(_root);
cout << endl;
}
// 插入
bool Insert(const K& key)
{
// 空树
if(_root == nullptr)
{
_root = new Node(key);
return true;
}
// 不为空树，要先找到插入位置
else
{
pNode cur = _root;
pNode parent = nullptr;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_pright;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_pleft;
}
else
{
return false;
}
}
cur = new Node(key);
if (cur->_key > parent->_key)
parent->_pright = cur;
else
parent->_pleft = cur;
return true;
}
}
// 删除
void Erase(const K& key)
{
_erase(_root, key);
}
private:
pNode _root;
void _inorder(pNode root)
{
if (root == nullptr)
return;
_inorder(root->_pleft);
cout << root->_key << " ";
_inorder(root->_pright);
}
void _destroy(pNode root)
{
if (root == nullptr)
return;
_destroy(root->_pleft);
_destroy(root->_pright);
delete root;
}
bool _erase(pNode& root, const K& key)
{
// 先找到key值的节点
pNode cur = root;
pNode parent = nullptr;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_pright;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_pleft;
}
else // 相等，找到了
break;
}
if (cur == nullptr) // 查无key值节点
return false;
// 1. cur左右至少有一个空（1️⃣、2️⃣情况）
if (cur->_pleft == nullptr || cur->_pright == nullptr)
{
pNode child = cur->_pleft;
if (child == nullptr)
child = cur->_pright;
// cur为根
if (cur == root)
{
root = child;
}
// cur不为根
else
{
if (cur == parent->_pleft)
{
parent->_pleft = child;
}
else
{
parent->_pright = child;
}
}
delete cur;
cur = nullptr;
}
// 2. cur左右都非空（3️⃣情况）
else
{
//(1)找到右边最小(也可以是左边最大，通常小的离根较近，我们选用右边最小)的节点代替cur
pNode minRight = cur->_pright;
while (minRight->_pleft)
{
minRight = minRight->_pleft;
}
swap(cur->_key, minRight->_key);
//(2)转换为在cur的右子树删除minRight节点
_erase(cur->_pright, minRight->_key); // 此时一定是1️⃣或2️⃣情况
}
return true;
}
};
💡 _erase函数root参数设为引用的妙处在cur为根时，体现为以下两种情况相同处理
1. _erase(_root, key);
2. _erase(cur->_pright(或cur->_pleft), minRight->_key);
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树，在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文
<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
💬KV模型的代码实现:
// KV型
template <class K, class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Self;
Self* _pleft;
Self* _pright;
K _key;
V _val;
BSTreeNode(const K& key, const V& val)
: _key(key)
, _val(val)
, _pleft(nullptr)
, _pright(nullptr)
{}
};
template <class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
typedef BSTreeNode<K, V>* pNode;
public:
//constructor
BSTree()
:_root(nullptr)
{}
//destructor
~BSTree()
{
_destroy(_root);
}
void Inorder()
{
_inorder(_root);
cout << endl;
}
bool Insert(const K& key,const V& val)
{
// 空树
if (_root == nullptr)
{
_root = new Node(key, val);
return true;
}
// 不为空树，要先找到插入位置
else
{
pNode cur = _root;
pNode parent = nullptr;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_pright;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_pleft;
}
else
{
return false;
}
}
cur = new Node(key, val);
if (cur->_key > parent->_key)
parent->_pright = cur;
else
parent->_pleft = cur;
return true;
}
}
void Erase(const K& key)
{
_erase(_root, key);
}
pNode Find(const K& key)
{
pNode cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_pright;
}
else if (key < cur->_key)
{
cur = cur->_pleft;
}
else
{
return cur;
}
}
return nullptr;
}
private:
pNode _root;
void _inorder(pNode root)
{
if (root == nullptr)
return;
_inorder(root->_pleft);
cout << root->_key << ":" << root->_val << endl;
_inorder(root->_pright);
}
void _destroy(pNode root)
{
if (root == nullptr)
return;
_destroy(root->_pleft);
_destroy(root->_pright);
delete root;
}
bool _erase(pNode& root, const K& key)
{
// 先找到key值的节点
pNode cur = root;
pNode parent = nullptr;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_pright;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_pleft;
}
else // 相等，找到了
break;
}
if (cur == nullptr) // 查无key值节点
return false;
// 1. cur左右至少有一个空
if (cur->_pleft == nullptr || cur->_pright == nullptr)
{
pNode child = cur->_pleft;
if (child == nullptr)
child = cur->_pright;
// cur为根
if (cur == root)
{
root = child;
}
// cur不为根
else
{
// cur左右都为空
if (child == nullptr)
{
if (parent->_pleft->_key == cur->_key)
{
parent->_pleft = nullptr;
}
else
{
parent->_pright = nullptr;
}
}
// cur左右只有一个为空，不为空的为child
else
{
if (child->_key < parent->_key)
{
parent->_pleft = child;
}
else
{
parent->_pright = child;
}
}
if (cur == parent->_pleft)
{
parent->_pleft = child;
}
else
{
parent->_pright = child;
}
}
delete cur;
cur = nullptr;
}
//2. cur左右都非空
else
{
//找到右边最小的节点代替cur
pNode minRight = cur->_pright;
while (minRight->_pleft)
{
minRight = minRight->_pleft;
}
swap(cur->_key, minRight->_key);
//转换为在cur的右子树删除minRight节点
_erase(cur->_pright, minRight->_key);
}
return true;
}
};
💭 二叉搜索树的插入、删除等操作，时间大部分都花费在查找节点上了。因此分析二叉搜索树的性能，主要看查找的性能。
假设二叉树有N个节点
如图是最优情况下的查找，该二叉搜索树接近完全二叉树，此时查找节点的时间复杂度是O(logN)
❗但也有上图所示的极端情况，有序插入节点后，二叉搜索树退化为单支，这种情况是最差情况，查找节点的时间复杂度为O(N)
💭 二叉搜索树退化为接近单支树时，其效率和性能就失去了。为了解决这个问题，使二叉搜索树始终保持最优情况，我们可以将二叉搜索树改造为AVL树和红黑树。下文分析AVL树。
💭二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
能满足这种特性的树称为AVL树
⭕一颗AVL树可以是一棵空树，也可以是有以下性质的一棵二叉搜索树：
AVL树是一棵高度平衡的树。一棵n个节点的AVL树的高度为O(logn)，查找的时间复杂度为O(logn)。
⭕定义
// AVL树的节点
template <class T>
struct AVLTreeNode
{
AVLTreeNode(const T& val)
:_val(val)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
AVLTreeNode* _left; // 左指针
AVLTreeNode* _right; // 右指针
AVLTreeNode* _parent; // 双亲指针
T _val;
int _bf;// 平衡因子
};
// AVL树
template <class T>
class AVLTree
{
typedef AVLTreeNode<T> node;
typedef AVLTreeNode<T>* ptr;
public:
AVLTree()
:_root(nullptr)
{}
bool insert(const T& val);
private:
ptr _root;
};
💭AVL树的原理主要体现在插入时要通过对节点的调节，以保证每个节点的左右子树高度差绝对值不超过1（即平衡因子不超过1）。插入后，分为以下三种情况。
默认平衡因子 = 右子树高度 - 左子树高度
那么这里的旋转到底是怎么一回事？见后文详细分析。
📃 先搭建AVL树insert插入函数定义的大致框架
bool insert(const T& val)
{
// 先按二叉搜索树规则，找到插入位置
ptr cur = _root;
ptr parent = nullptr;
while (cur)
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
// 相同元素不能插入
return false;
}
}
// 创建新节点并插入
cur = new node(val);
// 若根为空，直接把cur作根
if (_root == nullptr)
{
_root = cur;
return true;
}
else
{
if (cur->_val < parent->_val)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
}
// 更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
(parent->_bf)--;
}
else
{
(parent->_bf)++;
}
// 1.parent的_bf更新后为0
if (parent->_bf == 0)
{
// 插入成功
break;
}
// 2.parent的_bf更新后为1或-1，此时需要继续向上更新平衡因子
else if (parent->_bf == 1 || parent->_bf == -1)
{
//持续往上更新
cur = parent;
parent = parent->_parent;
}
// 3.parent的_bf更新后为2或-2，此时需要旋转，旋转后以parent为根的子树为平衡二叉树，不需要在继续向上更新平衡因子
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转...
break;
}
}
return true;
}
🔎如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。这种调整称之为旋转。根据节点插入位置的不同，AVL树的旋转分为四种：
为什么能这样旋转？
💬 代码实现
// 左左--右单旋
void RotateR(ptr pParent)
{
ptr subL = pParent->_left;
ptr subLR = subL->_right;
ptr ppParent = pParent->_parent;
//建立新的链接关系
//1.pParent(父)和subLR(子)
pParent->_left = subLR;
if (subLR)
subLR->_parent = pParent;
//2.subL(父)和pParent(子)
subL->_right = pParent;
pParent->_parent = subL;
//3.ppParent(父)和subL(子)
if (pParent == _root)
{
_root = subL;
}
else
{
if (ppParent->_left == pParent)
{
ppParent->_left = subL;
}
else
{
ppParent->_right = subL;
}
}
subL->_parent = ppParent;
//4.更新平衡因子
subL->_bf = pParent->_bf = 0;
}
💬 代码实现
// 右右--左单旋
void RotateL(ptr pParent)
{
ptr subR = pParent->_right;
ptr subRL = subR->_left;
ptr ppParent = pParent->_parent;
pParent->_right = subRL;
if (subRL)
subRL->_parent = pParent;
subR->_left = pParent;
pParent->_parent = subR;
if (pParent == _root)
{
_root = subR;
}
else
{
// 是否可以用函数参数引用 ptr& pParent 优化？
//if (subR->_val < ppParent->_val)
if (ppParent->_left == pParent)
{
ppParent->_left = subR;
}
else
{
ppParent->_right = subR;
}
}
subR->_parent = ppParent;
subR->_bf = pParent->_bf = 0;
}
🔎我们可以复用RotateL（左单旋）和RotateR（右单旋）来实现右左双旋，但需要注意的是，这两个函数会把平衡因子直接更新为0，但是观察右左双旋的过程图，发现结果所更新节点的平衡因子不全为0。因此，右左双旋要自己更新平衡因子，不能依赖于RotateL和RotateR。
当在b子树插入新节点时，旋转后的结果
特殊情况，当h==0时，30的右子树为空，60就是新插入节点。最终平衡因子全为0。
💬 代码实现
🔎通过上两张图可以发现，当在c子树插入时，最终subL指向节点的平衡因子为-1，其他两个为0；当在b子树插入时，最终pParent指向节点的平衡因子为1，其他两个为0。因此，判断在哪颗树插入时决定最终如何更新平衡因子的关键，而插入后且调整前的subLR的平衡因子就可以判断。插入后且调整前，若subLR的平衡因子为1，则是在c子树插入；若subLR的平衡因子为-1，则是在b子树插入。还有h==0的特殊情况，此时subLR的平衡因子为0，作特殊处理。
void RotateLR(ptr pParent)
{
ptr subL = pParent->_left;
ptr subLR = subL->_right;
int bf = subLR->_bf; // 保存插入后调整前subLR的平衡因子
// 两次旋转
RotateL(subL);
RotateR(pParent);
// 更新平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
pParent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
pParent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
pParent->_bf = 0;
}
else
{
assert(false);
}
}
💬代码实现
void RotateRL(ptr pParent)
{
ptr subR = pParent->_right;
ptr subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(pParent);
if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
pParent->_bf = -1;
}
else if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
pParent->_bf = 0;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
pParent->_bf = 0;
}
else
{
assert(false);
}
}
// AVL树的节点
template <class T>
struct AVLTreeNode
{
AVLTreeNode(const T& val)
:_val(val)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
T _val;
int _bf;// 平衡因子
};
// AVL树
template <class T>
class AVLTree
{
typedef AVLTreeNode<T> node;
typedef AVLTreeNode<T>* ptr;
public:
// 构造函数
AVLTree()
:_root(nullptr)
{}
// 析构函数
~AVLTree()
{
destroy(_root);
}
// 中序遍历
void InOrder()
{
_inorder(_root);
}
// 插入新节点
bool insert(const T& val)
{
// 先按二叉搜索树规则，找到插入位置
ptr cur = _root;
ptr parent = nullptr;
while (cur)
{
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)
{
parent = cur;
cur = cur->_right;
}
else
{
// 相同元素不能插入
return false;
}
}
// 创建新节点并插入
cur = new node(val);
if (_root == nullptr)
{
_root = cur;
return true;
}
else
{
if (cur->_val < parent->_val)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
}
// 更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
(parent->_bf)--;
}
else
{
(parent->_bf)++;
}
// 1.parent的_bf更新后为0
if (parent->_bf == 0)
{
// 插入成功
break;
}
// 2.parent的_bf更新后为1或-1，此时需要继续向上更新平衡因子
else if (parent->_bf == 1 || parent->_bf == -1)
{
//持续往上更新
cur = parent;
parent = parent->_parent;
}
// 3.parent的_bf更新后为2或-2，此时需要旋转，旋转后以parent为根的子树为平衡二叉树，不需要在继续向上更新平衡因子
else if (parent->_bf == 2 || parent->_bf == -2)
{
if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
break;
}
}
return true;
}
bool IsBalance()
{
return is_balance(_root);
}
int Height()
{
return get_height(_root);
}
private:
// 检查该树是否平衡
bool is_balance(ptr root)
{
if (root == nullptr)
return true;
int leftHeight = get_height(root->_left);
int rightHeight = get_height(root->_right);
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_val << "平衡因子异常" << endl;
}
return (abs(rightHeight - leftHeight) == 1 || rightHeight == leftHeight)
&& is_balance(root->_left)
&& is_balance(root->_right);
}
// 获取以root为根的子树的高度
int get_height(ptr root)
{
if (root == nullptr)
return 0;
return 1 + max(get_height(root->_left), get_height(root->_right));
}
// 析构函数的子函数
void destroy(ptr root)
{
if (root == nullptr)
return;
destroy(root->_left);
destroy(root->_right);
delete root;
}
void _inorder(ptr root)
{
if (root == nullptr)
return;
_inorder(root->_left);
cout << root->_val << " ";
_inorder(root->_right);
}
// 左左--右单旋
void RotateR(ptr pParent)
{
ptr subL = pParent->_left;
ptr subLR = subL->_right;
ptr ppParent = pParent->_parent;
//1.pParent(父)和subLR(子)
pParent->_left = subLR;
if (subLR)
subLR->_parent = pParent;
//2.subL(父)和pParent(子)
subL->_right = pParent;
pParent->_parent = subL;
//3.ppParent(父)和subL(子)
if (pParent == _root)
{
_root = subL;
}
else
{
// 是否可以用函数参数引用 ptr& pParent 优化？
if (ppParent->_left == pParent)
{
ppParent->_left = subL;
}
else
{
ppParent->_right = subL;
}
}
subL->_parent = ppParent;
//4.更新平衡因子
subL->_bf = pParent->_bf = 0;
}
// 右右--左单旋
void RotateL(ptr pParent)
{
ptr subR = pParent->_right;
ptr subRL = subR->_left;
ptr ppParent = pParent->_parent;
pParent->_right = subRL;
if (subRL)
subRL->_parent = pParent;
subR->_left = pParent;
pParent->_parent = subR;
if (pParent == _root)
{
_root = subR;
}
else
{
// 是否可以用函数参数引用 ptr& pParent 优化？
//if (subR->_val < ppParent->_val)
if (ppParent->_left == pParent)
{
ppParent->_left = subR;
}
else
{
ppParent->_right = subR;
}
}
subR->_parent = ppParent;
subR->_bf = pParent->_bf = 0;
}
void RotateLR(ptr pParent)
{
ptr subL = pParent->_left;
ptr subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(pParent);
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
pParent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
pParent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
pParent->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(ptr pParent)
{
ptr subR = pParent->_right;
ptr subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(pParent);
if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
pParent->_bf = -1;
}
else if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
pParent->_bf = 0;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
pParent->_bf = 0;
}
else
{
assert(false);
}
}
ptr _root;
};
完。
如何匹配未被反斜杠转义的平衡定界符对(其本身未被反斜杠转义)(无需考虑嵌套)？例如对于反引号，我试过了，但是转义的反引号没有像转义那样工作。regex=/(?!$1:"how\\"#expected"how\\`are"上面的正则表达式不考虑由反斜杠转义并位于反引号前面的反斜杠，但我愿意考虑。StackOverflow如何做到这一点？这样做的目的并不复杂。我有文档文本，其中包括内联代码的反引号，就像StackOverflow一样，我想在HTML文件中显示它，内联代码用一些spanMaterial装饰。不会有嵌套，但转义反引号或转义反斜杠可能出现在任何地方。
我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是rubygems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和rubygems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是
给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：
我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:
我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？ 最佳答案 你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac
我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art