数据结构-二叉树

二叉排序树

二叉排序树（Binary sort tree）又称为二叉查找树、二叉搜索树。

二叉排序树可以是空树，或是满足以下性质的二叉树：

• 若其 左子树 非空，则左子树上的结点都 小于 根结点的值；
• 若其 右子树 非空，则右子树上的结点都 大于等于 根结点的值；
• 其左右子树本身也各是一棵二叉排序树。

含有 n 个结点的二叉排序树的平均查找长度和树的形态有关。

一个无序序列可以通过二叉排序树变成一个有序序列，构造树的过程就是对无序序列进行排序的过程。

平衡二叉树

Q: 如何提高形态不均衡的二叉排序树的查找效率？
A: 做 “平衡化” 处理，尽量让二叉树的形状均衡。

定义：又称 AVL 树（Adelson-Velskii and Landis）
一棵平衡二叉树或者是子树，或者是具有下列性质的二叉排序树：
1.左子树与右子树的高度之差的绝对值小于等于1；
2.左子树和右子树也是平衡二叉排序树。

为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）
平衡因子 = 结点左子树的的高度 - 结点右子树的高度
根据二叉平衡树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0 或 1。

对于一棵有 n 个结点的 AVL 树，其高度保持在 $O(log_2n)$ 数量级，ASL 也保持在 $O(log_2n)$ 量级。

失衡二叉树平衡调整的四种类型：

二叉树平衡调整

红黑树

红黑树是一种 自平衡 的排序二叉树。

五个性质：

1. 每个节点非红即黑；
2. 根节点总是黑色的；
3. 每个叶子节点都是黑色的空节点（NIL节点）；
4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

为什么要用红黑树？
简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。