二叉搜索树在添加、删除节点时，都可能会导致二叉搜索树退化成链表，为了防止二叉搜索树退化成链表，让添加、删除、搜索的复杂度维持在O(logn)，我们需要在添加或者删除节点操作之后，想办法让二叉搜索树恢复平衡。
平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度越低）
最理想平衡，就是像完全二叉树、满二叉树那样，高度是最小的
二叉搜索树调整方案：用尽量少的调整次数达到适度平衡即可，一棵达到适度平衡的二叉搜索树，可以称之为平衡二叉搜索树
平衡二叉搜索树
Balanced Binary Search Tree，简称 BBST，经典常见的平衡二叉搜索树有：
- AVL树
- 红黑树
一般也成它们为：自平衡的二叉搜索树
网友评论