Tree

SCNU-Turing-Class CLRS Discussion Week4-5

---

$Ciallo～(∠・ω< )⌒★！$​

​右子树就是柚子树
​柚子厨蒸鹅心

$Ciallo～(∠・ω< )⌒★！$

二叉树 Binary Tree

二叉树的定义

​一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。

​每个节点包含的属性有：
1. left指针，指向左子节点
2. right指针，指向右子节点
3. prev指针，指向父节点（书上这么写的，但实际构建可能不写这个。当然可以构建一个prev指针指向父节点，形成一个双向二叉树）
4. key关键字，节点的值

构建代码如下：

//c++
struct TreeNode {
    int val;          // 节点值
    TreeNode *left;   // 左子节点指针
    TreeNode *right;  // 右子节点指针
    TreeNode *prev;   // 父节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), prev(nullptr) {}
};

二叉树常用术语

• 「根节点 $root\ node$ 」：位于二叉树顶层的节点，没有父节点。
• 「叶节点 $leaf\ node$ 」：没有子节点的节点，其两个指针均指向 None 。
• 节点的「度 $degree$ 」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的「高度 $height$ 」：从根节点到最远叶节点所经过的边的数量。
• 节点的「深度 $depth$ 」：从根节点到该节点所经过的边的数量。
• 节点的「高度 $height$ 」：从距离该节点最远的叶节点到该节点所经过的边的数量。

常见二叉树类型

• 完美二叉树 $perfect\ binary\ tree$

  • 所有层的节点都被完全填满。
  • 在完美二叉树中，叶节点的度为 0，其余所有节点的度都为2
  • 若树的高度为 ℎ ，则节点总数为 2^ℎ+1^−1 ，呈现标准的指数级关系。

• 完全二叉树 $complete\ binary\ tree$

  • 只有最底层的节点未被填满
  • 最底层节点尽量靠左填充。

• 完满二叉树 $full\ binary\ tree$

  • 所有节点都有两个子节点（除了叶节点）。

• 平衡二叉树 $balanced\ binary\ tree$

  • 任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

二叉树的退化

​ 当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

• 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
• 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至$O(n)$​。

	完美二叉树	链表
第$i$层的节点数量	$2^{i-1}$	$1$
高度为$h$的树的叶节点数量	$2^{h-1}$	$1$
高度为$h$的树的节点总数	$2^{h-1}-1$	$h+1$
节点总数为$n$的树的高度	$\log_{2}{(n+1)}-1$	$n-1$

二叉搜索树 Binary Search Tree

• 一棵 x.left.key$\le$ x.right.key 的二叉树

二叉树的遍历

深度优先搜索 Depth-first traversal

• 二叉树的遍历在「深度优先搜索 DFT」中分为三种：

  • 前序遍历

  • 中序遍历

  • 后续遍历

代码实现

INORDER-TREE-WALK(x) 
 if x≠NIL 
 INORDER-TREE-WALK(x.left) 
 print x.key
 INORDER-TREE-WALK(x.right)

/* 前序遍历 */
void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

/* 中序遍历 */
void inOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root->left);
    vec.push_back(root->val);
    inOrder(root->right);
}

/* 后序遍历 */
void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}

复杂度分析

• 时间复杂度：$\Theta(n)$

对于渐进下界：

​ 遍历需要访问 $BST$ 的全部节点。所以有：

$$T(n)=\Omega(n)$$

接下来证明渐进上界：

​ 对于一棵空树，调用遍历函数需要一个极小的常数时间。所以设$T(0)=c$，$c$为常数​

​ 对于一棵节点数$n>0$ 的树，设左子树节点数 $k>0$ ，右子树节点数为 $n-k-1$ ，额外开销为$d$，则递归不等式为：

$$T(n)\le T(k)+T(n-k-1)+d，d为常数$$

​ 我们不妨假设 $\exists{\ c\ \forall\ R}$ ，当 $c$ 很大时，有：$T(n)\le cn$

​ 则上式可化为：

$$T(n) \le ck+c(n-k-1)+d=cn-(c-d)$$

​ 当 $c-d\le 0$ 时，有 $T(n)=O(n)$​ 。

综上所述，==$T(n)=\Theta (n)$==​​​

• 空间复杂度：$O(n)$

​ 在最差情况下，即树退化为链表时，递归深度达到 $n$ ，系统占用 $O(n)$​ 栈帧空间。

广度优先遍历 Breadth-first traversal

• 「层序遍历 level-order traversal」

​ 从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

代码实现

