AVL树
一. AVL树概念
一棵AVL树具有以下性质:
1.它的左右子树都是AVL树。
2.左子树和右子树高度之差(简称平衡因子)的绝对值不超过(-1,0,1)。
二.平衡化旋转
1.左单旋
(右右->左):在较高右子树的右侧插入新节点,则用左单旋
- 情况一:(如下图)
- 情况二:
- 情况三:
-
情况四:
2.右单旋
(左左->右):在较高左子树的左侧插入新节点,用右单旋
3.先左后右双旋
(左右):在较高左子树的右侧
4.先右后左双旋
(右左):在较高右子树的左侧