平衡二叉搜索树

1. 树的概念

image

一个树由节点组成，这些节点包含根节点，父节点，子节点，兄弟节点；没有任何一个节点的树称为空树；如果一棵树只包含一个节点，那么该节点为根节点；

节点的度（degree）: 子树的个数
树的度：所有节点度中的最大值
叶子节点：度为0的节点
非叶子节点：度不为0的节点
层数（level）: 根节点在第1层，根节点的子节点在第2层，以此类推
节点的深度（depth）: 从根节点到当前节点的唯一路径的节点总数
树的深度：所有节点深度的最大值
节点的高度：从当前节点到最远叶节点的路径节点总数
树的高度：所有节点高度中的最大值
树的深度等于树的高度

二叉树是每个节点的度最大为2的树，分别为 左子树 或 右子树；树按类型分为 有序树 和 无序树，二叉树是一种有序树。二叉树特征：

二叉树

非空二叉树的第 i 层，最多包含由 $i^{2-1}$ 个节点，其中i >= 1;
高度为h的二叉树上，最多包含 $2^h$ - 1 个节点，其中h >= 1;
对于任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则n0 = n2 + 1;

假设节点度为1的个数是n1，那么二叉树的总节点树n = n0 + n1 + n2；
二叉树的边数 boundary = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1；
可得出 n0 = n2 + 1;

二叉树分类：

真二叉树 是度为0，或度为2
满二叉树 是度为0，或度为2，且所有的叶子节点都是最后一层；满二叉树肯定是真二叉树，而且是相同层数的二叉树中节点个数最多的。

满二叉树
完全二叉树 是指叶子节点只会出现在最后两层，而且最后一层的叶子节点都是向左对齐的。完全二叉树从根节点到倒数第二层都是满二叉树。完全二叉树的特效如下：

度为1 的节点只有左节点。且度为1的节点数只有1个或0个；
同样的节点数的二叉树，完全二叉树的高度最小；
假设完全二叉树的高度为h (h >= 1), 那么有
至少有 $2^{h-1}$ 个节点；
最多有 $2^{h}$ - 1 个节点；
节点数为 $2^{h-1}$ <= n < $2^{h}$ ;
h-1 <= $\log_2{n}$ < h ；
h = floor( $\log_2{n}$ ) + 1 ；

如果有n 节点的完全二叉树(n>0)，从上到下，从左到右的节点排序索引从1开始，对于任意的第i个节点；

i = 1 , 表示根节点；
i > 1 ，则父节点索引为floor(i/2)；
如果 2i <= n，它的左子树索引为 2i ；
如果 2*i > n ，该节点无左子树；
如果 2i + 1 <= n ,该节点的右子节点索引为 2i + 1;
如果 2*i + 1 > n，该节点无右子节点；

2. 二叉树的遍历

二叉树的遍历分为 前序遍历（Preorder Traversal），中序遍历（Inorder Traversal）， 后序遍历（Postorder Traversal），层序遍历（Level Traversal）。

前序遍历：从根节点, 前序遍历左子树，前序遍历右子树。遍历顺序为：4，2，1，3，6，5，7；
中序遍历：中序遍历左子树、根节点、中序遍历右子树。遍历顺序为：1，2，3，4，5，6，7；
后序遍历：后序遍历左子树、后序遍历右子树、根节点。遍历顺序为：1，3，2，5，7，6，4；
层序遍历：从上到下，从左到右依次访问每个节点。遍历顺序为：4，2，6，1，3，5，7；

层序遍历的应用：

计算二叉树的高度：

    public int height() {
        if (root == null) return 0;
        
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) { // 意味着即将要访问下一层
                levelSize = queue.size();
                height++;
            }
        }
        
        return height;
    }

    // 方式2
    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

判断是否为完全二叉树：

    public boolean isComplete() {
        if (root == null) return false;
        
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) { // node.left == null && node.right != null
                return false;
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            } else { // node.right == null
                leaf = true;
            }
        }
        
        return true;
    }

前驱节点与后继节点

前驱节点（predecessor）：中序遍历时的前一个节点。即node.left.right.right.right...，直到right为null;
后继节点（successor）：中序遍历时的后一个节点。即node.right.left.left.left...，直到left为null;

3. 二叉搜索树

二叉搜索树是二叉树的一种，又被称为二叉查找树、二叉排序树。英文缩写为BST。

任意一个节点的值大于其左子树所有节点的值；
任意一个节点的值小于其右子树所有节点的值；
二叉搜索树节点的值必须具备可比较性。比如int， float, 如果是 自定义的对象 必须指明比较方式；
二叉搜索树的搜索、删除、添加最坏时间复杂度均可优化为O(logn)；
不允许为null；

4. 平横二叉搜索树

时间复杂度分析

上图为二叉搜索树的时间复杂度，当n较大时两者的差异比较明显。所以为了保障二叉搜索树的性能，需要保障左右子树的平衡。

平衡：当节点数量固定时，左右子树的高度越接近，这颗树就越平衡，即树的高度越低。最理想的平衡像完全二叉树、满二叉树，高度达到最小。

改进二叉搜索树的方式是在节点的添加，删除操作之后，想办法让二叉搜索树达到平衡，从而达到一颗适度平衡的二叉搜索树，称为平衡二叉树。

平衡二叉树 英文简称BBST，常见的典型平衡二叉树有：

AVL， Window NT内核中广泛使用；
红黑树， java的TreeMap, TreeSet, HashMap, HashSet等广泛使用。

5. AVL

