数据结构-平衡树

数据结构-平衡树 😊 | Powered By HeartFireY | Balanced Tree 📕 | 需要的前导知识：二叉搜索树(BST) 一、概念

平衡树是二叉搜索树和堆合并构成的数据结构，它满足以下性质：

1. 空树是平衡树；
2. 非空平衡树左右两个子树高度的绝对差不超过 1 1 1；
3. 非空平衡树左右子树均为平衡树

对一棵二叉搜索树进行查询/新增/删除等操作，所花的时间与树的高度 h h h成比例，如果二叉搜索树退化为链，那么 h = n h = n h=n，此时时间复杂度最差。因此让树尽可能的维持矮平的状态有利于提高算法的时间复杂度。

如果能够将树结构的高度维持在 log ⁡ n \log n logn的状态下，则时间复杂度最优，此时的二叉搜索树我们成为平衡二叉搜索树(Balanced Search Tree)。

二、分类

1. Treap
2. Splay
3. WBLT
4. Size Balanced Tree
5. AVL Tree
6. 红黑树
7. 伸展树

由于各个知识点占用篇幅较大，具体各部分内容单独形成博客，不合并在本篇博客讲述。