比如 10 9 这俩数 插入一个 6
10
/
9
/
6
这种旋转完之后就是
9
/ \
6. 10
但如果是这种的话
10 9 6 插入一个 4
10
/
9
/
6
/
4
10 和 9 都可以认为这棵树不平衡,也就是说 10 和 9 的左右子树都不平衡(或者说是故障点,等于现在树里有 2 个故障点)
逻辑上该认为哪个是轴呢
代码该从哪个节点开始处理呢
我知道旋转之后的结果肯定是这
9
/ \
6. 10
/
4
但是逻辑上不太清楚(或者说先处理哪个故障点呢)
1
noli 2019-02-12 17:14:00 +08:00 via iPhone
avl 树中有 10 9 6 三个节点上时候,就不可能是你现在画出来的样子吧?
|
2
ileadall 2019-02-12 21:02:44 +08:00
楼上加一,但事实上是下向上调整高度的时候,第一个不平衡的点来决定哪一种旋转类型。
|
3
drizztdouu00 2019-02-13 09:56:32 +08:00 via Android
每次插入后 会调整高度 不会出现你说的这种情况
|