AVL树
August 8, 2018 · View on GitHub
在计算机科学中,AVL树 (以发明者 Adelson-Velsky 和 Landis 命名) 是一种 自平衡 二元搜索树. 这是第一个发明的数据结构. 在AVL树中,任何节点 的 两个子树的高度 最多相差一个; 如果在任何时候它们相差 多于一个,则重新平衡以恢复此属性. 查找,插入和删除 在 平均和最差情况 下 都需要O(log n)的时间,其中 n 是操作之前 树中节点的数量. 插入和删除 可能需要通过 一个或多个树 旋转来重新平衡树.
动画显示将多个元素插入到 AVL树 中. 它包括左,右,左右和左右旋转.
具有平衡因子的AVL树 (绿色)
AVL树旋转
左左旋转
右旋转
左右旋转
左右旋转
