平衡树

搜索二叉树

概念

术语	说明
度	节点含有的子树的个数称为该节点的度
树的度	最大的节点度称为树的度
叶节点	度为零的节点
深度	对于任意节点 n，n 的深度为从根到 n 的唯一路径长，根的深度为 0
高度	对于任意节点 n，n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0
森林	由 m（m>=0） 棵互不相交的树的集合称为森林
堂兄弟节点	同层的节点互为堂兄弟节点
兄弟节点	相同父节点的节点互称为兄弟节点
节点的祖先	从根到该节点所经分支上的所有节点
根据父节点被遍历输出的顺序	可以分为先序遍历,中序遍历,后序遍历。
红黑树的路径	从根节点到空节点被成为一条路径

二叉搜索（排序）树

构成条件:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。

• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。

• 左右子树也分别为二叉搜索树。

性质

• 当在二叉搜索树当中搜索数据的时候，最多搜索高度次——O(n)，此时退化为单支，当二叉树平衡时，使用O(logn)时间。

注意

• 不允许存在重复节点。

• 在代码实现时，需要记录其父节点。

• 中序遍历有序，并且由于优先遍历当前最小节点，所以也是升序的。

删除节点

1. 当需要删除的节点为叶节点，直接删除即可。
2. 当要删除的节点只有一个子节点，将待删除节点替换为其子节点即可
3. 当待删除节点的度为2时：
   • 找到待删除节点在“中序遍历序列”中的下一个节点，记为 tmp 。
   • 用 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp 即可——删除叶子节点。

/* 删除节点 */
void remove(int num) {
    // 若树为空，直接提前返回
    if (root == nullptr)
        return;
    TreeNode *cur = root, *pre = nullptr;
    // 循环查找，越过叶节点后跳出
    while (cur != nullptr) {
        // 找到待删除节点，跳出循环
        if (cur->val == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 若无待删除节点，则直接返回
    if (cur == nullptr)
        return;
    // 子节点数量 = 0 or 1
    if (cur->left == nullptr || cur->right == nullptr) {
        // 当子节点数量 = 0 / 1 时， child = nullptr / 该子节点
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 删除节点 cur
        if (cur != root) {
            if (pre->left == cur)
                pre->left = child;
            else
                pre->right = child;
        } else {
            // 若删除节点为根节点，则重新指定根节点
            root = child;
        }
        // 释放内存
        delete cur;
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode *tmp = cur->right;
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 递归删除节点 tmp
        remove(tmp->val);
        // 用 tmp 覆盖 cur
        cur->val = tmpVal;
    }
}

AVL树(作者命名)

AVL 树既是二叉搜索树，也是平衡二叉树。

构成条件

• 它的左右子树都是AVL树。
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)，从而可以防止二叉搜索树的退化。

注意

1. AVL 树的相关操作需要获取节点高度。
2. “节点高度”是指从该节点到它的最远叶节点的距离。
3. 叶节点的高度为0，而而空节点的高度为 -1。

平衡因子

节点平衡因子 = 左子树高度 - 右子树高度

对于一棵 AVL 树的任意节点的平衡因子始终保持在[-1,-1]区间。

AVL 树旋转

当平衡因子绝对值大于1时，对应的节点就被称为“失衡节点”。根据失衡情况的不同，又有不同的平衡方式:

• 左旋转：将失衡节点旋转到右子节点的左子节点位置。——LL

• 右旋转：将失衡节点旋转到左子节点的右子节点位置。——RR

对于左旋来说，如果它的右子树存在，那么:

• 右子树会代替失衡节点的位置，并且将失衡节点作为自身的左子树。

• 右子树本身的左子树，将会被嫁接到失衡节点的右子树位置。

右旋则是以上操作的镜像

• 先左(右)旋后右(左)旋——LR(RL)

需要旋转两次，旋转方向和顺序与类型名称相同，也就是 LR 先左旋后右旋，RL 先右旋后左旋

• 步骤一：将新增节点的父节点，安插在根节点和根节点的左子节点之间。（谋权）

• 步骤二：然后将根节点变为它的空侧的子节点（篡位），然后将原新增的节点（就是被抛弃的子节点），变换原来的方向,嫁接在新根节点的子节点上（变节）

调整后的子树的根节点一定是新增节点的父节点，所以称之为谋权篡位

如何选择平衡？

• LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由 1 变为 2。

• RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由 -1 变为 -2。

• LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由 1 变为 2。

• RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由 -1 变为 -2。

例题验证

运用场景

由于AVL树需要旋转来保持平衡，而旋转是非常耗时的。因此：

• 适合用于插入 删除次数比较少，但查找多的情况。

红黑树(颜色命名)

通过对任何一条从根到叶子的路径上各个节点着色的方式的限制。

性质

1. 红黑树中，NIL节点（空叶子节点）为黑色。

2. 节点为红色或黑色，且一个节点是红色的，那它的孩子必须是黑的。 —— 任何路径没有连续的红色节点。

3. 根节点必须是黑色。

4. 红黑树确保最长路径不会超过最短路径的两倍，且红黑树不是严格平衡。 —— 高效的关键。

5. 每条路径，均包含相同数目的黑色节点。

6. 任何不平衡都会在三次旋转之内调整完毕。

插入

• 插入红色节点而不是黑色节点，因为插入黑色节点会影响性质 5，对其它路径产生影响。

• 而且，如果当插入的节点的父节点是黑色的时候，那么就是完全正确的插入。但如果父节点是红色，那么会违反性质2，此时要进行调整）。

如何平衡，旋转？详情——红黑树平衡变换

使用场景：

红黑树多用于搜索、插入、删除操作多的情况。