平衡因子（Balance Factor）指某个节点左右子树的高度差；
AVL 特点：

每个节点的平衡因子只能为-1、0、1；

搜索，添加，删除的时间复杂度为O(logn)；

添加节点导致的失衡以及解决办法：

向AVL树中添加节点时（只会在叶子节点添加），可能会导致所有祖先节点都失衡，但是父节点、非祖父节点都是不可能失衡的。
LL ----- 右旋转

右旋转
RR ----- 左旋转

左旋转
LR ----- LR 旋转

LR旋转
RL ----- RL旋转: 与LR 旋转相似，先将p右旋转，再将g左旋转；略...

添加节点后，调整平衡

删除节点导致的失衡以及解决办法：

可能会导致 父节点 或 祖先节点 失衡（只有1个节点失衡），其他节点不会导致失衡。恢复平衡后，可能会导致更高层的祖先节点失衡。删除和添加的都是根据节点所在的位置是否失衡，来进行旋转，以达到平衡。
一直递归父节点以及祖父节点，先判断平衡因子是否-1，0，1，如果不是调整节点的平衡(rebalance)

删除后，调整平衡

平均时间复杂度

搜索：O(logn)；
添加：O(logn)，仅需O(1)次旋转操作;
删除：O(logn)，最多需要O(logn)次旋转操作；

6. 红黑树

红黑树

红黑树也是一种自平衡的二叉搜索树，红黑树的5个特性：

节点是 Red 或者 Black；
根节点是 Black；
叶子节点（外部节点、空节点）为 Black；
Red 的子节点都是 Black节点（即在所有路径上，不可能包含连续2个为 Red 的节点）；
任意节点 到 叶子节点的所有路径上包含相同数量的 Black 节点；

红黑树和 4阶B树具有等价转化。

Black 节点与它的 Red 子节点融合形成B树的一个节点；
红黑树的 Black 节点个数与 4阶B树的节点总数相等；

1）添加节点：

parent : 父节点
sibling : 兄弟节点
uncle : 叔父节点（parent节点的兄弟节点）
grand : 祖父节点（parent节点的父节点）
新添加的节点必须添加到叶子节点中，建议新添加的为 Red 节点，这样可以尽可能满足红黑树性质，即满足性质1，2，3，5，性质4不一定满足。

如果添加的是根节点，那么直接染成 Black；
如果 parent 节点是 Black，那么添加的 Red 节点不需要做任何处理，就已经符合红黑树的全部性质；

88节点的添加
如果 parent 节点是 Red，就会出现连续两个 Red，不符合性质4，需要进行处理；
a. 如果 uncle 节点不是 Red，将会导致节点上溢；
b. 如果 uncle 节点不是 Red，添加节点的位置 LL \ RR；
1）将 parent 染成 Black，将 grand 染成 Red；
2）对 grand 进行单旋转操作；

uncle节点不是red，LL\RR情况

c. 如果 uncle 节点不是 Red, 添加节点的位置 LR \ RL；
1）将自己染成 Black，将 grand 染成 Red；
2）进行 LR\RL 双旋转；

uncle节点不是red，LR\RL情况

d. 如果 uncle 节点是 Red；
1）将 parent，uncle 染成Black；
2）将 grand 染成 Red，向上合并，即当作新的节点进行处理；

uncle节点是red，将parent、uncle染成black，grand染成red，向上合并当作新节点添加

2）删除节点：

由于删除节点时，我们会使用B树的前驱或后继节点来替换该节点，实际上删除都是叶子节点

删除的是 Red 节点，不需要任何处理；
不可能直接删除拥有2个Red 子节点的 Black 节点，因为这个节点会找到前驱或后继节点来替换，所以不考虑；
所以只需要考虑，删除的是拥有 1个Red 子节点的 Black 节点或者 Black的叶子节点:
删除的是拥有 1个Red 子节点的 Black 节点：
a. 用 Red子节点替代 parent节点；
b. 将替代的Red 子节点染成 Black，既可以修复红黑树性质；
删除Black的叶子节点，并且sibling为Black；
a. 如果sibling最少有一个Red 子节点：
1）根据情况，进行之前的LL、RR、LR、RL旋转
2）旋转后，中心点（该子树的根节点）继承parent的颜色；
3）旋转后，将左右子节点染成 Black；

删除Black的叶子节点，并且sibling为Black（80）

b. sibling没有一个Red 子节点：
1）将sibling 染成 Red, parent 染成 Black，就可以修复红黑树性质；

删除Black的叶子节点，sibling没有一个**Red** 子节点

删除Black的叶子节点，并且sibling为 Red；
a. 先将sibling染成 Black，parent 染成 Red，在进行旋转操作；
b. 回到sibling 是 Black的情况，再进行删除操作；

删除**Black**的叶子节点，并且sibling为 **Red**

3）红黑树的平均时间复杂度：

搜索：O(logn)；
添加：O(logn)，O(1)次旋转；
删除：O(logn)，O(1)次旋转；

4） AVL 与红黑树对比：

AVL 标准比较严格，平衡因子不能超过1；
AVL的树高度比红黑树高度低；
AVL搜索，添加，删除的时间复杂度都是O(logn)，添加仅需O(1)次旋转调整，删除最多需要O(logn)次旋转操作；
红黑树的搜索，添加，删除操作时间复杂度都是O(logn)，添加和删除仅需O(1)次旋转调整；
搜索的次数远远大于添加，删除时，优先选择AVL（高度比较低），否则选择红黑树，总体上红黑树的性能比 AVL高；

绘图工具： BinaryTreeGraph；