AVL树是一种自平衡二叉搜索树(BST),对于所有节点,其左右子树的高度差不能超过1。大多数BST操作(例如:搜索,最大,最小,插入,删除)以O(h)为时间,h是BST的高度。对于倾斜的二叉树,这些操作的成本可能变成O(n)。如果我们确保在每次插入和删除之后树的高度仍然是O(Logn),那么我们就可以保证所有这些操作的O(Logn)的上界。AVL树的高度总是O(Logn),其中n是树中的节点数。左

- 阅读全文 -