平衡树怎么旋转
平衡树如何旋转
15
11 20
8 14
13
如何旋卷呀
清华那本书实在看不明白
------解决方案--------------------
不要看严的书,去看殷人昆的书,讲得非常清楚.248页.
当插入一个新的节点p后,
从插入位置向根方向检验刚才的插入操作是否让某个节点的平衡因子大于1了.
如果没找到,则结束.
否则:
找到平衡因子大于1的节点,设该节点为t,则从t向p方向找到3个节点,然后进行左旋,右旋或者先左后右双旋或者先右后左双旋.
比如插入前:
15
11 20
8 14
插入13之后变成:
15
11 20
8 14
13
此时,从13向根15找:13-> 14-> 11-> 15,发现15的平衡因子大于1了;那就从15向13方向
查找,一共找3个:15-> 11-> 14.下面就针对15,11,13这3个节点处理.
用左右双旋.
先左旋变成(左旋就想象成用左手去往下掰):
15
14 20
11
8 13
在右旋变成(自然就是用右手往下掰了):
14
11 15
8 13 20
这就是最终结果了.
清华很喜欢AVL树,一定要弄的明明白白哦.
还有一种平衡树叫Red-Black树,但是感觉没有AVL树更能说明平衡的思想.
虽然我不知道实际工程里面用哪个,但还是AVL树更好理解.
15
11 20
8 14
13
如何旋卷呀
清华那本书实在看不明白
------解决方案--------------------
不要看严的书,去看殷人昆的书,讲得非常清楚.248页.
当插入一个新的节点p后,
从插入位置向根方向检验刚才的插入操作是否让某个节点的平衡因子大于1了.
如果没找到,则结束.
否则:
找到平衡因子大于1的节点,设该节点为t,则从t向p方向找到3个节点,然后进行左旋,右旋或者先左后右双旋或者先右后左双旋.
比如插入前:
15
11 20
8 14
插入13之后变成:
15
11 20
8 14
13
此时,从13向根15找:13-> 14-> 11-> 15,发现15的平衡因子大于1了;那就从15向13方向
查找,一共找3个:15-> 11-> 14.下面就针对15,11,13这3个节点处理.
用左右双旋.
先左旋变成(左旋就想象成用左手去往下掰):
15
14 20
11
8 13
在右旋变成(自然就是用右手往下掰了):
14
11 15
8 13 20
这就是最终结果了.
清华很喜欢AVL树,一定要弄的明明白白哦.
还有一种平衡树叫Red-Black树,但是感觉没有AVL树更能说明平衡的思想.
虽然我不知道实际工程里面用哪个,但还是AVL树更好理解.