码云
SBTree
insert中对头节点的处理
void Insert(int val)
{
Node* node = new Node(val);
// 找插入位置
if (_root == nullptr)
{
_root = node;
return;
}
else
{
Node* pre = _root, *head = _root;
while (head)
{
pre = head;
if (head->_val < val) head = head->_right;
else if (head->_val > val) head = head->_left;
else
{
assert(false);
}
}
if (val < pre->_val) pre->_left = node;
else pre->_right = node;
}
}
pop需要记住规律
- 右边为nullptr
- 左边为nullptr
- 两边都为nullptr
- 两边都不为nullptr
将情况3合并到情况1，2一起分析
void pop(int val)
{
// 需要在一开始找cur的时候就要找到pre节点
// 因为需要改变pre后的节点
// 找cur阶段不需要找pre节点，pre节点指的是左树最右边节点的父节点
// 在左右有nullptr的时候是需要直接进行调整的——需要知道pre节点
// 所以必须在找des的时候找到pre节点
Node* des = _root, * pre = _root;
while (des)
{
// 只有在向下变换的时候才会变
// 如果在一开始就变，当他在找到des的时候，也会变换一次，这个时候就坏了
//pre = des;
if (des->_val < val) pre=des,des = des->_right;
else if (des->_val > val) pre=des,des = des->_left;
else
{
if (des->_left == nullptr)
{
if (pre == _root)
{
_root = pre->_right;
}
// 左为空
else if (pre->_left == des)
{
pre->_left = des->_right;
}
else
{
pre->_right = des->_right;
}
delete des;
des = nullptr;
}
else if (des->_right == nullptr)
{
if (pre == _root) _root = _root->_left;
else if (pre->_left == des)
pre->_left = des->_left;
else pre->_right = des->_left;
delete des;
des = nullptr;
}
else
{
// 两边都不是空节点
pre = des;// 必须要将pre节点进行转移
Node* cur = des->_left;
// 进行找节点的时候必须保证这个子树不是空树
// 找左树的最右节点
while (cur->_right)
{
pre = cur;
cur = cur->_right;
}
swap(cur->_val, des->_val);
pre->_right = cur->_left;
delete cur;
cur = nullptr;
}
break;
}
}
}
- 必须在查找目标删除节点的时候就要
提供pre节点的位置——在目标节点的左右有节点为空的时候需要立即知道pre节点并直接进行链接 - 删除的点是否为
根节点
<1> 目标节点的左右有空节点的情况
需要考虑删除的点是根节点（需要特殊判断)
<2> 在目标节点的左右不为空的情况
不需要考虑这个点是否为根节点，他的变换规则是找到左边最大的或者右边最小的交换，所以不需要考虑是否为根节点 - 循环
终止条件是找到了nullptr依旧没有找到目标节点 - 在
insert中，pre需要一起更新；在pop中，在查找过程中更新，不能一起更新，如果des已经找到了目标节点，但是你在已进入循环就更新，那直接就将pre移动到了需要删除的点的位置，当左右节点有空的时候就找不到pre节点
AVL
概念
任意节点的
左右高度 < 2，并且使用平衡因子——右树高度-左树高度
insert
pop不需要知道，如果想知道，可以去网上找找
void insert(const T& val)
{
Node* node = new Node(val);
if (_root == nullptr)
{
_root = node;
return;
}
Node* des = _root, * pre = _root;
while (des)
{
pre = des;
if (des->_val < val) des = des->_right;
else if (des->_val) des = des->_left;
else assert(false);
}
if (pre->_val < val) pre->_right = node, pre->_bf++;
else pre->_left = node, pre->_bf--;
node->_parent = pre;
// 进行调整
Node* cur = pre;
pre = cur->_parent;
while (pre && cur->_bf)
{
if (pre->_left == cur) pre->_bf--;
else pre->_bf++;
if (pre->_bf == -2 && cur->_bf == -1)
{
rotateR(pre);
break;
}
else if (pre->_bf == 2 && cur->_bf == 1)
{
rotateL(pre);
break;
}
else if (pre->_bf == -2 && cur->_bf == 1)
{
rotateLR(pre);
break;
}
else if (pre->_bf == 2 && cur->_bf == -1)
{
rotateRL(pre);
break;
}
else
{
cur = pre;
pre = cur->_parent;
}
}
}
void rotateL(Node* pre)
{
Node* subR = pre->_right, *subRL = subR->_left;
Node* ppre = pre->_parent;
subR->_parent = ppre;
if (pre == _root)
{
_root = subR;
}
else
{
if (ppre->_right == pre) ppre->_right = subR;
else ppre->_left = subR;
}
pre->_parent = subR;
subR->_left = pre;
pre->_right = subRL;
if (subRL) subRL->_parent = pre;
pre->_bf = subR->_bf = 0;
}
void rotateR(Node* pre)
{
Node* subL = pre->_left, *subLR = subL->_right;
Node* ppre = pre->_parent;
subL->_parent = ppre;
if (pre == _root)
{
_root = subL;
}
else
{
if (ppre->_right == pre) ppre->_right = subL;
else ppre->_left = subL;
}
pre->_parent = subL;
subL->_right = pre;
pre->_left = subLR;
if (subLR) subLR->_parent = pre;
pre->_bf = subL->_bf = 0;
}
void rotateRL(Node* pre)
{
Node* subR = pre->_right;
int bf = subR->_left->_bf;
rotateR(subR);
rotateL(pre);
if (bf == 1) pre->_bf = -1;
else subR->_bf = 1;
}
void rotateLR(Node* pre)
{
Node* subL = pre->_left;
int bf = subL->_right->_bf;
rotateL(subL);
rotateR(pre);
if (bf == -1) pre->_bf == 1;
else subL->_bf = -1;
}
- 插入
第一个节点对根节点进行特判 - 插入的时候需要知道pre节点，插入的同时要调整平衡因子
- 注意循环更新条件
while (pre && cur->_bf)，我们要更新的是pre节点，所以pre必须要有；cur->bf 如果为0的话，证明子树已经平衡，不会影响上面；如果bf是1，可能还有向上影响的可能需要继续向上 - 在代码复用上，一定要小心，需要在复用的时候，将需要变化的位置进行改变才行
单旋的时候需要注意pre节点是根节点以及subLR节点是空节点的情况双旋的平衡因子更新是不同的，需要特别分析
左右双旋
