平衡树学习笔记

· · 个人记录

全称“平衡二叉搜索树”

二叉搜索树(BST)

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树。
性质：一个节点x左子树所有点的关键字都比x的关键字小，右子树所有点的关键字都比x的关键字大
二叉搜索树很多时候用来进行数据查找。这个过程从树的根结点开始，沿着一条简单路径一直向下，直到找到数据或者得到空值。 通常查询等操作的时间复杂度为O(log_2 n)到O(n)之间。

平衡树

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，依据序列构造的二叉搜索树为右斜树。此时二叉树退化成单链表，搜索效率降低为 O(n)。
二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。
节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。
这种左右子树的高度相差不超过 1 的树为平衡二叉树。

平衡树具有如下特点：

  1. 具有二叉查找树的全部特性。

  2. 每个节点的左子树和右子树的高度差至多等于1。

通过平衡树，我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(log_2 n)。

实际应用中每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，因此我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

平衡树常见的类型有：

其中红黑树常见于工程写法，OI中常用treap维护权值信息，Splay维护区间信息。

学习笔记——treap

学习笔记——Splay