数据结构和算法

一种简单的平衡树-AVL树

AVL 树AVL树(Adelson-Velskii 和 Laandis)树是带有平衡条件(balance condition)的二叉查找树。这个平衡条件必须要容易保持,而且他保证树的深度必须是 O(log N)。最简单的想法是要求左右子树具有相同的高度。 另一种平衡条件是要求每个节点都必须有相同高度的左子树和右子树。如果空子树的高度定义为 -1,那么只有具有 2k-1 个节