AVL树是一颗平衡二叉查找树,平衡指左子树和右子树高度差为1,因此他的高度始终为O(logN)级别。
一.创建:需要从上往下进行判断这个树是否失衡。如果失衡的话需要进行调整:
1.找到失衡的节点进行调整:如图
此时是个平衡二叉查找树,我们要插入节点1的话,变成上图的样子,已经失衡了我们需要进行右旋转,所谓右旋转指的是距离差距节点最近的失衡节点变成了它子节点的右孩子。于是:
这样又变成了avl树。如果节点3本身具有右节点a3那么把a3放在5号节点之后。左旋转和右旋转是相反的操作。
2.左旋右旋无法变成avl树的时候我们需要左右互相使用: