一、题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如，输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6]，则重建如下图所示的二叉树并输出它的头结点：

二、解析

根据前序、中序遍历的特性和上面的图形能得到的结论：

• 前序遍历的第一个元素就是树的根节点。
• 根节点左边的元素就是左子树，根右边的就是右子树。

图片描述：

基于这两个特性就可以通过以下方式来构建出一颗二叉树：从前序遍历中确认根节点，再到中序遍历中找到定位到这个根节点，这样就可以拿到对应的左子树和右子树了。然后再按照相同的方式分别得到左右子树的子树，那么整个二叉树就可以构建起来了。

三、代码实现

二叉树节点定义：

template<typename T>
class tree_node {
    friend class bin_tree<T>;
    tree_node(const T &data) : data(data), lchild(nullptr), rchild(nullptr) {}
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
}

二叉树定义：

class bin_tree {
public:
    bin_tree() : root(nullptr) {}
    tree_node<T> *root;
};

在二叉树类中实现通过前序遍历和中序遍历构造二叉树的函数：

/*
 * 根据前序和中序遍历序列构造一个二叉树
 * @pre_order 前序遍历序列
 * @in_order 中序遍历序列
 * @len 序列长度
 */
void construct(const T pre_order[], const T in_order[], const unsigned int len) {
    if (len < 1)
        return;

    this->root = construct_core(pre_order, pre_order + len - 1, 
            in_order, in_order + len - 1);
}

/*
 * 通过前序遍列和中序遍历的结果构建二叉树
 * 前序遍历序列[pre_order_start, pre_order_end]，中序遍历序列[in_order_start, in_order_end]
 * @pre_order_start 前序遍历的开始位置
 * @pre_order_end 前序遍历的结束位置
 * @in_order_start 中序遍历的开始位置
 * @in_order_end 中序遍历的结束位置
 */
tree_node<T> *construct_core(const T *pre_order_start, const T *pre_order_end,
                             const T *in_order_start, const T *in_order_end) {
    // 遍历指针
    const T *cursor;
    // 前序遍历序列中左子树的结束位置
    const T *lchild_end;
    // 左子树的长度
    unsigned int lchild_len;
    // 根节点
    tree_node<T> *root = nullptr;;

    // 前序遍历的首元素即为树根
    root = new tree_node<T>(pre_order_start[0]);

    // 如果前序遍历的头和尾相等，说明只有一个元素了，返回当前元素
    if (pre_order_start == pre_order_end) {
        // 下面是简单的判断输入参数是否合法
        // 如果只有一个元素了，前序和中序的遍历结果是相同的
        if (in_order_start == in_order_end && *in_order_start == *pre_order_start)
            return root;
        else // 输入有问题
            throw "invalid input";
    }

    // 在中序遍历中找到根节点
    cursor = in_order_start;
    while (cursor < in_order_end && *cursor != root->data)
        cursor++;

    // 匹配到中序遍历的最后一个元素了还没有找到，说明输入不合法
    if (cursor == in_order_end && *cursor != root->data)
        throw "invalid input";

    lchild_len = cursor - in_order_start;
    lchild_end = pre_order_start + lchild_len;

    // 递归获取左子树
    if (lchild_len > 0) {
        root->lchild = construct_core(pre_order_start + 1, lchild_end,
                                      in_order_start, cursor - 1);
    }

    // 递归获取右子树
    if (lchild_len < pre_order_end - pre_order_start) {
        root->rchild = construct_core(lchild_end + 1, pre_order_end,
                                      cursor + 1, in_order_end);
    }

    return root;
}

四、单元测试

单元测试覆盖以下几点：

• 树为空
• 树只有一个节点
• 完全二叉树
• 满二叉树
• 不完全二叉树

4.1 树为空

/*
 * 测试：通过前序和中序遍历序列构造二叉树
 * 案例：二叉树为空
 */
TEST(construct_by_pre_order_and_in_order, no_node) {
    bin_tree<int> tree;
    tree.construct(nullptr, nullptr, 0);
    EXPECT_FALSE(tree.get_root());
}

4.2 树只有一个节点

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：二叉树包含一个节点
 */
TEST(construct_by_pre_order_and_in_order, one_node) {
    bin_tree<int> tree;
    int data[1] = {1};
    tree.construct(data, data, 1);
    EXPECT_TRUE(tree.get_root());
    EXPECT_FALSE(tree.get_root()->get_lchild());
    EXPECT_FALSE(tree.get_root()->get_rchild());
}

4.3 完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：完全二叉树测试
 *          1
 *        2   3
 *       4 5
 */
TEST(construct_by_pre_order_and_in_order, complete_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3};
    int in_order[7] = {4, 2, 5, 1, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
}

4.4 满二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：满二叉树测试
 *          1
 *        2   3
 *       4 5 6 7
 */
TEST(construct_by_pre_order_and_in_order, full_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3, 6, 7};
    int in_order[7] = {4, 2, 5, 1, 6, 3, 7};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 7);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    EXPECT_EQ(node->get_rchild()->get_data(), 7);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());
}

4.5 非完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：普通二叉树测试
 *          1
 *        2   3
 *         5 6
 */
TEST(construct_by_pre_order_and_in_order, normal_bin_tree) {
    int pre_order[7] = {1, 2, 5, 3, 6};
    int in_order[7] = {2, 5, 1, 6, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
    // 左子节点为6，右子节点为空
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
}

4.6 测试结果

一、梳排序简介

梳排序是冒泡排序的一种优化方案，主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据，先进行部分优化，然后逐步减少步长，以此来对数据进行预处理。

以数组[3,1 5, 2, 4]为例，假设步长是2，那么就分别处理[3, 5, 4]和[1, 2]，先局部优化。优化完成后，再使用冒泡排序。

关于步长的选取

步长并不是逐步递减的，步长的选取一般通过一个步长因子来控制：

1. 初始化时，步长等于数组长度除以步长因子。
2. 后续的所有步长都等于前一次步长除以步长因子，直到步长小于等于1。

从实验结果来看，这个步长因子设置为1.3时能获得较好的性能，并且实验数据证明，梳排序的良好性能甚至可以与快速排序媲美。

排序示例

以数组[41, 11, 18, 7, 16, 25, 4, 23, 32, 31, 22, 9, 1, 22, 3, 7, 31, 6, 10]为例，它的长度是19，计算得到的步长分别是[14, 10, 7, 5, 3, 2]，它的预处理过程可以整理为：

其中no表示第几趟排序，step表示步长，data是当前经过处理后的数组。很明显可以看出经过6次预处理后，数据已经基本有序了。

此时再通过冒泡排序来对整体排序就能减少很多工作量了（实际上只需要再做一次冒泡排序就能完成排序了）。如果没有第一阶段的处理，冒泡需要19趟排序才能完成，而经过处理后，第8趟排序就已经有序了。此时排序结束，节省了一半以上的时间。

二、代码

C++代码：

const float factor = 1.3;

template<typename T>
void comb_sort(T data[], const unsigned int n) {
    unsigned int i, j, step = n;
    bool flag = true;

    if (n < 2)
        return;
    
    // 步长处理
    while ((step = (unsigned int) (step / factor)) > 1) {
        for (i = n - 1; i >= step; i--) {
            j = i - step;
            if (data[i] < data[j])
                my_swap(data[i], data[j]);
        }
    }

    // 冒泡排序
    for (i = 0; flag && i < n - 1; i++) {
        flag = false;
        for (j = 1; j < n - i; j++) {
            if (data[j] < data[j - 1]) {
                my_swap(data[j], data[j - 1]);
                flag = true;
            }
        }
    }
}

一、单链表

链表是一种线性结构，通过前后节点指针连接起每个节点，从结构来看就像是用一个链把所有的节点都串起来了，因此被称为链表。

它和数组最大的不同就是不能随机访问，数组的内存空间是顺序的，通过计算位置偏差就能定位到元素。而链表的节点的地址是不连续的，它无法直接通过地址定位随机访问。但是数组在以下场景就没有链表方便了：

1. 开辟新空间：数组元素到达上限后，如需添加新元素，需要重新开辟一块更大的空间，然后把当前数组的数据拷贝过去再继续添加元素。
2. 删除元素：删除数组元素后，需要把被删除元素后面的元素都集体前移。
3. 移动元素：移动元素和删除类似，移动节点会导致部分节点数据迁移。

但是对于链表而言，都不存在以上问题。它不管是新增、删除甚至移动节点，都能在O(1)的时间完成。因此，在某些情况下，它更适合数组来使用。

二、单链表的操作

2.1 链表结构

链表都是由一个个节点组成的，从面向对象的特性上来说，链表和节点是两个不同的东西。每个节点至少都包含了一个数据字段和一个next节点指针，next指针指向的是下一个节点地址，而链表只需要保存一个首节点指针就行了。通过链表的首节点指针和每个节点的next指针，就可以循环遍历到节点的每一个元素了。

2.2 添加节点操作

添加节点的操作可通过下图演示：

可以分为两步来描述：

1. 设置新节点（B节点）的next指针为下一个节点（C节点）地址。
2. 把插入节点（A）节点的next指针指向新节点（B节点）。

这样就完成了一个节点的插入。

2.3 删除节点操作

删除节点的操作图示：

操作描述：

1. 找到删除节点的前置节点（A节点）。
2. 设置前置节点的next指针为删除节点的next指针指向。
3. 删除节点。

2.4 移动节点操作

移动节点的操作可以分解为删除和添加节点两步：

1. 把移动节点从链表中删除。
2. 把这个删除的节点重新插入到链表的指定位置。

三、代码描述（C++）

3.1 节点和链表定义

节点定义：

template<typename T>
class list_node {
public:
    friend class singly_linklist<T>;
    list_node() : next(nullptr) {}
    list_node(const T &data) : next(nullptr), data(data) {}
private:
    T data;
    list_node<T> *next;
};

节点的定义很简单，包含了一个T类型的数据域和next指针，其中比较特殊的是对singly_linklist类的友元定义，singly_linklist是后面要定义的链表类，通过设置友元可以方便链表类直接操作节点中的私有数据域，因为需要在链表中对节点进行新增、删除和移动等操作。

链表的定义如下：

template<typename T>
class singly_linklist {
public:
    singly_linklist() : len(0), head(nullptr), tail(nullptr) {}
private:
    size_t len;
    list_node<T> *head;
    list_node<T> *tail;
};

链表中包含了两个指针head和tail，head指针是上面说的链表首元素的地址，而tail指针则是链表尾元素指针，tail指针在单链表中实际上没有很大的用途，但是在后续的双向链表和双向循环链表中都会用到，单链表中可以用作冗余字段使用。

除了首位指针以外，还有一个表示链表长度的字段，这个字段也是作为冗余使用，实际项目中如果需要获取链表长度就可以在0(1)时间返回，避免了便利链表。链表长度的设置方法也很简单：每添加一个节点，长度加一；每删除一个节点，长度减一。

3.2 添加节点

插入链表节点的逻辑很简单，代码在网上一搜也是一大把，但很少有准确并简单的实现方式。

本文中的链表（包括后续的双向链表和循环链表）都参考了linux内核中的实现方式，力求简单、高效并且准确。

链表节点的插入有头插法和尾插法，头插法的意思是把节点插到链表头部，而尾插法的意思是把节点插到链表尾部。两者逻辑不同，但是共同点就是都要插入节点到链表中，只是插入的位置不同。因此对添加节点而言，有必要把插入节点逻辑抽离出来作为私有函数供其他插入函数调用。

定义一个私有的添加节点函数（c语言中通过static关键字完成，c++通过private关键字完成），传入参数包含三个：

• 待插入的节点new_node，因为是私有函数提供给类中的其他函数使用的，因此外部函数调用前要确保值不为空。
• 待插入节点的前置节点prev，值可能为空（插入节点到链表首部的时候）。
• 待插入节点的后置节点next，值可能为空（插入节点到链表尾部的时候）。

添加节点除了设置前后节点指针以外，还有一个难处理的地方就是首尾指针的赋值。

什么时机才应该重新赋值首尾指针？？？

更新首尾指针的地址的场景：

1. 空链表插入新节点。
2. 非空链表插入节点到链表首部或者尾部。
3. 删除首、尾节点（删除的场景在下面讨论）。

可以整理出来的一个规律是：

• 如果新插入节点的前置节点是空（此时插入节点到链表头），设置头指针为新插入的节点。
• 如果新插入节点的后置节点为空（此时插入节点到链表尾），设置尾指针为新插入的节点。

代码如下：

/*
 * 添加节点操作，新添加的节点需确保不是空值
 * @new_node 新节点
 * @prev 前驱节点，节点可能为空（插入到首部的时候）
 * @next 后继节点，节点可能为空（插入到尾部的时候）
 */
template <typename T>
void singly_linklist::add_node(list_node<T> *new_node, list_node<T> *prev, list_node<T> *next) {
    len++;
    new_node->next = next;

    if (prev) { // 如果前置节点不为空，修改前置节点的next指针
        prev->next = new_node;
    } else { // 前置节点为空，说明放在了链表头部，设置头节点的指针
        head = new_node;
    }

    if (next == nullptr) { // 后置节点为空，说明放在链表的尾部，设置尾节点的指针
        tail = new_node;
    }
}

实现了add_node函数后，再实现头插和尾插函数就简单了：

/*
 * 插入元素到末尾
 * @data 待插入数据
 */
template <typename T>
const singly_linklist<T> &singly_linklist::push_back(list_node<T> *node) {
    if (node == nullptr)
        return *this;

    // 添加节点到末尾，前置节点是尾节点，后置节点是空
    add_node(node, tail, nullptr);

    return *this;
}

/*
 * 插入数据到开头
 * @node 待插入的数据节点
 */
template <typename T>
const singly_linklist &singly_linklist::push_front(list_node<T> *node) {
    if (node == nullptr)
        return *this;

    // 添加节点到开头，前置节点是空，后置节点是头节点
    add_node(node, nullptr, head);
  
    return *this;
}

一个要注意的地方是两个函数的返回值都是const singly_linklist &，在函数结束后都返回*this，这么做的目的就是为了支持链式表达式。

3.3 删除节点

删除节点和添加节点一样，难处理的地方就是首尾指针的赋值（也就是上面添加节点时说到的需要处理但是还没有处理的的第3点）。

删除节点时处理首尾指针的规律和插入节点一致：

1. 如果删除节点的前置节点是空（删除的是头节点），设置头节点指针为删除节点的后置节点。
2. 如果删除节点的后置节点是空（删除的是尾节点），设置尾节点指针为删除节点的前置节点。

代码如下：

/*
 * 删除节点，待删除的节点请确保不是空值
 * @del_node 待删除节点
 * @prev 前驱节点
 * @next 后继节点
 */
template <typename T>
void singly_linklist::remove_node(list_node<T> *del_node, list_node<T> *prev, list_node<T> *next) {
    len--;
    del_node->next = nullptr;

    if (prev) { // 如果存在前置节点，更新前置节点的next指针
        prev->next = next;
    } else { // 不存在前置节点，删除的是头节点，更新头节点的指针
        head = next;
    }

    if (next == nullptr) { // 不存在后置节点，删除的是尾节点，更新尾节点指针
        tail = prev;
    }
}

对比remove_node和add_node的函数实现可以看到，函数开头都没有对新增节点或删除节点做合法校验。

不校验的意义在于两个都是内部函数，提供给内部其他函数使用的，其他函数在外层调用的时候已经判断参数合法性了，函数内已经确保不会为空。

在实现remove_node之后，需要再实现的一个功能是找到前置节点，因为删除节点要先找到前置节点才能调用。查找前置节点函数find_prev的操作为：

/*
 * 查找某个节点的前一个节点
 * @node 当前节点
 * @return 如果存在上一个节点，返回上一个节点的地址，否则返回nullptr
 */
template <typename T>
list_node<T> *singly_linklist::find_prev(list_node<T> *node) {
    list_node<T> *p = head;
    if (node == nullptr)
        return nullptr;
  
    // 遍历链表查找前置节点
    while (p != nullptr) {
        if (p->next == node) {
            return p;
        }
        p = p->next;
    }
    return p;
}

有了find_prev之后，对外的remove函数就可以实现了：

/*
 * 删除节点
 * @node 待删除节点
 */
template <typename T>
const singly_linklist &singly_linklist::remove(list_node<T> *node) {
    list_node<T> *prev;
    if (node == nullptr)
        return;

    // 找到前置节点
    prev = find_prev(node);

    // 删除节点
    remove_node(node, prev, node->next);

    delete node;
}

基于remove函数实现pop_front和pop_bak：

// 弹出首元素
template <typename T>
const singly_linklist &singly_linklist::pop_front() {
    remove(head);
}

// 弹出尾元素
template <typename T>
const singly_linklist &singly_linklist::pop_back() {
    remove(tail);
}

四、单元测试

测试头插法：

TEST(singly_linklist, push_front) {
    int i;
    singly_linklist<int> list;
    const list_node<int> *p;
    vector<int> v{1, 2, 3};

    list.push_front(3).push_front(2).push_front(1);
    EXPECT_EQ(3, list.get_len());

    p = list.get_head();
    for (i = 0; i < v.size(); i++) {
        EXPECT_EQ(p->get_data(), v[i]);
        p = p->get_next();
    }
    EXPECT_EQ(p, nullptr);
}

测试尾插法：

TEST(singly_linklist, push_back) {
    int i;
    singly_linklist<int> list;
    const list_node<int> *p;
    vector<int> v{1, 2, 3};

    list.push_back(1).push_back(2).push_back(3);
    EXPECT_EQ(3, list.get_len());

    p = list.get_head();
    for (i = 0; i < v.size(); i++) {
        EXPECT_EQ(p->get_data(), v[i]);
        p = p->get_next();
    }
    EXPECT_EQ(p, nullptr);
}

测试获取前置节点：

TEST(singly_linklist, get_prev) {
    int i;
    singly_linklist<int> list;
    const list_node<int> *p;
    list_node<int> *node1, *node2, *node3;

    // 插入3个节点
    node1 = new list_node<int>(1);
    node2 = new list_node<int>(2);
    node3 = new list_node<int>(3);
    list.push_back(node1).push_back(node2).push_back(node3);
    EXPECT_EQ(3, list.get_len());

    p = list.find_prev(node1);
    EXPECT_EQ(p, nullptr);
    p = list.find_prev(node2);
    EXPECT_EQ(p, node1);
    p = list.find_prev(node3);
    EXPECT_EQ(p, node2);

}

测试删除节点：

TEST(singly_linklist, remove) {
    int i;
    singly_linklist<int> list;
    const list_node<int> *p;
    list_node<int> *node1, *node2, *node3;

    node1 = new list_node<int>(1);
    node2 = new list_node<int>(2);
    node3 = new list_node<int>(3);

    list.push_front(node1);
    list.push_back(node2);
    list.push_back(node3);

    // 删除中间节点
    list.remove(node2);
    EXPECT_EQ(node1, list.get_head());
    EXPECT_EQ(node3, list.get_tail());
    EXPECT_EQ(node1->get_next(), node3);

    // 删除头节点
    list.remove(node1);
    EXPECT_EQ(node3, list.get_head());
    EXPECT_EQ(node3, list.get_tail());
    EXPECT_EQ(node3->get_next(), nullptr);

    // 删除尾节点
    list.remove(node3);
    EXPECT_EQ( list.get_head(), nullptr);
    EXPECT_EQ( list.get_tail(), nullptr);
}

测试结果：

一、行锁和两阶段锁协议

行锁：顾名思义，就是对某一行加锁，修改的时候不会锁住整个表。相对于表锁来说，行锁的开销更大（因为涉及到MVCC等需要保存快照），但是粒度更小，更适合于高并发场景。行锁是每个引擎单独实现的，但是并不是所有的引擎都实现了行锁。例如MyISAM就没有实现行锁，它只支持表锁，而InnoDB支持行锁，因此高并发场景基本都会选择InnoDB作为数据库引擎。

行锁是系统自动加上的，无需手动干预。当多个事务同时更新一行数据时，后来事务的更新操作会被阻塞，直到行锁被释放才能更新。而行锁并不是在事务一启动就加上了，而是在真正需要的时候才加锁，也就是说只有在更新的时候才对行加锁。这样做有两个好处：

1. 减小锁的粒度和加锁时长，提高并发度。
2. 事务启动的时候，并没有明确说明需要修改什么行，此时如果如果要锁定行必须锁定整个表才行。

和加锁时机不同，行锁不是在更新完行之后立马就解锁，而是在事务执行完成（执行了commit或者rollback）之后才解锁。这两个加锁的时机被称为两阶段锁协议。

例如以下表包含了学生信息：

# 创建表
CREATE TABLE stu_info  (
  `id` int(0) UNSIGNED NOT NULL AUTO_INCREMENT,
  `name` varchar(20) NOT NULL DEFAULT '',
  `age` tinyint(0) UNSIGNED NOT NULL DEFAULT 20,
  PRIMARY KEY (`id`)
) ENGINE = InnoDB CHARACTER SET = utf8;
# 插入三行数据
insert into stu_info(name, age) values('maqian', 24), ('zed', 10), ('yasuo', 15);

启动两个事务，同时修改id为2的学生的年龄，其中事务一先修改但不提交，事务二也修改同一行内容，事务二就会被阻塞。具体的执行流程为：

首先，第一个事务执行修改：

然后，第二个事务也执行修改：

此时事务二被阻塞，因此这一条记录已经被事务一锁定了，要等待事务一释放锁后才能修改。

一直到一段时间过去后事务二会弹出报错，意思时等待锁超时了：

ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

此时事务二虽然不能修改id为2的记录，但是可以修改其他id的记录：

这说明，两个事务都只是对各自修改的记录行加锁了，并没有对整个表加锁。两个事务执行完成后的表：

+----+--------+-----+
| id | name   | age |
+----+--------+-----+
|  1 | maqian |  24 |
|  2 | zed    |  16 |
|  3 | yasuo  |  18 |
+----+--------+-----+

行锁变表锁

当行锁涉及的索引失效时，会导致行锁变成表锁。例如上面的示例中修改条件都是id = 2，因为id是主键，默认会生成索引。因此两个事务更新记录时使用的是行锁，事务一锁住id = 2的行的时候，事务二还是能更新id = 3的行。

但是一旦把条件改成其他列，即where后面的条件改成其他（如where name 'zed'）时，行锁会升级成表锁。即使事务一只修改name = 'zed'的列，事务二也无法修改name = 'yasuo'这一列。

二、死锁

在事务中，多个事务间同时对不同的行加锁，可能会导致死锁。例如以下场景：

事务一先修改id = 3的用户的年龄并锁住该行，然后事务二修改id = 2的年龄也锁住这行。接着事务一修改id = 2的用户年龄，因为这一行已经被事务二锁住了，所以这条语句会被阻塞，要等到事务二释放锁才能继续。但是此时事务二想修改id = 3的用户的年龄，刚好这行又被事务一给锁住。两个事务互相都要等待对方先释放锁，产生了死锁。

这个场景比较类似《unix环境高级编程》中对死锁产生原因的描述：当多个线程以不当的顺序同时对多个锁加锁就会导致死锁。

死锁产生后，MySQL有两种方法来解决死锁：

1. 等待锁超时。如上面测试的一样，当更新语句等待锁一段时间后会超时退出，不会无休止等待下去。但是这个超时时间默认是50S，太长了，在高并发系统中是无法接受的。
2. 设置死锁检测。通过设置innodb_deadlock_detect = on，开启MySQL的死锁检测，系统会自动检测死锁的事务并回滚改动。

大部分时候使用的都是方式二，主动检测死锁来释放锁，因为方式一超时时间太长了。但是方式二也有缺点是检测时间是O($n^2$)。例如，有100个事务在执行的时候，每个事务执行的时候都要和另外99个线程检测是否存在死锁。此时需要执行10000次死锁检测，当事务的数量再上升的时候，死锁的检测又会上升一个量级。

如何解决这个问题呢？一般有以下几种办法：

1. 合理规划数据表的执行顺序，尽量避免多个事务以不同顺序更新同一个表。如果都是相同的顺序访问，是不会产生死锁的。这种情况下，可以关闭死锁检测。
2. 控制并发量，在代码中限制同时执行事务的数量，控制在10以内，超过的排队执行。这样就减少了死锁检测的次数，虽然有排队的事务，但是排队的时间远远小于多个事务之间的死锁检测时间。

数据结构之B树

一、B树的基本概念

B树是一种多叉树，被广泛应用于数据库索引中。它也是一种特殊的搜索树，和搜索树最大的不同在于它的每个节点都包含了n个关键字和n+1个指向子节点的指针。它的表现形式为：

B树的特点：

1. 假设x.key为当前节点中的关键字，x.child.key是子节点中的关键字，那么它们之间存在以下关系：
   x.child.key <= x.key1 <= x.child2.key <= x.key2 <= x.child3.key <= ... <= x.keyn
2. 每个节点的关键字个数都有上界和下界，上下界用B树的最小度数t ≥ 2来表示。
3. 除了根节点以外，每个节点必须有t - 1个关键字，除了根节点以外，每个节点都有t个孩子。
4. 每个节点最多有2t - 1个关键字，最多有2t个孩子。当一个节点恰好有2t - 1个关键字时，称该节点是满的。
5. t = 2的时候B树最简单，每个内部节点有2、3或者3个孩子，也被称作2-3-4树。
6. t值越大，B的高度就越小。

为什么B树广泛应用于索引中

因为磁盘读取的最小单位是扇区，每个扇区是512字节。操作系统读取磁盘的最小单位是块，一个块包含了若干个扇区（一般一个块是4096字节，包含8个扇区）。如果和红黑树或其他二叉搜索树一样，每个节点只保存一个数据，那么磁盘读取的效率就相当低了。如果需要读取多个数据，就要执行多次磁盘IO操作才能完成任务了，而磁盘IO在系统中属于较为耗时的操作，因此多次IO势必导致效率大大降低。

B树就是为了改进这一问题而衍生出来的，B树的节点一般设置为磁盘的块大小，也就是4K，里面包含了多个数据节点的内容，这样一次IO就能读到多个数据内容。并且由于B树也具有搜索树的性质，因此很快就能定位到数据内容。

二、B树操作

B树的主要操作有两个：分裂和合并。因为B树的每个节点包含关键字的数量为[t - 1, 2t - 1]，当节点的关键字数量超出后，就要对节点进行分裂操作，分裂操作会导致B树高度增加。当节点关键字被删除，数量不满足条件时就要合并两个节点，合并节点会导致B树高度下降。

3.1 增加节点

以一个度为4的B树为例，插入S后，B树节点的关键字数量变成了7，需要进行分裂。

此时对节点的分裂过程为：

1. 新生成节点，将S右边的关键字和子节点移到新节点中。
2. S左边的关键字和子节点保存在当前节点。
3. S节点往上提，放到父节点中的合适位置。
4. 如果S节点上提导致父节点的数量也超出了，还需要继续对父节点进行分裂。

注意：每次上提到父亲节点的关键字都是被分裂节点的中间关键字。

分裂示例

以下是度为3的B树分裂的过程，每个节点最多有5个关键字，最少2个关键字。

初始时的B树：

插入B，这只是一个简单的对叶节点插入的过程，插入后不会影响其他节点，B树的条件也还满足，直接插入就行：

插入Q，因为插入Q后会导致RSTUV节点关键字超出，因此要分裂这个节点。T节点作为中间节点放到父节点中（也可以把S提到父节点，T放在UV节点）：

插入L，它被放到JK节点之后，也是一个简单的叶节点插入。但是因为根节点的关键字满了，所以对根节点分裂，此时将P提出来作为根节点，树的高度加1：

插入F，放在ABCDE节点之后，插入后将导致节点分裂，节点C提到父节点：

2.3 删除节点

在B树中删除节点，将会引发节点的合并。相对于增加节点来说，删除节点的远比增加节点要复杂。

以上面的B树为例，初始状态为：

删除关键字F，作为叶子节点，删除F后并没有影响到B树的性质，直接删除即可。得到以下B树：

删除关键字M，因为M所处的节点是内部节点，删除M后会导致NO关键字所在的节点没有父节点。此时需要把M的前驱关键字L替换掉M，然后删掉L：

也可以把M的后继关键字N替换上来，但是M替换后会导致子节点不满足关键字数量条件。

删除关键字G，G所处的节点也是内部节点，删除后会导致DE或者JK所处的节点没有父节点，此时也需要和上面删除M一样在子节点中找到前驱或者后继替换上来。但是这里不同的是，两个子节点都是只有t - 1个关键字，再从中拿掉一个关键字后会导致子节点关键字数量不满足。此时就需要合并两个子节点，然后直接删除G节点：

删除关键字D，D所处的节点是叶子节点，可以和删除节点F一样，直接删除。但是这里也有一个不同的点是，父节点和父节点的兄弟节点此时都只有t - 1个节点，此时除了删除节点D以外，还要合并父亲节点，此时树的高度减一：

删除关键字B，B所在的节点关键字数量是t - 1，删除B后会导致节点的最小关键字数量不满足条件。因此要从父节点或者兄弟节点借一个关键字。此时就分为两种情况：

1. 如果兄弟节点的关键字个数也是t - 1，那么直接和兄弟节点合并，从父节点提取一个关键字下来（下面删除C时候的场景）。
2. 如果兄弟节点的关键字个数大于t - 1（目前就是这个情况，兄弟节点有3个关键字），此时就从父节点借一个关键字C替换掉B，借掉C后，就相当于删除了一个内置节点的元素，所以父亲节点要从它后继节点中找一个关键字补上，也就是E。最终的结果就是用C覆盖B，再用E覆盖原来C的位置，再删除E。

删除节点C，此时的情况就是上面的第一种情况了，兄弟节点的关键字个数是t - 1，要合并两个节点，得到：

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/add-two-numbers

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字0之外，这两个数都不会以0开头。

示例：

• 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
• 输出：7 -> 0 -> 8
• 原因：342 + 465 = 807

二、题解

思路：

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。：

算法：

就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表l1和l2的表头开始相加。由于每位数字都应当处[0, 9]的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为2，并将进位carry = 1带入下一次迭代。进位carry必定是0或1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。

伪代码如下：

• 将当前结点初始化为返回列表的哑结点。
• 将进位carry初始化为 00。
• 将p和q分别初始化为列表l1和l2的头部。

• 遍历列表l1和l2直至到达它们的尾端。

  • 将x设为结点p的值。如果p已经到达l1的末尾，则将其值设置为0。
  • 将 y设为结点q的值。如果q已经到达 l2l2 的末尾，则将其值设置为0。
  • 设定sum = x + y + carry。
  • 更新进位的值，carry = sum / 10。
  • 创建一个数值为 (sum % 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
  • 同时，将 pp 和 qq 前进到下一个结点。
• 检查carry = 1是否成立，如果成立，则向返回列表追加一个含有数字 11 的新结点。
• 返回哑结点的下一个结点。

请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。

特别注意以下情况：

1. 当一个列表比另一个列表长时
2. 当一个列表为空时，即出现空列表
3. 求和运算最后可能出现额外的进位，这一点很容易被遗忘

三、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *rs, *p, *q, *cur;
        int carry = 0, sum, x, y;

        rs = new ListNode(0);
        cur = rs;

        p = l1;
        q = l2;

        // [1] 注意循环终止的条件是两个链表都不为空了才停止
        while (p || q) {
            // [2] 注意p或者q等于NULL的清情况
            x = p ? p->val : 0;
            y = q ? q->val : 0;

            // [3] 注意加上进位
            sum = x + y + carry;

            cur->next = new ListNode(sum % 10);
            carry = sum / 10;

            // [4] 注意处理p或q节点等于NULL的情况
            p = p ? p->next : NULL;
            q = q ? q->next : NULL;
            cur = cur->next;
        }

        // [5] 注意最后的进位
        if (carry) {
            cur->next = new ListNode(carry);
        }
        
        // [6] 返回rs的下一个节点
        return rs->next;
    }
};

复杂度分析：

• 时间复杂度：O(max(m,n))，假设m和n分别表示l1和 l2的长度，上面的算法最多重复max(m,n)次。
• 空间复杂度：O(max(m,n))， 新列表的长度最多为max(m,n)+1。

来源：力扣（LeetCode）

链接：234. 回文链表

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

请判断一个链表是否为回文链表。

示例 1：

输入：1->2
输出：false

示例 2：

输入：1->2->2->1
输出：true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

二、题解

2.1 暴力法

算法：

1. 遍历链表并复制一份
2. 同时把复制出来的链表反转
3. 使用2个指针分别遍历两个链表对比每个节点

算法复杂度：

• 时间复杂度：O(n)，需要遍历两次链表。
• 空间复杂度：O(n)，需要拷贝一份链表。

2.2 快慢指针

判断是否回文数核心思想是先找到链表的中间节点，然后从中间节点开始往两边对比、或者从两边往中间节点对比，以此判断是否为回文数。

算法：

使用2个指针，快指针每次走一步，慢指针每次走两步。当快指针到链表末尾的时候，慢指针在链表中间。这个时候反转后半部分链表，再使用两个指针从链表两端朝中间遍历即可判断出是不是回文。

图示：

当快指针走到末尾的时候，慢指针刚好走到一半，中间节点就在p1和p1前一个节点之间：

以下是节点个数为奇数时，快慢指针从开始到结束时候的状态，中间节点是p1的前一个节点：

可以看到不管链表个数是奇数还是偶数，中间节点都是在慢指针p1附近。

优化

上面的快慢指针算法的执行步骤：

1. 快指针遍历到末尾（遍历了一半的链表）。
2. 反转慢指针到快指针这一段（遍历了一半的链表）。
3. 从两端往中间遍历（遍历了一半的链表）。

整个时间复杂度是O(n)，虽然是O(n)，但是实际上链表遍历了1.5次。因为要对比整个链表，所以算法的时间复杂度不可能低于O(n)，O(n)最理想的情况就是只遍历一次，因此可以想办法优化掉多余的0.5次遍历。

算法如下：

1. 快慢指针分别遍历链表，遍历的过程中，把慢指针经过的节点反转。
2. 当快指针走到链表末尾的时候，慢指针依旧在链表中间的位置，但是此时，慢指针前面的节点都已经反转了。
3. 分别从满指针前后朝两端遍历，对比每个节点。

该算法把前面的步骤1和2合并成了一个操作，减少了一次遍历操作（需要遍历一半链表节点），最后只要遍历1次链表即可完成判断链表是否回文。

算法要注意区分奇数个节点和偶数个节点。

当链表节点个数是偶数个的时候，快指针在指向NULL时，p1前面的就是链表的前半段，从p1开始就是后半段：

链表节点个数是奇数个的时候，p2不会走到NULL（p2要走2步，没有更多的节点了），此时p1在最中间的节点。p1之前是链表的前半段，p1之后就是链表的后半段：

代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head, *pre = NULL, *next = NULL;
        
        // 注意链表为空的时候也要返回true
        if (head == NULL || head->next == NULL) {
            return true;
        }

        // pre节点用于保存中间节点的前面一个节点
        while (fast && fast->next != NULL) {
            fast = fast->next->next;

            // 反转
            next = slow->next;
            slow->next = pre;
            pre = slow; // 备份节点
            slow = next;
        }

        // 奇数个节点的时候，fast指向最后一个节点，非NULL
        // 此时slow指向中间节点，slow下滑一个节点
        // 此时pre所指向的是前半段链表，slow所指向的是后半段链表
        if (fast != NULL) {
            slow = slow->next;
        }

        while (pre != NULL && slow != NULL) {
            if (pre->val != slow->val) {
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }

        return pre == NULL && slow == NULL;
    }
};

这里要注意的是pre指针的作用，从上面的图示中可以发现，不管是奇数还是偶数个节点，反转后都是从slow节点前分隔开的。因此pre的作用就是保存slow前面的节点，用于后续回文数比对。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

一、红黑树

红黑树也是BST树的一种，它和AVL树不同，它不要求各个节点的高度都是完全一致，是一个近似平衡的树。

红黑树通过黑树节点增加颜色，对每一条根节点到叶子节点上面的各个节点颜色进行约束，确保没有一条路径会比其他路径长出2倍。

红黑树的性质：

1. 每个节点的颜色要么是红色，要么是黑色
2. 根节点是黑色的
3. 每个叶子节点（NIL）是黑色
4. 如果一个节点是红色的，则它的两个子节点都是黑色的
5. 对于每个节点，其到任意后代的叶子节点的路径上，都包含相同数量的黑色节点

和普通树不同的是，红黑树的叶子节点都是NIL节点，它是一个特殊的节点，颜色是黑色。

定理：一个有n各内部节点的红黑树的高度至多为2lg(n+1)。

下面就是一棵红黑树示例，省去了末尾的NIL叶子节点：

红黑树的操作和BST/AVL树相差不大，搜索、旋转也都是一模一样的代码。红黑树的操作：

• RB_INSERT: 插入节点到红黑树
• RB_DELETE: 从红黑树中删除节点

二、红黑树的添加操作

红黑树每个新插入的节点都是红色，节点添加操作分为以下两步：

1. 按照BST的插入节点操作插入一个节点
2. 调整节点颜色，以满足红黑树性质

过程中负责的步骤是第二部，也就是插入之后的调整，调整的规则有如下几种。

2.1 节点颜色调整规则

假设待插入节点为z，设其叔叔节点为y。插入节点后，有以下几种情况：

情况一：父节点是红色，叔叔节点也是红色

这种情况下，插入节点z会违反性质4，并且z的叔父节点也是红色，所以为了维持性质，需要修改其父亲节点和叔叔节点的颜色为黑色，修改其祖父节点的颜色为红色。并把z设置为祖父节点，继续判断z的属性，如果修改后z的叔叔节点还是红色，继续当前的操作。直到叔叔节点y是黑色了，情况一就转换成情况二，向下看。

情况二：父节点是红色，叔叔节点是黑色，当前节点是其父节点的右儿子

叔叔节点是黑色，判断当前节点是其父亲的左儿子还是右儿子，如果是左儿子，将满足情况三，按照情况三来处理。如果是右儿子，设置z指向其父节点，并对新的z节点左旋，把情况二转换成情况三。

情况三：父节点是红色，叔叔节点是黑色，当前节点是其父节点的左儿子

这种情况下，为了保持平衡，修改z的父颜色为黑色，z的祖父节点为红色，然后对祖父节点右旋。得到满足条件的红黑树：

情况四：父节点是黑色

如果父节点是黑色，无需调整，插入节点后树依旧是一棵红黑树，性质不会破坏。

2.2 插入节点代码

红黑树的插入代码前部分和BST插入一模一样，最后添加完成之后执行操作FIXUP对红黑树进行调整：

void rb_tree_insert(struct rb_tree_st *tree, struct rb_tree_node_st *node) {
    struct rb_tree_node_st *x = tree->root;
    struct rb_tree_node_st *y = NULL;
    struct rb_tree_node_st *z = node;

    while (x != NULL) {
        y = x;
        if (z->key < x->key)
            x = x->lchild;
        else
            x = x->rchild;
    }

    z->parent = y;
    if (y == NULL)
        tree->root = z;
    else if (y->key > z->key)
        y->lchild = z;
    else
        y->rchild = z;

    z->lchild = NULL;
    z->rchild = NULL;
    node->color = NODE_COLOR_RED;

    rb_tree_fixup(tree, node);
}

红黑树调整代码：

void rb_tree_fixup(struct rb_tree_st *tree, struct rb_tree_node_st *node) {
    struct rb_tree_node_st *z = node;
    struct rb_tree_node_st *y = NULL;
    
    while (z->parent && z->parent->color == NODE_COLOR_RED) {
        // 如果父节点是红色，那么必定有祖父节点，根据父节点的位置得到叔父节点
        if (z->parent == z->parent->parent->lchild)
            // 父节点是祖父节点的左子节点
            y = z->parent->parent->rchild;
        else
            y = z->parent->parent->lchild;

        if (y && y->color == NODE_COLOR_RED) {
            // 叔父节点是红色，把叔父节点和父节点全部置黑，不区分叔父节点是左儿子还是右儿子
            y->color = NODE_COLOR_BLACK;
            z->parent->color = NODE_COLOR_BLACK;
            // 祖父节点置红，然后重新处理祖父节点
            z->parent->parent->color = NODE_COLOR_RED;
            z = z->parent->parent;
            continue;
        }

        // 此时叔父节点必定是黑色，把y设为祖父节点，需要区分叔父节点是左儿子还是右儿子
        y = z->parent->parent;
        if (z->parent == y->lchild) {
            if (z == z->parent->rchild) {
                z = z->parent;
                left_rotate(tree, z);
            }
            z->parent->color = NODE_COLOR_BLACK;
            z->parent->parent->color = NODE_COLOR_RED;
            right_rotate(tree, z->parent->parent);
        } else {
            if (z == z->parent->lchild) {
                z = z->parent;
                right_rotate(tree, z);
            }
            z->parent->color = NODE_COLOR_BLACK;
            z->parent->parent->color = NODE_COLOR_RED;
            left_rotate(tree, y);
        }
    }
    // 设置根节点是黑色
    tree->root->color = NODE_COLOR_BLACK;
}

三、删除节点

和AVL中一样，删除节点总是比增加节点麻烦一些。因为红黑树也是一颗BST树，并且也是一个接近平衡的二叉树，因此它的删除过程也和AVL树一样。先删除节点，然后调整，步骤为：

1. 删除或者替换节点，这一步有可能导致红黑树性质不满足
2. 调整节点颜色，以满足红黑树性质

在AVL树中，删除节点并不是把这个节点直接删除，而是找到这个节点的后继节点来替代该节点。红黑树中的删除也是按照这种办法，假设删除节点为z，设定y表示替换z位置的节点，x表示实际上被删除的节点（即逻辑上被删除的叶子节点），w是x的兄弟节点。删除节点x点有可能是z的儿子，也有可能是y的儿子，也有可能是NIL。

当删除节点是红色，删除时不会影响红黑树的性质，需要调整的直有删除节点是黑色的场景。

3.1 删除节点调整颜色规则

情况一：删除节点x的兄弟节点w是红色

操作：修改w和父节点的颜色，并对父节点左移。此时x的新兄弟节点是原w节点的左子节点，必定为黑色。情况一可以转换成下面的情况来处理。

情况二：x的兄弟节点w是黑色，且w的两个子节点都是黑色

操作：去掉w上的黑色，并使x为其父节点，继续循环处理新x节点。

情况三：x的兄弟节点w是黑色，w的左孩子是红色，w的右孩子是黑色

操作：修改w和其左儿子的颜色，并对w右旋，然后把w设置为其原来的左儿子。将情况三转换成情况四。

情况四：x的兄弟节点w是黑色，且w的右孩子是红色

第四种情况是我们最终想要转换的情况，因为只有这一种情况能通过旋转来彻底解决平衡。

