avl_tree.md

自平衡二分搜索树

• 树的平衡：对于树中的任意节点，其左右子树的高度差不超过1。

• 节点高度：当前节点高度为其左右子树最高树高 + 1，空树的高度为0。

• 平衡因子：当前节点的左右子树高度差。

自平衡二分搜索树：AVL Tree

AVL 树是最早被发明的自平衡二叉搜索树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis 。