带你读《图解算法小抄》十二、树(5)https://developer.aliyun.com/article/1348183?groupCode=tech_library
2. AVL树
在计算机科学中,AVL树(以发明者Adelson-Velsky和Landis的姓氏命名)是一种自平衡的二叉搜索树。它是第一种这样的数据结构。
在AVL树中,任何节点的两个子树的高度最多相差一;如果它们的高度相差超过一,就会进行重新平衡以恢复这个性质。
查找、插入和删除在平均情况和最坏情况下都需要 O(log n) 的时间,其中n是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。
动画展示了将多个元素插入AVL树中的过程。它包括左旋、右旋、左右旋和右左旋。
带有平衡因子的AVL树(绿色)
1)AVL树的旋转操作
左-左旋转
右-右旋转
左-右旋转
右-左旋转
带你读《图解算法小抄》十二、树(7)https://developer.aliyun.com/article/1348179?groupCode=tech_library