操作：设置w的颜色为其父节点的颜色，w父节点设置为黑色，w的右儿子设置为黑色，对父节点进行左旋。

上面的描述过于抽象，可以用一个例子来理解。下面是一棵红黑树，想要删除节点60（60原先是黑色）：

删除的步骤：

1. 设置80的颜色为其父节点的颜色（红色）
2. 设置80的父节点70颜色为黑色，设置80右儿子85的颜色为黑色
3. 对70左旋，去掉节点60，得到右边的红黑树，此时红黑树的性质依旧保持

3.2 删除代码实现

删除红黑树节点的伪代码（来自算法导论）：

修复节点伪代码：

一、平衡二叉树

1.1 什么是平衡二叉树

平衡二叉树（AVL树）是二叉搜索树的一种，它是一种高度平衡的二叉树，树中的每一个节点，两个子节点的高度差最多为1。

在最坏的情况下，BST树高度差可以达到n，查找操作时间复杂度也会达到O(n)，此时树是一个链式形状，如下图所示：

对这棵树而言，它和链表几乎没有差别，反而比链表多了一些内存占用。而AVL树的出现就是为了解决这种情况，在AVL树中，这些元素将会被排布成：

此时查找一个元素的时间复杂度就是O(lgn)，节省了大量的时间。

AVL树所包含的操作和BST树一样：

• SEARCH：查找某个节点在树中的位置，实现和BST完全一致
• MINIMUM：求以指定节点为根的树中的最小元素，实现和BST完全一致
• MAXIMUM：求以指定节点为根的树中的最大元素，实现和BST完全一致
• PREDECESSOR：求指定节点的前驱节点，实现和BST完全一致
• SUCCESSOR：求指定节点的后继节点，实现和BST完全一致
• INSERT：在树中插入节点，实现在BST基础上修改
• DELETE：删除节点，实现在BST基础上修改

网上绝大部分AVL树的实现都是通过递归来的，为了秉持《算法导论》中的优良传统，也不打算使用递归来实现。而算法导论又没有针对AVL的章节，只在红黑树的课后习题13-3中提到了，并没有实现。除了INSERT和DELETE操作以外，其他操作都和BST树一致，下面就专门针对这两个操作对AVL树进行分析。

1.2 AVL树节点

相对BST树的节点来说，AVL树节点内部多了一个height成员，表示当前节点的高度。每当某个节点的左右子节点高度差超过1时（这个高度差被称为平衡因子，一般是右子节点的高度减去左子节点的高度），就需要对该节点进行旋转调整。

struct avl_tree_node_st {
    int key;
    int height; // 当前节点的高度
    struct avl_tree_node_st *parent;
    struct avl_tree_node_st *lchild;
    struct avl_tree_node_st *rchild;
};

关于初始时节点的高度为0还是为1的问题

大部分情况下，新建一个节点，会将它的高度设置为0，这比较符合主观的逻辑，因为它没有任何子节点。

这种情况下计算一个节点的高度的步骤为：

1. 如果该节点是叶子节点，得到高度为0
2. 如果该节点不是叶子节点，得到高度是左右子节点中高度更高的加1

这里要处理的一个特殊情况就是规则1：判断节点是否为叶节点，不是叶节点才能通过规则2计算。如果直接按照规则2来计算的话叶子节点高度是1，和预定条件相违背。

而如果初始化时，设置节点的高度为1，此时计算一个节点的高度就只有一个操作：

• 它的高度等于其左右子节点中高度更大的加1

不用判断是否为叶子节点，在程序处理中更好处理一点。而实际上，高度对我们来说不重要，重要的是平衡因子。

因此，AVL树节点的高度初始时设置为1更好一点。

二、左旋和右旋

AVL树最重要的操作就是左旋和右旋，当一个节点不平衡后，都需要通过这两个操作达到平衡：

对左旋和右旋的描述：

• 对节点y右旋：y将变成其左子节点x的右子节点，原来x的右子节点β变成y的左子节点。
• 对节点x左旋：x将变成其右子节点y的左子节点，原来的y的左子节点β变成x的右节点

两个操作是相反的，彼此旋转都可以得到对方，以下是一个左旋的例子：

左旋的代码实现：

static void _left_rotate(struct avl_tree_st *t, struct avl_tree_node_st *node) {
    struct avl_tree_node_st *x, *y;
    // x表示左旋节点，y表示x的右子节点
    x = node;
    y = x->rchild;

    // 修改x节点的右子节点指向
    x->rchild = y->lchild;
    if (y->lchild)
        y->lchild->parent = x;

    // 修改父节点使其子节点指向新的x节点
    y->parent = x->parent;
    if (x->parent == NULL)
        t->root = y;
    else if (x->parent->lchild == x)
        x->parent->lchild = y;
    else
        x->parent->rchild = y;

    // 重新设置x和y的关系
    y->lchild = x;
    x->parent = y;

    // 修改旋转后节点的高度
    x->height = NEW_HEIGHT(x);
    y->height = NEW_HEIGHT(y);
}

右旋和左旋基本一致，只是指针方向相反了。

三、二叉树操作

3.1 计算节点高度

获得一个节点的高度是O(1)的，因为节点内部已经有一个height成员，直接拿就行了。

static inline int _node_height(struct avl_tree_node_st *node) {
    if (node == NULL)
        return 0;
    return node->height;
}

而当一个节点更新之后，从这个节点往上的根节点高度都有可能更新，需要重新设置高度，此时更新的操作就是比较左右子节点的高度，在更高的基础上加1，C语言中可以直接使用宏定义完成：

#define NEW_HEIGHT(node)    \
    max(_node_height(node->rchild), _node_height(node->lchild)) + 1

计算某个节点的平衡因子:

static inline int _get_balance(struct avl_tree_node_st *node) {
    if (node == NULL)
        return 0;
    return _node_height(node->rchild) - _node_height(node->lchild);
}

3.2 增加节点

增加节点的前置操作和BST一致，给节点找到一个合适的位置先插入。然后再判断其是否满足平衡的条件，如果不满足，对它进行调整。增加节点有会有下面四种不平衡的情况。

3.2.1 LL型

下面的树中插入元素5导致树失衡，此时元素30的平衡因子为-2：

这种情况属于LL型不平衡状态，只要对不平衡的节点30执行右旋操作即可解决不平衡。

3.3.2 LR型

下面的树中插入元素15，此时元素30失衡，平衡因子为-2：

这种情况属于LR型不平衡状态，要先对插入元素的父节点10进行左旋，转换成LL型再对30右旋解决平衡。

3.3.3 RR型

下面的树中插入元素55，元素30失衡，平衡因子为2：

这种情况属于RR型不平衡状态，对30执行左旋即可恢复平衡。

3.3.4 RL型

在下面的树中，插入45导致30失衡，平衡因子为2：

这种情况属于RL型不平衡状态，先对50右旋，转换成RR型再对30左旋，恢复平衡。

3.3.5 插入操作实现

插入操作和BST的插入操作一模一样，只是在插入完成后，新增了一步对节点的平衡操作。

void avl_tree_insert(struct avl_tree_st *t, struct avl_tree_node_st *node) {
    struct avl_tree_node_st *x, *y;
    x = t->root;
    y = x;
    while (x != NULL) {
        y = x;
        if (node->key < x->key)
            x = x->lchild;
        else
            x = x->rchild;
    }

    node->parent = y;
    if (y == NULL)
        t->root = node;
    else if (node->key < y->key)
        y->lchild = node;
    else
        y->rchild = node;

    // 平衡节点
    if (y != NULL)
        avl_tree_insert_balance(t, node);
}

3.3.6 插入平衡

上面说过：插入节点后，有可能导致其父节点甚至祖父节点的高度变化。因此，平衡节点时，要从新增节点的父节点开始，一直到根节点，重新更新路径上每个节点的高度并计算平衡因子，一旦平衡因子不符合条件，则按照上面的四种情况旋转。

void avl_tree_insert_balance(struct avl_tree_st *t, struct avl_tree_node_st *node) {
    struct avl_tree_node_st *x, *y;
    // is_modify用来表示是否被旋转过了，如果旋转过了，旋转操作里面已经更新了高度，无需再更新高度
    int height, balance, is_modify;
    // x是新增节点
    x = node;
    // y是新增节点的父节点，从父节点开始，重新更新节点高度
    y = node->parent;

    while (y) {
        is_modify = 0;
        balance = _get_balance(y);
        if (balance > 1) {
            // 右子树高度高于左子树高度
            x = y->rchild;
            if (x->key < node->key) {
                // RR
                _left_rotate(t, y);
            } else {
                // RL
                _right_rotate(t, x);
                _left_rotate(t, y);
            }
            is_modify = 1;
        } 

        if (balance < -1) {
            // 左子树高度高于右子树高度
            x = y->lchild;
            if (x->key > node->key) {
                // LL
                _right_rotate(t, y);
            } else {
                // LR
                _left_rotate(t, x);
                _right_rotate(t, y);
            }
            is_modify = 1;
        }

        if (is_modify == 0) {
            // 没有执行旋转，判断高度是否有改变
            height = NEW_HEIGHT(y);
            if (height != y->height)
                y->height = height;
            else
                break; // 如果节点高度没有改变的话，也不会再影响父节点的高度，直接跳出循环
        }
       
        y = y->parent;
    }
}

