Java数据结构和算法 - AVL树

2021/07/23 algorithm 共 403 字,约 2 分钟
Bob.Zhu

AVL树是最早的一种平衡树,它以发明者的名字命名:Adelson-Velskii 和 Landis。在AVL树中每个节 点存储一个额外的数据:它的左子树和右子树的高度差。这个差值不会大于1,也就是说,节点的左子树的高 度和右子树的高度相差不会大于一层。

插入之后,检查新节点插入点所在的最低子树的根,如果他的子节点的高度相差大于1,执行一次或者两次旋 转使它们的高度相等。然后算法向上移动,检查上面的节点,必要时均衡高度。这个检测检查所有路径一直 向上,直到根为止。

AVL树查找的时间复杂度为O(logN),因为树一定是平衡的。但是,由于插入(或者删除)一个节点时需要扫 描两趟树,一次向下查找插入点,一次向上平衡树,AVL树不如红黑树效率高,也不如红黑树常用。

![image-alter](/image/post/2021/07/23/01/xxx.jpg)

参考资料

文档信息

Search

    Table of Contents