​ 广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

/* 层序遍历 */
vector<int> levelOrder(TreeNode *root) {
    // 初始化队列，加入根节点
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一个列表，用于保存遍历序列
    vector<int> vec;
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 队列出队
        vec.push_back(node->val); // 保存节点值
        if (node->left != nullptr)
            queue.push(node->left); // 左子节点入队
        if (node->right != nullptr)
            queue.push(node->right); // 右子节点入队
    }
    return vec;
}

复杂度分析

• 时间复杂度：$\Theta (n)$​

​ 所有节点被访问一次，使用 $\Theta (n)$ 时间，其中 $n$ 为节点数量。

• 空间复杂度：$O(n)$​

​ 在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 $(n+1)/2$ 个节点，占用 $O(n)$ 空间。

二叉搜索树的查找

​ 给定目标节点值 num ，可以根据二叉搜索树的性质来查找。如图 7-17 所示，我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

• 若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。
• 若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。
• 若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点。

代码实现

/* 查找节点 */
TreeNode *search(int num) {
    TreeNode *cur = root;
    // 循环查找，越过叶节点后跳出
    while (cur != nullptr && cur->val != num) {
        // 目标节点在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 目标节点在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 返回目标节点
    return cur;
}

最大关键字元素和最小关键字元素

/* 最小关键字-迭代 */
TreeNode *Minimun(TreeNode *x){
 while(x->left != nullptr)
        x = x->left;
    return x;
}

/* 最小关键字-递归 */
TreeNode *Minimun(TreeNode *x){
    if(x->left != nullptr)
        return Minimun(x->left);
    else
        return x;
}

/* 最大关键字 */
TreeNode *Maximun(TreeNode *x){
 while(x != nullptr)
        x = x->right;
    return x;
}

/* 最大关键字-递归 */
TreeNode *Maximun(TreeNode *x){
    if(x->right != nullptr)
        return Minimun(x->right);
    else
        return x;
}

后继和前驱

TREE-SUCCESSOR(x)
 if x.right ≠ NIL 
  return TREE-MINIMUM(x.right) 
 y = x.p 
 while y ≠ NIL and x == y.right 
  x = y 
  y = y.p 
 return y

/* c++版后继 */
TreeNode *Successor(TreeNode *x){
    //如果结点x的右子树非空，那么x的后继恰是x右子树中的最左结点
    if(x->right != nullptr)
        return Minimun(x->right);
    TreeNode *y=x->prev;
    //如果x的右子树为空并有一个后继，那么向上回溯直到**x节点**是其父节点的左孩子
    while(y != nullptr && x->val == y->right->val){
        x = y;
        y = y->prev;
    }
    return y;
}

/* c++版前驱 */
TreeNode *Predecessor(TreeNode *x){
    //如果结点x的左子树非空，那么x的前驱恰是x左子树中的最右结点
    if(x->left != nullptr)
        return Maximun(x->left);
    TreeNode *y=x->prev;
    //如果x的左子树为空并有一个前驱，那么向上回溯直到**x节点**是其父节点的右孩子
    while(y != nullptr && x->val == y->left->val){
        x = y;
        y = y->prev;
    }
    return y;
}

二叉搜索树的插入

​ 给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作流程如下所示：

1. 查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。
2. 在该位置插入节点：初始化节点 num ，将该节点置于 None 的位置。

代码实现

/* 伪代码 */
TREE-INSERT(T,z) 
 y = NIL
 x = T.root 
 while x ≠ NIL 
  y = x 
  if z.key < x.key 
   x = x.left
  else 
   x = x. right 
 z.p = y 
 if y == NIL 
  T. root= z   // tree T was empty 
 elseif z.key < y.key 
  y.left= z 
 else y.right = z

/* 插入节点-迭代版 */
void insert(int num) {
    // 若树为空，则初始化根节点
    if (root == nullptr) {
        root = new TreeNode(num);
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    // 循环查找，越过叶节点后跳出
    while (cur != nullptr) {
        // 找到重复节点，直接返回
        if (cur->val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 插入位置在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 插入节点
    TreeNode *node = new TreeNode(num);
    if (pre->val < num)
        pre->right = node;
    else
        pre->left = node;
}

/* 插入节点-递归版 */
void insert(TreeNode* &cur, int num) {
    // 如果当前节点为空，则创建新节点并返回
    if (cur == nullptr) {
        cur = new TreeNode(num);
        return;
    }
    // 如果值已存在，则直接返回
    if (cur->val == num)
        return;
    // 如果要插入的值比当前节点的值大，则插入到右子树中
    if (cur->val < num)
        insert(cur->right, num);
    // 如果要插入的值比当前节点的值小，则插入到左子树中
    else
        insert(cur->left, num);
}

复杂度分析

• 时间复杂度：$O(log\ n)$ ，n为节点数
• 空间复杂度：$O(1)$

二叉搜索树的删除

​ 先在二叉树中查找到目标节点，再将其删除。与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的“左子树 < 根节点 < 右子树”的性质仍然满足。

​ 因此，我们根据目标节点的子节点数量，分 0、1 和 2 三种情况，执行对应的删除节点操作。

• 若 $z$ 有0个子节点，则简单地将 $z$ 删除，并修改 $z$ 的父节点，用 $NIL$​ 作为孩子来替换 $z$ 。

• 若 $z$ 有1个子节点，则将这个子节点提升到 $z$ 的位置，并修改 $z$ 的父节点，用 $z$ 的孩子来替换 $z$ 。（图a、b）

• 若 $z$ 有2个子节点，找 $z$ 的后继 $y$ ，然后 $y$ 的右孩子（若有）取代 $y$ 的位置，最后用 $y$ 取代 $z$ 。 （图c、d）

代码实现

/* 将以u为根的子树用以v为根的子树代替 */
TRANSPLANT(T,u,v)
 /*若u为根节点*/
 if u.p == NIL
   T.root=v
  /*若u是其父节点的左孩子*/
 else if u == u.p.left
  u.p.left = v
 /*若u是其父节点的右孩子*/
 else
  u.p.right = v
 if v ≠ NIL
  v.p=u.p

/* 删除结点z */
TREE-DELETE(T,z)
 /* 若z没有左孩子-图a */
 if z.left == NIL
  TRANSPLANT(T,z,z.right) /* 以z的右子树代替z */
 /* 若z没有右孩子-图b */
 else if z.right == NIL
  TRANSPLANT(T,z,z.left) /* 以z的左子树代替z */
 /* z有两个孩子 */
 else
  y = TREE-MINIMUM(z.right) /* y为z的后继，y必然没有左节点 */
  /* 若y不是z的孩子-图d */
  if y.p ≠ z
   TRANSPLANT(T,y,y.right) /* 将y的位置替换为y的右子树 */
   y.right = z.right /* 将y的右子树设置为z的右子树 */
   y.right.p = y /* 将y的右子树的父节点设置为y */
  /* 若y是z的右孩子-图c 以及图d的后续 */
  TRANSPLANT(T,z,y) /* 用y替换z */
  y.left = z.left 
  y.left.p = y

/* 删除节点 */
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 or 1 时， child = nullptr or 该子节点
        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;
    }
}

复杂度分析

• 时间复杂度：$O(log\ n)$ ，n为节点数
• 空间复杂度：$O(1)$​

*随机构建二叉搜索树 Randomly built binary search trees

​ 定义 $n$​ 个关键字的一棵随机构建二叉搜索树为按随机次序插入这些关键字到一棵初始的空树中而生成的树，这里输入关键字的 $n!$ 个排列中的每个都是等可能地出现。那么对于这棵树的期望高度，则有如下定理：

• 定理 一棵有 $n$ 个不同关键字的随机构建二叉搜索树的期望高度为 ==$O(log\ n)$== 。
• 证明如下：

​ 我们先定义如下三个随机变量：

​ 1. $X_{n}$ 为一棵有 $n$ 个不同关键字的随机构建二叉搜索树的高度。

​ 2. $Y_{n}=2^{X_{n}}$ 为指数高度，定义 $Y_{0}=0$ 和 $Y_{1}=2^{0}=1$ 。

​ 3. $R_{n}$ 为一个随机变量，选择一个关键字作为树根，其为这个关键字在 $n$ 个关键字集合中的秩（$rank$），表示这个关键字在排好序后应占据的位置。$R_{n}$ 的值对于集合 $\{1, 2,...,n\}$ 中的任何元素都是等可能的。

​ 若 $R_{n}=i$ ，那么根的左子树是一棵有 $i-1$ 个关键字的随机构建二叉搜索树，并且右子树是一棵有 $n-i$ 个关键字的随机构建搜二叉索树。

​ 因为二叉树的高度为：

$$X_{n} =max(leftSubtree.height,rightSubtree.height)+1$$

​ 所以有：

$$Y_{n}=2\cdot max(Y_{i-1},Y_{n-i})$$

​ 接下来，我们定义指示器随机变量（$chapter\ 5.2$）$Z_{n,1}$ ，$Z_{n,2}$ ，$...$ ，$Z_{n,n}$ ，其中：

$$Z_{n,i}=I\{R_{n}=i\}=\begin{cases} \ 1 &n=i\\ \ 0 &n\ne i \end{cases} \qquad ①$$

​ 又因为 $R_{n}=i$ 对于集合中每一个元素取值的概率是相同的，所以：

$$P\{R_{n}=i\}=\frac{1}{n}\ ,(i=1,2,...,n) \qquad ②$$

​ 结合 $①\ ②$ ，得到：

$$E[Z_{n,i}]=1 \cdot P\{R_{n}=i\}=\frac{1}{n} \ ,(i=1,2,...,n) \quad ③$$

​ 由于 $Z_{n,i}$ 恰有一个值为 $1$ ，其余所有值为 $0$ ，因此：

$$Y_{n}=\sum_{i=1}^{n}{Z_{n,i}(2\cdot max(Y_{i-1},Y_{n-i}))}$$

​ 由于 $Z_{n,i}$ 独立于 $Y_{i-1},Y_{n-i}$ 的值，上式两边取期望，得：

$$\begin{align*} E[Y_{n}] &= E\left[\sum_{i=1}^{n}{Z_{n,i}(2 \cdot \max(Y_{i-1},Y_{n-i}))}\right] \\ &=\sum_{i=1}^{n}E[{Z_{n,i}}(2 \cdot \max(Y_{i-1},Y_{n-i}))] &(期望的线性性质)\\ &=\sum_{i=1}^{n}E[{Z_{n,i}}]\cdot E[2 \cdot \max(Y_{i-1},Y_{n-i})] &(独立性)\\ &=\sum_{i=1}^{n}\frac{1}{n}\cdot E[2 \cdot \max(Y_{i-1},Y_{n-i})] &(③式)\\ &=\frac{2}{n}\sum_{i=1}^{n}E[\max(Y_{i-1},Y_{n-i})] &(期望的线性性质)\\ &\le\frac{2}{n}\sum_{i=1}^{n}(E[Y_{i-1}]+E[Y_{n-i}]) &(补充证明1)\\ \end{align*}$$

​ 因为 $E[Y_{0}]$ ，$E[Y_{1}]$，$...$ ，$E[Y_{n-1}]$ 每一项各出现两次，一次作为 $E[Y_{i-1}]$ ，另一次为 $E[Y_{n-1}]$ 。

​ 所以上述公式可化为：

$$E[Y_{n}] \le\frac{4}{n}\sum_{i=0}^{n-1}E[Y_{i}]$$

​ 使用替换法，证明 $E[Y(n)]=O(n^3)$ ：

$$\begin{align*} \frac{4}{n}\sum_{i=0}^{n-1}E[Y_{i}] &\le \frac{4}{n}\sum_{i=0}^{n-1}cn^3\\ &\le \frac{4}{n} \cdot \frac{cn^4}{4}=cn^3 \end{align*}$$

​ 所以，$E[Y(n)]=O(n^3)$ ，即$E[2^{X(n)}]=O(n^3)$。

​ 由 $Jensen$ 不等式（补充证明2）：

$$2^{E[X(n)]}\le E[2^{X(n)}]=O(n^3)$$

​ 两边取对数：

$$E[X(n)]=O(lgn)$$

​ 综上所述，一棵有 $n$ 个不同关键字的随机构建二叉搜索树的期望高度为 ==$O(log\ n)$​== 。

补充证明1：

要证明 $E[\max(X,Y)] \leq E[X] + E[Y]$，我们可以考虑分两种情况：

1. 当 $X \leq Y$ 时，有 $\max(X,Y) = Y$。
2. 当 $X > Y$ 时，有 $\max(X,Y) = X$。

因此，我们可以写出以下不等式：

$$\begin{align*} E[\max(X,Y)] &= E[\max(X,Y) \mid X \leq Y] \cdot P(X \leq Y) + E[\max(X,Y) \mid X > Y] \cdot P(X > Y) \\ &\leq E[Y] \cdot P(X \leq Y) + E[X] \cdot P(X > Y) \\ &= E[Y \cdot \mathbb{1}_{X \leq Y}] + E[X \cdot \mathbb{1}_{X > Y}] \end{align*}$$

其中，$\mathbb{1}_{X \leq Y}$ 和 $\mathbb{1}_{X > Y}$ 是指示函数。现在，因为指示函数的期望是概率本身，所以我们有：

$$E[Y \cdot \mathbb{1}_{X \leq Y}] = P(X \leq Y) \cdot E[Y] \leq P(X \leq Y) \cdot E[X] + P(X \leq Y) \cdot E[Y] \\ E[X \cdot \mathbb{1}_{X > Y}] = P(X > Y) \cdot E[X] \leq P(X > Y) \cdot E[X] + P(X > Y) \cdot E[Y]$$

将上述两个不等式代入前面的不等式中，我们得到：

$$E[\max(X,Y)] \leq E[Y] \cdot P(X \leq Y) + E[X] \cdot P(X > Y) \leq E[X] + E[Y]$$

因此，$E[\max(X,Y)] \leq E[X] + E[Y]$​​，证毕。

补充证明2：

假设 $f$ 是一个 $convex$ 函数（国外是凸函数，国内是凹函数）。我们想要证明对于任意随机变量 $X$ 和权重 $w_i$，满足 $\sum_{i} w_i = 1$，有：

$$E[f(X)] \geq f(E[X])$$

为了证明这一点，我们首先需要定义 $convex$ 函数的性质。一个函数 $f$ 被称为 $convex$ 函数，如果对于任意 $x_1, x_2$ 和 $0 \leq \lambda \leq 1$，都有：

$$f(\lambda x_1 + (1 - \lambda) x_2) \leq \lambda f(x_1) + (1 - \lambda) f(x_2)$$

现在，我们来证明 Jensen 不等式：

根据 $convex$ 函数的定义，我们有：

$$f(\lambda E[X] + (1 - \lambda) E[X]) \leq \lambda f(E[X]) + (1 - \lambda) f(E[X])$$

$$\Rightarrow f(E[X]) \leq \lambda f(E[X]) + (1 - \lambda) f(E[X])$$

$$\Rightarrow f(E[X]) \leq f(E[X])$$

这是显然成立的。因此，我们得出：

$$E[f(X)] \geq f(E[X])$$

这就证明了 Jensen 不等式。

:sweat_smile: 红黑树 Red-Black Tree :fearful:

🥵Q宝速速给我抄抄😋

红黑树的性质

1. 每个节点要么红，要么黑
2. 根节点永远为黑
3. 叶节点 $(NIL)$ 为黑
4. 不会有两个相连的红节点（一个节点是红的，那么俩子节点是黑的）
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点（即黑高 $bh(x)$ 相同）
6. (*)每一棵红黑树都对应着一棵 $2-3-4$ 树（或 $2-3$ 树）

• 其最明显的优势：一棵有 $n$ 个节点的红黑树的高度至多为 ==$2log( n+1)$==​ 。

证明如下：

​ 设 $x$ 为一棵红黑树的根节点，$bh(x)$​ 为一棵红黑树某个节点的黑高（即一条简单路径上黑色节点的个数），$h$ 为一棵红黑树的高度。

​ 我们先证明以 $x$ 为根的子树中至少包含 $2^{bh(x)}-1$ 个内部节点

​ 要证明此点，我们以数学归纳法进行证明：

​ 1. 当 $x.depth=0$ ，即 $x$ 为根节点，此时子树中的节点满足 $2^{bh(x)}-1=2^{0}-1=0$​ 。

​ 2. 当 $x.depth=k$ ，假设该命题成立，即以 $x$ 为根的子树中至少包含 $2^{bh(x_{k})}-1$ 个内部节点，此时的黑高为 $bh(x_{k})$ 或 $bh(x_{k})-1$ ，这取决于 $x.color$ 是黑还是红。

​ **3.**则当 $x.depth=k+1$ ，即 $x$​ 下一节点时，因为同一节点左右子树的黑高一致，所以有：

$$bh(x_{k+1})=bh(x_{k})-1$$

​ 此时 $x.depth=k$ 的左右子树节点数至少为：$2^{bh(x_{k+1})}-1=2^{bh(x_{k})-1}-1$ 。

​ 所以内部总节点数至少为：$(2^{bh(x_{k})-1}-1)+(2^{bh(x_{k})-1}-1)+1=2^{bh(x_{k})}-1$ 。

​ （这里只加一次 $1$ 是因为考虑到了左右子树可能存在 $NIL$ ）

​ 综上所述，以 $x$ 为根的子树中至少包含 ==$2^{bh(x)}-1$== 个内部节点。

​ 又因为根节点到叶节点至少有一半是黑节点，所以黑高至少为 $\left\lceil h/2\right\rceil$ ，于是有：

$$n \ge 2^{\left\lceil h/2\right\rceil}-1$$

​ 两边取对：

$$log(n+1) \ge \left\lceil h/2\right\rceil$$

​ 即：

$$h\le 2log(n+1)$$

红黑树的旋转

在 $CS61B$​ 上，旋转的正式定义为：

• rotateLeft(G) : Let x be the right child of G. Make G the new left child of x.
  • 左旋：设 $x$ 为 $G$ 的右子结点，让 $G$ 成为 $x$ 的新左子结点。
• rotateRight(G): Let x be the left child of G. Make G the new right child of x.
  • 右旋：设 $x$ 为 $G$ 的左子结点，让 $G$ 成为 $x$ 的新右子结点。

上面发生的事情的书面描述是这样的：

• $G$ 的右子项 $P$ 与 $G$ 合并，并带来了它的孩子。
• 然后 $P$ 将其左子项传递给 $G$，$G$ 向左下降成为 $P$ 的左子项。

可以看到树的结构及其高度发生了变化。我们也可以在非根节点上轮换。我们只是暂时断开节点与父节点的连接，旋转节点上的子树，然后重新连接新的根。

代码实现

/* 伪代码-左旋 */
LEIT-ROTATE(T,x) 
 y = x.right 
 x.right = y.left 
 if y.left ≠ T.nil
  y.left.p = x
 y.p = x.p 
 if x.p == T.nil /* 根节点 */
  T.root=y 
 else if x == x.p.left 
  x.p.left = y 
 else x.p.right = y 
 y.left= x 
 X.p = y

/* cs61b-java版 *//* 建议结合图来分析代码 */
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
    // assert (h != null) && isRed(h.right);
    Node x = h.right;     //将x设为h的右节点
    h.right = x.left;     //将h的右节点设为x的左节点(即h.left.right)
    x.left = h;           //将x的左节点设为h
    return x;             //返回旋转后的根节点
}

private Node rotateRight(Node h) {
    // assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    return x;
}

/* c++版 */
TreeNode *rotateLeft(TreeNode *h){
    TreeNode *child = h->right;
    h->right = child->left;
    child->left = h;
    return x;
}

TreeNode *rotateRight(TreeNode *h){
    TreeNode *child = h->left;
    h->left = child->right;
    child->right = h;
    return x;
}

复杂度分析

• 时间复杂度：$O(1)$

• 空间复杂度：$O(1)$

红黑树的插入

插入操作与 $BST$​ 基本一致。只是将插入节点染成红色，接着调用 $RBT-Insert-Fixup$ 函数，修复红黑树的性质。

代码实现

RB-INSERT(T,z)
 y = T.nil
 x = T.root
 while x != T.nil 
  y = x 
  if z. key < x. key 
   x = x.left 
  else
   x = x.right 
 z.p = y
 if y == T.nil 
  T.root= z 
 elseif z.key < y.key 
  y.left = z 
 else
  y.right = z
 /* 以上是BST-Insert操作 */
 z.left = T.nil
 z.right = T.nil
 z.color = RED
 RB-INSERT-FIXUP(T,z)

$fixup$ 原理分析

接下来我们来分析一下 $Fixup$​ 的原理：

​ 执行 $Insert$ 操作后，针对 $RBT$ 的五个性质，我们不难发现：

​ 性质 $1$ 和性质 $3$ 以及性质 $5$ 依然成立

​ 可能被破坏的是

​ 性质 $2$ （根节点为黑色）

​ 性质 $4$ （不会有两个相连的红节点）

​ 并且这两个性质至多只有一条被破坏。

​ 因此我们从修复性质 $4$ 入手，确定循环终止条件，即 $z$ 的父节点是黑色时终止。

​ 接下来我们以 $z.p$ 是左孩子为例，右孩子的代码直接所有方向取反。

​ 此时，有如下 $3$​ 种情况：

​ $case1$：$z$ 的叔节点 $y$ 是红色的

​ 该情况在 $z$ 和 $z.p$ 都是红色时发生。因为 $z.p.p$ 是黑色的，所以我们把 $z.p$ 和 $y$ 染成黑色，把 $z.p.p$ 染成红色以保持性质 $5$ 。然后我们以 $z.p.p$ 作为新的 $z$ 节点来重复循环（即 $z$ 上移两个节点）。

​ $case2$：$z$ 的叔结点 $y$ 是黑色的且 $z$ 是一个右孩子（ $z$ 和其父节点方向相反）

​ $case3$：$z$ 的叔结点 $y$ 是黑色的且 $z$ 是一个左孩子（ $z$ 和其父节点方向一致）

​ 我们将情况 $2$ 和 $3$​ 合并在一起来看。

​ 对于情况 $2$ ，我们立即对 $z.p$ 执行一次左旋，将其转变为情况 $3$ 。

​ 对于情况 $3$ ，我们能肯定的是，$z.p.p$ 必定为黑色。为了修复性质，我们交换 $z.p$ 和$z.p.p$ 的颜色，并对 $z.p.p$ 执行一次右旋。此时，$z.p$ 的颜色是黑色，循环终止，修复成功。

$fixup$ 代码

RB-INSERT-FIXUP(T,z) 
 while z.p.color == RED 
  if z.p == z.p.p.left 
   y = z.p.p.right /* y是z的叔节点 */
   /* case1 */
   if y.color == RED 
    z.p.color = BLACK 
    y.color = BLACK 
    z.p.p.color = RED 
    z = z.p.p 
   else
    /* case2 */
    if z == z. p. right 
     z = z.p 
     LEFT-ROTATE(T,z)
    /* case3 */
    z.p.color = BLACK 
    z.p.p.color = RED 
    RIGHT-ROTATE(T,z.p.p)
  else(same as then clause with "right" and "left" exchanged)
   ......
 T.root.color= BLACK

复杂度分析

• 时间复杂度：$O(log\ n)$​
  • 树高为 $O(log\ n)$ ，则插入操作需要 $O(log\ n)$ 的时间
  • 调用 $Fixup$ 时，仅当情况 $1$ 发生时，$z$ 才会沿树上升两层，此时需要$O(log\ n)$ 的时间，其他情况都是 $O(1)$ 。
  • 因此是 $O(log\ n)$
• 空间复杂度：$O(1)$

红黑树的删除

删除操作跟 $BST$ 的删除操作类似，只是多了一个记录节点 $x$ 以及在最后添加了一个 $RBT-Delete-Fixup$ 的操作

代码实现

/* 参考BST的删除 */
/* 用以v为根的子树替换以u为根的子树 */
RB-TRANSPLANT(T, u, v) 
 if u.p == T.nil  /* 若u为根节点 */
  T.root=v 
 else if u == u.p.left  /* 若u是其父节点的左孩子 */
  u.p.left = v  
 else  /* 若u是其父节点的右孩子 */
  u.p.right = v 
 v.p = u.p

/* 参考BST的删除 */
/* attention:第9、13、24行传递的第三个参数与x相同，x只是引用作用，不参与实际删除操作，只是给后续的fixup操作提供参数 */
RB-DELETE(T, z) 
 y = z 
 y-original-color = y.color 
 /* 若z的左树为空 */
 if z.left == T.nil 
  x = z.right 
  RB-TRANSPLANT(T, z, z.right)  /* 用z的右孩子代替z */
 /* 若z的右树为空 */
 else if z.right == T.nil 
  x = z.left 
  RB-TRANSPLANT(T, z, z.left)   /* 用z的左孩子代替z */
 /* 若z有两个孩子 */
 else 
  y = TREE-MINIMUM(z.right)     /* y是z的后继 */
  y-original-color = y.color 
  x = y.right
  /* 若y是z的孩子 */
  if y.p == z 
   x.p = y
  /* 若y不是z的孩子 */
  else
   RB-TRANSPLANT(T, y, y.right)  /* 用y的右孩子代替y */
   y.right = z.right             /* 令z的右孩子 */
   y.right.p = y                 /* 成为y的右孩子 */
  RB-TRANSPLANT(T, z, y)        /* 用后继y代替z */
  y.left = z.left               /* 将z的左孩子给 */
  y.left.p = y                  /* (肯定)没有左孩子的y */
  y.color = z.color
 if y-original-color == BLACK      /* y是红的不用管 不会影响红黑树的性质 */
  RB-DELETE-FIXUP(T, x)

$fixup$ 原理分析

下面重点讲 $Fixup$ 的原理：

​ 记录节点 $x$ ，其为我们替换 $y$ 所需的节点。

​ 因为其引用的节点替换 $y$ 后可能会违反红黑树的性质，所以我们要对 $x$ 及其子树向上进行 $Fixup$ 操作。

​ 如果 $y$ 是黑色的话，会产生三个问题：

​ 1. 若 $y$ 是原先的根节点，而其一个红色的孩子代替了 $y$ ，则会违反==性质2==，即根节点不能为红色。

​ 2. 若 $x$ 和 $x.p$ 是红色的话，则违反了==性质4==，即两个红色节点不能相连。

​ **3.**若移动 $y$ 后导致之前包含 $y$ 的简单路径的 $bh(x)$ 少了 $1$ ，则 $y$ 的任何祖先都不满足性质5，即 $bh(x)$ 相等。

​ 解决这一问题的方法就是将现在占有 $y$ 原先位置的 $x$ 视作还有额外一层黑色，即黑黑色或红黑色。

​ （但 $x.color$​ 不变，只是视作有两种颜色，这里则变为违反==性质1==，但是后面会进行修复）

​ 所以问题转变为 $Fixup$ 操作需要修复性质 $1、2、4$ 。

​ $while$ 循环的目标就是要把额外的黑色沿树上移，直到：

​ 1. $x$​​ 指向红黑节点，此时将其染成单个黑色

​ 2. $x$ 指向根节点，此时可以简单地"移除"额外的黑色

​ 3. 执行适当的旋转及重新染色，退出循环

​ 在循环里， $x$ 是黑黑色的~~（如果是红黑色，那就直接染成黑色了，瞎进什么循环）~~，下面设 $x$ 是其父节点左孩子， $w$ 是 $x$ 的兄弟节点。

则会有如下几种情况：

​ $case1$：$x$ 的兄弟节点 $w$ 是红色的 兄弟兄弟，你怎么是红色的(疾旋鼬.jpg)

​ 因为 $w$ 是红色，其必有俩黑色子节点，所以可以改变 $w$ 以及 $w.p$ 的颜色，并做一次旋转。

​ 这样就将 $case1$ 转换为接下来的三种情况处理。

​ $case2$：$x$ 的兄弟节点 $w$ 是黑色的且 $w$​ 的两个孩子都是黑色

​ 因为 $w$ 是黑色的，所以从 $x$ 和 $w$ 上各去掉一层黑色，即 $w$ 变为红色，$x$ 上移。为补偿删掉的一层黑色，将新的 $x$ 加一层黑色，继续循环，直到满足条件。

​ 若从 $case1$ 过来的，此时新的 $x$ 是红黑色的，满足条件，直接将新的 $x$​ 染成黑色，结束循环，修复完成。

​ $case3$：$x$ 的兄弟节点 $w$ 是黑色的且 $w$​ 的右节点是黑色，左节点是红色

​ 此情况需要转换为 $case4$ 来解决，所以我们先交换 $w$ 和 $w.left$ 的颜色，然后对 $w$ 进行右旋。

​ $case4$：$x$ 的兄弟节点 $w$ 是黑色的且 $w$ 的右节点是红色

​ 此情况下，将 $w.right$ 变为黑色，$x.p$ 与 $w$ 交换颜色，并对 $x.p$ 进行一次左旋，消除 $x$ 的额外黑色，最后将 $x$ 设为根节点，跳出循环。（ $x$ 的那一层黑色给到了原来 $w$​ 的右节点）

$fixup$ 代码

RB-DELETE-FIXUP(T, x) 
 while x != T. root and x.color == BLACK 
  if x == x.p.left 
   w = x.p.right 
   /* case1 */
   if w.color == RED 
    w.color = BLACK 
    x.p.color = RED 
    LEFT-ROTATE(T, x.p) 
    w = x.p.right 
   /* case2 */
   if w.left.color == BLACK and w.right.color == BLACK 
    w.color = RED 
    x = x.p
   else 
   /* case3 */
   if w.right.color == BLACK 
    w.left.color = BLACK 
    w.color = RED 
    RIGHT-ROTATE(T,w) 
    w = x.p.right
   /* case4- */
   w.color = x.p.color 
   x.p.color = BLACK 
   w.right.color = BLACK 
   LEFT-ROTATE(T, x.p) 
   x = T.root 
  else (same as then clause with "right" and "left" exchanged) 
   ......
 x.color = BLACK

复杂度分析

• 时间复杂度：$O(log\ n)$ ​

  • 不调用 $Fixup$ 时需要 $O(log\ n)$ ，因为树高是 $O(log\ n)$
  • 而调用$Fixup$ ，$case1、3、4$ 进行常数次数操作，$case2$ 至多循环到根节点，也即树高 $O(log\ n)$ ​
  • 因此是 $O(log\ n)$

• 空间复杂度：$O(1)$

B树 B-tree

未完工喵~:yum:

$shmm$ 速速🤺