3.3 删除节点

删除节点的操作比插入操作要复杂，同样也是先利用BST中的删除操作，执行元素删除。然后再对删除后的节点进行平衡操作。删除一个元素也是四种失衡场景，也是LL/LR/RR/RL，恢复平衡的方式和增加一致：

3.3.1 LL型

3.3.2 LR型

3.3.3 RR型

3.3.4 RL型

3.3.5 如何确认是哪种类型的旋转

删除节点失衡后，对失衡节点的旋转和调整和新增节点一模一样。

但是和新增节点不同，新增节点通过判断父节点的高度和平衡因子很容易就能分辨出旋转类型。删除节点后，当发现失衡时当前节点已经是失衡节点了，并不能直接确定属于哪种失衡。

处理办法：假设失衡节点是z，令y是z的子节点中高度更高的一个，令x是y的子节点中高度更高的一个，例如：

通过比较三者的key值就可以确定旋转的类型，此处y.key > z.key，属于R型，而x.key > y.key，也是R型。两者结合起来就是RR型，元素30应该执行左旋。

特殊情况

当z失衡时，左右子节点的高度必定不同。但是y的两个子节点高度有可能相同，这样就会产生两组特殊情况：

此时y的左右节点高度都是一致的，而实际上这种情况属于LL型，应该对30右旋。

相反的，下面这种情况应该属于RR型，要对30左旋：

3.3.6 删除节点后如何更新高度

增加节点后，从增加节点的父节点开始更新高度。但是删除和新增不同，删除都是通过叶子节点替代的方式来处理的，直接从删除节点的父节点开始更新高度不准确。此时可以分为以下几种情形：

删除节点只有一个节点

使用子节点L替换父节点后，L的高度不会增加，但是原来z的父节点高度减少了，要从z的父节点开始更新高度。

删除节点有两个节点且后继节点是删除节点的右儿子

在BST删除一个节点z时，如果节点有两个儿子，那么就要在右子树中找到最小的元素y替换被删除元素的位置。这个最小的元素y有两种情况：y是z的右儿子和y不是z的右儿子

当y是z的右儿子时：

y替代z后，y和x的高度都不会变化，同样只要从z的父节点开始更新高度就行了。

但是当y不是z的右儿子时，删除节点z后，x的高度不会变化，从x的新父亲r开始的节点就有可能发生变化，例如下图中的r的高度就减少了1：

此时要从y的原始父节点开始更新高度。并且还要注意的是：被删除节点z的父节点的高度也变化了，修改r的高度之后还要继续向上修改其祖先节点的高度。

3.3.7 删除代码

AVL删除和BST类似，只是多了一个x记录删除后需要开始更新高度的起始节点。

void avl_tree_delete(struct avl_tree_st *t, struct avl_tree_node_st *node) {
    struct avl_tree_node_st *x, *y;

    // x记录节点删除后需要开始更新高度的起始节点
    x = node;
    // y是实际要进行替换删除的节点
    y = node->parent;

    if (node->lchild == NULL || node->rchild == NULL) {
        y = node->lchild ? node->lchild : node->rchild;
        _transplant(t, node, y);
        // 只有一个子节点，需要更新高度的节点是被删除节点的父节点
        x = node->parent;
    } else {
        y = tree_minimum(node->rchild);
        x = y;
        if (y != node->rchild) {
            // 不是右子节点，需要更新高度的节点是y的父节点r
            x = y->parent;
            _transplant(t, y, y->rchild);
            y->rchild = node->rchild;
            y->rchild->parent = y;
        }
        _transplant(t, node, y);
        y->lchild = node->lchild;
        y->lchild->parent = y;
    }
    // 删除完成之后，修改各节点高度，调整平衡
    if (x != NULL)
        avl_tree_delete_balance(t, x);
}

3.3.8 更新节点高度和平衡

根据章节3.3.1-3.3.5可以得到删除节点后的平衡处理代码：

void avl_tree_delete_balance(struct avl_tree_st *t, struct avl_tree_node_st *node) {
    struct avl_tree_node_st *x, *y, *z;
    int height, balance, is_modify;

    // z是被删除节点后需要开始更新高度的起始节点
    // z失衡后，y是z的子节点中高度最高的，x是y的子节点中高度较高的
    z = node;

    while (z) {
        is_modify = 0;
        balance = _get_balance(z);

        if (balance > 1) {
            // R型
            y = _node_height(z->rchild) > _node_height(z->lchild) ? z->rchild : z->lchild;
            // 注意>=符号，不是>号
            x = _node_height(y->rchild) >= _node_height(y->lchild) ? y->rchild : y->lchild;
            if (x->key > y->key) {
                // RR
                _left_rotate(t, z);
            } else {
                // RL
                _right_rotate(t, y);
                _left_rotate(t, z);
            }
            is_modify = 1;
        }

        if (balance < -1) {
            y = _node_height(z->rchild) > _node_height(z->lchild) ? z->rchild : z->lchild;
            x = _node_height(y->rchild) > _node_height(y->lchild) ? y->rchild : y->lchild;
            if (x->key < node->key) {
                // LL
                _right_rotate(t, z);
            } else {
                // LR
                _left_rotate(t, y);
                _right_rotate(t, z);
            }
            is_modify = 1;
        }

        if (is_modify == 0) {
            height = NEW_HEIGHT(z);
            z->height = height;
        }

        z = z->parent;
    }
}

四、关于节点增加或删除后更新祖先节点高度的终止条件

当插入或者删除节点的时候，会引起其祖先节点的高度修改，从而产生不平衡。因此，每次增加或者修改元素之后，需要从该节点的父节点开始，在去往根节点的路径上，逐个对每个节点的高度更新。

由于树的高度是左右子节点的高度决定的，那么可以得到一个结论：如果左右子节点的高度没有变化的话，其祖先节点的高度一定不会变化，其平衡因子也不会变化。因此，对于增加节点而言，如果在到根路径上的某个节点高度没有变化的话，就无需再继续向上更新了。例如：

增加25和35元素并没有引起其父节点高度的变化，因此其祖父节点的高度也不会变化，在更新完其父节点的高度后就可以终止循环了。

在增加和删除操作中，都有一个is_modify变量来记录该节点是否失衡被旋转了。如果这个字段的值是0，表示该节点没有失衡，没有执行旋转操作，需要更新该节点的高度。如果这个字段是1，表示节点被旋转了，旋转之后的节点高度已经被重新赋值了，无需再次修改。这也就是为什么把计算平衡因子放在计算节点高度之后了，避免重复更新高度。

而height的作用就是判断节点高度是否变化了，如果没有变化，根据上面的出的结论，就无需继续遍历祖先节点了，祖先节点的高度一定不会变化，跳出循环即可。

五、参考文档

BST树实现

AVL Tree | Set 1 (Insertion)

AVL Tree | Set 2 (Deletion)

一、二叉搜索树

1.1 什么是二叉搜索树

算法导论中对二叉搜索树（Binary Search Tree, 简称BST）的定义：

设x是二叉搜索树中的一个节点，如果y是x左子树中的一个节点，那么y.key<=x.key。如果y是x右子树中的一个节点，那么y.key>=x.key。

以下两棵树就是二叉搜索树：

其中a是一个包含6个节点，高度为2的二叉搜索树。b是一个包含相同关键字、高度为4的低效二叉树。

注意：树中包含了两个相同的节点5，在实际用途中，很少把相同的关键字放到二叉搜索树中。

二叉搜索树主要的操作：

• SEARCH：查找某个节点在树中的位置
• MINIMUM：求以指定节点为根的树中的最小元素
• MAXIMUM：求以指定节点为根的树中的最大元素
• PREDECESSOR：求指定节点的前驱节点
• SUCCESSOR：求指定节点的后继节点
• INSERT：在树中插入节点
• DELETE：删除节点

定理：二叉搜索树中的以上各个操作都是在O(h)时间内完成。

1.2 树节点定义

二叉搜索树的节点需要包含以下元素：

• 节点的键值，也就是key
• 父节点和左右子节点的指针

假设key值类型为int，那么树节点的结构应该为：

