https://github.com/kangjianwei/Data-Structure/blob/master/▲课本算法实现 /▲09%20 查找 /07%20BalancedBinarySortTree/BalancedBinarySortTree.c#L305-L310
(链接显示不对,调不过来了,总之你看链接的指向应该知道在哪里找...)
在发现左边失衡要调整的时候,值考虑了 LH,RH,但是还有 EH 这种特殊的情况
这种特殊的情况只出现在删除节点时, 测试数据:
依次插入: 9 5 10 -1 6 11 -2 1 2
然后删除 10
会使 9 节点失衡,EH=2,但是这个失衡是 9 右子树某节点删除导致的,而不是 9 左子树插入新节点导致的
这时,似乎需要对 9 当做 LL 型进行旋转:
就像这个代码: https://www.geeksforgeeks.org/avl-tree-set-2-deletion/ 中的:
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
这里考虑了==0 的情况 是课本出错了吗?这个教材很权威的吧,我还是认为可能自己哪里想错了
1
heyenyan 2019-08-10 07:16:23 +08:00 via Android
9 为什么会失衡?
|
2
Alozxy 2019-08-10 07:25:37 +08:00
不知到你用的是哪一版的教材,我手上的这一版只有写插入操作,没有删除操作的描述
|
3
dlsflh 2019-08-10 08:46:03 +08:00 via Android
咦…教材出错不是很正常的事情吗
|
7
Alozxy 2019-08-10 15:11:08 +08:00
|