数据结构-平衡树

😊 | Powered By HeartFireY | Balanced Tree

📕 | 需要的前导知识：二叉搜索树(BST)

一、概念

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

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

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

二、分类

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