struct bst_tree_node_st {
    int key;
    struct bst_tree_node_st *lchild;
    struct bst_tree_node_st *rchild;
    struct bst_tree_node_st *parent;
};

二、二叉搜索树操作

2.1 查找操作( SEARCH)

通过二叉搜索树的性质很容易得到查找算法：从树根开始查找，沿着树的路径一直向下。对每个遇到的节点x，比较关键字k和x.key，如果两个关键字相等，查找终止。如果k小于x.key，在x的左子树中继续查找。否则就在x的右子树中继续查找。

伪代码如下（来自《算法导论》)：

TREE-SEARCH(x, k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else return TREE-SEARCH(x.right, k)

上面采用了递归的方法来进行查找，递归最明显的特点就是简单，代码量小。但是在树高度很高时候，递归就会产生巨大的内存消耗和更多的CPU消耗，因为要频繁对函数及参数压栈，并且函数中栈是有大小限制的，不能无限递归。

大部分时候建议使用非递归查找，非递归查找的伪代码实现为：

ITERATIVE-TREE-SEARCH(x, k)
    while x ≠ NIL and k ≠ x.key
        if k < x.key
            x = x.left
        else x = x.right
    return x

非递归对应的C语言描述：

struct bst_tree_node_st *bst_tree_search(struct bst_tree_st *t, int key) {
    struct bst_tree_node_st *p = t->root;
    while (p != NULL && key != p->key) {
        if (key < p->key)
            p = p->lchild;
        else
            p = p->rchild;
    }
    return p;
}

2.2 求最大元素(MAXIMUM)和最小元素(MINIMUM)

根据二叉树的性质可知：最小的节点一定是最左边的节点，最大的节点一定是最右边的节点。

例如对下面这个二叉树而言，最小的元素是2，最大的元素是20。

找最小的元素只要一直在左子节点中查找，直到节点的左节点是NULL为止。相反，找最大的元素，只要在节点的右节点中查找，直到右节点是NULL为止。

/*
 * 得到某个子树中的最小元素节点
 * @root 待查找的子树根节点
 * @return 返回最小元素节点的指针，如果最小元素就是node，那么返回node
 */
struct bst_tree_node_st *bst_tree_minimum(struct bst_tree_node_st *root) {
    struct bst_tree_node_st *p = root;
    while (p != NULL && p->lchild != NULL)
        p = p->lchild;
    return p;
}

/*
 * 得到某个子树中的最大元素节点
 * @root 待查找的子树根节点
 * @return 返回最大元素节点的指针，如果最大的元素就是node，那么返回node
 */
struct bst_tree_node_st *bst_tree_maximum(struct bst_tree_node_st *root) {
    struct bst_tree_node_st *p = root;
    while (p != NULL && p->rchild != NULL)
        p = p->rchild;
    return p;
}

2.3 求前驱(PREDECESSOR)和后继(SUCCESSOR)

节点x的前驱节点是指中序遍历中顺序在x之前的元素，节点x的后继节点指中序遍历中顺序在x之后的元素。

以2.3节中的二叉树为例，其中序遍历的结果为：2 3 4 6 7 9 13 15 17 18 20。对于元素6而言，它的前驱节点是4，后继节点是7。

求前驱节点的过程：

• 如果节点有左子节点，那么前驱节点一定是左子树中的最大元素。例如6的前驱是4，15的前驱是13
• 如果节点没有左子节点，那么它的前驱就是以它或者以它任一祖先为右儿子的节点，例如上图中节点9的前驱是7，节点7的前驱是6

求后继节点的过程：

• 如果节点有右子节点，那么后继节点一定是右子树中最小的元素。例如15的后继节点是17，18的后继节点是20
• 如果节点没有右子节点，那么它的后继就是以它或者以它任一祖先为左儿子的节点，例如上图中的13的后继节点是15，17的后继节点是18

可以得到的一个结论：树中最小的元素没有前驱节点，树中最大的元素没有后继节点。

求前驱节点和后继节点的C语言描述：

/*
 * 求树中某个节点的后继节点
 * @node 当前节点，如果没有后继节点，返回NULL
 */
struct bst_tree_node_st *bst_tree_successor(struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x = node, *p;
    if (x->rchild)
        return bst_tree_minimum(x->rchild);

    p = x->parent;
    while (p != NULL && p->rchild == x) {
        x = p;
        p = x->parent;
    }
    return p;
}

/*
 * 求树中某个节点的前驱节点
 * @node 当前节点，如果没有前驱节点，返回NULL
 */
struct bst_tree_node_st *bst_tree_predecessor(struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x = node, *p;
    if (x->lchild)
        return bst_tree_maximum(x->lchild);

    p = x->parent;
    while (p != NULL && p->lchild == x) {
        x = p;
        p = p->parent;
    }
    return p;
}

2.4 插入节点(INSERT)

插入节点和搜索节点的工作方式一样，先根据元素大小找到合适的位置，然后作为子节点插入，每次插入的节点必定是叶子节点。

例如在下面的树中插入元素13，首先要找到它的父节点15，然后作为它的左子节点插入：

C语言实现：

/*
 * 在树中插入节点
 * @t 树
 * @node 新节点
 */
void bst_tree_insert(struct bst_tree_st *t, struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x, *y;
    y = NULL;
    x = t->root;
    // 找到合适的插入位置
    while (x != NULL) {
        y = x;
        if (node->key < x->key)
            x = x->lchild;
        else
            x = x->rchild;
    }
    node->parent = y;
    if (y == NULL)
        t->root = node;
    else if (node->key < y->key)
        y->lchild = node;
    else
        y->rchild = node;
}

2.5 删除节点(DELETE)

2.5.1 删除节点的基本操作

相对来说，删除节点要比插入节点复杂许多，它有三种不同的情况：

1. 如果待删除节点z没有孩子节点，那么直接把它删除，修改父节点指针即可完成。
2. 如果待删除节点z只有一个孩子，那么将这个孩子替换到z的位置，修改z的父节点指针，指向z的子节点。
3. 如果待删除节点z有两个孩子，找到z的后继节点y，让y占据z的位置，同时还要让y的右子节点（如果有的话）占据y的位置。

前面两种情况相对简单，甚至可以被合并成一种情况。而第三种情况最为复杂，它还能继续向下分解：

• z的后继节点y就是z的右子节点

• z的后继节点y不是z的右子节点，这种情况下可以推断出y一定不含左子节点，但此时y的右子节点x又有两种情况：

  • x为空
  • x不为空

下面分别对以上几种情况进行讨论：

2.5.2 删除节点只有一个儿子

只有左子节点的情况

只有右子节点的情况

不管是左儿子，还是右儿子，直接替换原删除节点即可。

2.5.3 删除节点有两个儿子且后继节点是右儿子

对应情况：

只需要把z的位置替换成y就可以了。

2.5.4 删除节点有两个儿子且后继节点不是右儿子

后继节点y不是z的右儿子，那么y必定没有左儿子（如果y有左儿子的话，那么z的后继节点肯定就是y的左儿子而不会是y）。

情况对应下图：

此时要做的两步操作：

1. 将y的右儿子（不管是否为NULL）替换成y
2. 将y替换成z

2.5.4 删除节点的代码

添加一个辅助操作TRANSPLANT，英文意思是移植，表示把一个节点用另一个节点代替：

static void transplant(struct bst_tree_st *t,
    struct bst_tree_node_st *old_node,
    struct bst_tree_node_st *new_node) {
    if (old_node->parent == NULL)
        t->root = new_node;
    else if (old_node == old_node->parent->lchild)
        old_node->parent->lchild = new_node;
    else
        old_node->parent->rchild = new_node;
    
    // 如果替换新节点不是NULL，设置新节点的父指针指向
    if (new_node != NULL)
        new_node->parent = old_node->parent;

然后在TREE_DELETE操作中调用TRANSPLANT完成删除操作：

/*
 * 删除节点
 * @t 树
 * @node 待删除的节点
 */
void bst_tree_delete(struct bst_tree_st *t, struct bst_tree_node_st *node) {
    struct bst_tree_node_st *y;
    if (node->lchild == NULL || node->rchild == NULL)
        // 至少有一个子节点为空，直接用子节点替换
        _transplant(t, node, node->lchild ? node->lchild : node->rchild);
    else {
        // 得到右子树中的最小节点，即节点在右子树中的后继节点
        y = bst_tree_minimum(node->rchild);
        if (y->parent != node) {
            // y不是删除节点的子节点，用y的右节点替换y
            _transplant(t, y, y->rchild);
            y->rchild = node->rchild;
            y->rchild->parent = y;
        }
        // 用y替换删除节点
        _transplant(t, node, y);
        y->lchild = node->lchild;
        y->lchild->parent = y;
    }
}