chapter_tree/avl_tree/

[giscus[bot]]

chapter_tree/avl_tree/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_tree/avl_tree/

[hello-ikun]

这部分确实是有点难度

[krahets]

很是同意，所以本章标了选读符号 doge

[hello-ikun]

k宝 你说的并查集什么时候更新呢

[krahets]

并查集近期不会更新 T T

[zrcoder]

@Xia-Sang 之前写过一篇并查集，虚构程序员写武侠游戏的故事来说： https://rdcode.netlify.app/main/graph/union-find/index.html

[hello-ikun]

感谢你的回复！

[symbolworld]

K神有时间可以更新一章红黑树的区别吗？想看看它们的区别和各自的应用场景，感谢！

[krahets]

红黑树暂时不在内容大纲里，抱歉哇！近期应该不会更新

[Mahaotian1]

您好，请问python的会更新吗

[krahets]

已更新～

[anzhen3531]

K神会更新图数据结构嘛 ？

[krahets]

必须的！

[GarveyH]

大佬，请问这一节中哪些函数归在private，哪些函数归在public中，这方面有什么考量吗？比如为什么要将 height 函数和 updateHeight 函数 分别放在 public 和 private 中呢？

[krahets]

Hi! 主要看方法的使用范围，如果方法只在类内部使用（一般也不希望用户调用），那么就设计为 private ，比如用户单独调用 updateHeight() 是没有意义的，它只是插入、删除操作中的一步。而 height() 是访问结点高度，类似于 vector.size() ，可以设置成 public 以便使用。

[TujinLee]

有个疑问，我看右旋操作是处理失衡节点node、child、grandchild之间的关系，那node的父级和node原来的连接不需要维护吗？右旋操作后岂不是断掉了？

[jiangyuxustore]

可以这么理解吗？如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上

[krahets]

@jiangyuxustore Bingo! 或者可以把“该节点的左子树中的最大节点”替换到删除节点上，本质上是不希望破坏二叉搜索树“左<根<右”的性质。

[plwater]

removeHelper(TreeNode node, int val) 方法（Java代码）的注释我觉得写得不是很规范，导致这部分代码有点晦涩难懂（也有可能是我太菜了ww），需要花很多时间和翻看评论区的讨论才能逐渐消化，如果把算法的方法注释（特别是方法入口处的注释）写得规范一点，我想对于帮助读者自行消化可能会起到很大的帮助，也会让这个项目价值更高。
特别感谢K老师和其他人的开源贡献，最近复习算法，收获特别大。
下面是根据我的理解补充的注释，可能不准确，仅为参考。

 /**
     * 递归删除节点（辅助方法）
     * @param node 二叉树的根节点（也可能是二叉树子树的根节点）
     * @param val 要删除的节点的值
     * @return 删除对应节点后的子树的根节点
     */
    private TreeNode removeHelper(TreeNode node, int val) {
    }

[krahets]

@plwater Hi，谢谢建议！建议前往代码仓库下载完整代码并运行，在调试过程中理解复杂代码。本书为了提升篇幅的紧凑性，部分放弃了代码注释的规范性

[plwater]

感谢建议，我会尝试在本地调试，理解你的用意了。

[YiCai1737407]

k神，这部分还会介绍红黑树吗？

[krahets]

正在考虑～！

[fallenleavesguy]

一定要介绍啊，我的大佬，嘿嘿

[limuzi9806]

加一

[Hutu-666]

大佬，想问一下，updateHeight()方法里为啥要 + 1 操作？

[krahets]

Hi，这个公式的含义是 高度 = max(左子树高度, 右子树高度) + 1 。其中，左子树高度和右子树高度是不包含该节点的高度的，因此要加 1 。

[UFO583]

/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
TreeNode *child = node->left;
TreeNode *grandChild = child->right;
// 以 child 为原点，将 node 向右旋转
child->right = node;
node->left = grandChild;
// 更新节点高度
updateHeight(node);
updateHeight(child);
// 返回旋转后子树的根节点
return child;
}
K神为什么这里没有更新 grandChild 的高度呢

[krahets]

Hi ，这是因为执行右旋（或左旋）后，节点 grandChild 的高度不会改变，可以观察文中配图来验证一下

[bethewind]

讲的不错,经过你的讲解感觉AVL树只有红黑树10%的难度

[hello-ikun]

复刻了一下 感觉可以的

[riiyn]

大佬，先左旋再右旋那张图，child.left=node, node.left=null也可以达到平衡吧，只是破坏了二叉搜索树的规则，这种做法属于左旋吗？左旋的时候child既可以取node左子节点也可以取右子节点吧，右旋同理

[krahets]

是的，这样会破坏二叉搜索树的性质，所以不能称为旋转操作了。旋转操作的意义就是在保持二叉搜索树性质的基础上，恢复二叉树的平衡性。两者缺一不可

[riiyn]

@krahets 明白了，谢谢大佬，还有个疑问，rotate那个方法，node的平衡因子判断应该是>0和<0吧，要不然不是忽略了1和-1的情况

[krahets]

@riiyn 客气啦，平衡因子判断是 $&gt; 1$ 和 $&lt; -1$ ，因为子树在这种情况下才是失衡的，${-1, 0, 1}$ 这三种情况是平衡状态，无需旋转。

[bukexiusi]

if t.balanceFactor(node.Left) >= 0 {
// 右旋
return t.rightRotate(node)
} else {
// 先左旋后右旋
node.Left = t.leftRotate(node.Left)
return t.rightRotate(node)
}

为什么判断条件是 >= 0，是不是 > 0 也可以，因为左右高度差不可能为 0

[krahets]

Hi，node.left 的左右高度差可能为 0 哈。例如在文中的 grandChild 底下再添加一个子节点。

[Liuhyi]

=0的时候可以直接右旋，也可以先左旋在右旋

[wanlufun]

为什么不用 updateHeight(grandChild) 呀？

[wanlufun]

我懂了 我懂了 基础知识忘记啦

分析原因

节点的高度，只与这个节点的子节点高度有关，由于没有修改grandchild 的子节点， 所以不需要updateHeight(grandChild)

[jincet]

这里讲的真好，清楚易懂

[XiaoGu-student-ore]

作者大大，我有一个问题，在c语言中，旋转总函数里面，不论你是上述四种失衡情况的哪一种，都会使node，child，grandchild变成一个横向链表，那在定义左旋和右旋函数中grandchild节点应该不需要声明吧？

[fgc346]

作者你好，建议左右旋的图片可以再优化下。我第一次看左右旋有点懵，不知道是谁绕着谁，向什么方向旋转。

[krahets]

好的，谢谢建议！

[480284856]

要不说成是：以“child”为原点，将处于“child”右边的“node”节点顺时针方向旋转？

[hml1996-fight]

作者你好，在向右旋转的python版本代码中有个疑问：
假如树为图7-26<1>所示，那么将值为3的节点进行右旋后，最终的结果会导致值为4的根节点的left还是值为3的节点呀

[hml1996-fight]

看到了前面TujinLee提出了相同的问题，明白了！

[liweijian199011]

期待可以早日加上红黑树，B+树，B-树的内容

[krahets]

mark

[Keria04]

/* 递归插入节点（辅助方法） */
TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return new TreeNode(val);
    /* 1. 查找插入位置并插入节点 */
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return 

关于插入节点的函数的问题：这个函数更新节点高度的部分似乎永远不会执行。

[sacredcodex]

你这里代码似乎缺失一点东西，不知道是这两天更新上的新内容，还是你复制漏掉了。应该是return node;吧。

在更新高度前有两个return，分别是创建一个新的叶子节点和重复不插入，这两种情况下，节点一定是平衡的，不需要判断更新。对于添加在左右节点会导致高度不平衡，对应这两个情况

    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);

他们在执行完这段命令后会更新高度信息。

[Keria04]

明白了，是我考虑不周。感谢回复！

[a2635814919]

7.5.3 AVL树常用操作里面 1.插入节点的代码部分，

    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);

没有在旋转操作之后调用updateHeight方法是不是因为balanceFactor方法调用了height方法，而height方法是递归的，所以节点已经实际上更新了高度的原因？

[a2635814919]

老师，还有一个问题是，代码展示块能不能改成可自定义长度，因为有的方法可能要拖动才能看全，有些不太方便

[sacredcodex]

在执行rotate操作时，已经对高度变化的节点调用了updateHeight方法，高度已经更新了。height方法不是递归的，只是输出节点存储的height值，只有updateHeight更新节点，没有递归。

[a2635814919]

@sacredcodex 谢谢，在左右单旋的时候调用了updateHeight方法，是我理解错误了

[Vstornzw]

C++
AVLTree类中TreeNode *root改为TreeNode *root = nullptr，否则在执行到：

/* 递归插入节点（辅助方法） */
TreeNode *insertHelper(TreeNode node, int val) {
if (node == nullptr)
return new TreeNode(val);
/ 1. 查找插入位置并插入节点 */
if (val < node->val)
...
报错

[krahets]

已测试无报错，请前往代码仓库下载源代码：https://github.com/krahets/hello-algo

[Vstornzw]

好的谢谢作者

[NaZixia]

个人的一些记忆方法
一个节点: 左旋:断右,接右 右旋:断左,接左

设本节点为T(ree) 本节点的左孩子 L 右孩子R R的右孩子r L的左孩子
左旋: 1断右 断开T与R ,断开 R与r
2接右 把T接到R的右 把r接到T的右 (接的是断开右剩下的树,可能不是单个节点)
3用R代替T操作前的位置

[NaZixia]

更正一下:
右多左旋,左多右旋
左旋:断右左,接右左 (左 右左
右旋:断左右,接左右 (右 左右
设本节点T,左右孩子大写的L R , 右孩子R的左右孩子小写l r,
设置本节点T与其父节点F(Father)默认断开
左旋:
1 断右左(边) 断开T与R,断开R与l
2 接右左(边) 接上T与l,接上R与T
3 F指R

    右旋: 左右改右左  R l 改L r

[KnewHow]

建议：可以扩展一个新的章节: 红黑树

[foxerz098]

Btree Rtree 红黑树什么时候考虑加上呀

[whoamiR]

厉害！

[Vstornzw]

在作者还没有开辟红黑树之前，这里先给出C++版本的红黑树哈
//红黑树不带删除
#include
#include
using namespace std;

enum RBTColor { RED, BLACK };

template
class RBTNode {
public:
RBTColor color; // 颜色
T key; // 关键字(键值)
RBTNode* left; // 左孩子
RBTNode* right; // 右孩子
RBTNode* parent; // 父结点

RBTNode(T value, RBTColor c, RBTNode* p, RBTNode* l, RBTNode* r) :
    key(value), color(c), parent(), left(l), right(r) {}
~RBTNode()
{
    cout << "delete : " << key << endl;
}

};

template
class RBTree {
private:
RBTNode* mRoot; // 根结点

public:
RBTree();
~RBTree();

// 前序遍历"红黑树"
void preOrder();
// 中序遍历"红黑树"
void inOrder();
// 后序遍历"红黑树"
void postOrder();

// (递归实现)查找"红黑树"中键值为key的节点
RBTNode<T>* search(T key);
// (非递归实现)查找"红黑树"中键值为key的节点
RBTNode<T>* iterativeSearch(T key);

// 查找最小结点：返回最小结点的键值。
T minimum();
// 查找最大结点：返回最大结点的键值。
T maximum();

// 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
RBTNode<T>* successor(RBTNode<T>* x);
// 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
RBTNode<T>* predecessor(RBTNode<T>* x);

// 将结点(key为节点键值)插入到红黑树中
void insert(T key);

// 销毁红黑树
void destroy();

// 打印红黑树
void print();

private:
// 前序遍历"红黑树"
void preOrder(RBTNode* tree) const;
// 中序遍历"红黑树"
void inOrder(RBTNode* tree) const;
// 后序遍历"红黑树"
void postOrder(RBTNode* tree) const;

// (递归实现)查找"红黑树x"中键值为key的节点
RBTNode<T>* search(RBTNode<T>* x, T key) const;
// (非递归实现)查找"红黑树x"中键值为key的节点
RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;

// 查找最小结点：返回tree为根结点的红黑树的最小结点。
RBTNode<T>* minimum(RBTNode<T>* tree);
// 查找最大结点：返回tree为根结点的红黑树的最大结点。
RBTNode<T>* maximum(RBTNode<T>* tree);

// 左旋
void leftRotate(RBTNode<T>*& root, RBTNode<T>* x);
// 右旋
void rightRotate(RBTNode<T>*& root, RBTNode<T>* y);
// 插入函数
void insert(RBTNode<T>*& root, RBTNode<T>* node);

//void insert(RBTNode<T>*& root, RBTNode<T>* node);
// 插入修正函数
void insertFixUp(RBTNode<T>*& root, RBTNode<T>* node);
// 销毁红黑树
void destroy(RBTNode<T>*& tree);

// 打印红黑树
void print(RBTNode<T>* tree, T key, int direction);

#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color==RED)
#define rb_is_black(r) ((r)->color==BLACK)
#define rb_set_black(r) do { (r)->color = BLACK; } while (0)
#define rb_set_red(r) do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c) do { (r)->color = (c); } while (0)
};

/*

• 构造函数
  */
  template
  RBTree::RBTree() :mRoot(NULL)
  {
  mRoot = NULL;
  }

/*

• 析构函数
  */
  template
  RBTree::~RBTree()
  {
  destroy();
  }

/*

• 前序遍历"红黑树"
  /
  template
  void RBTree::preOrder(RBTNode tree) const
  {
  if (tree != NULL)
  {
  cout << tree->key << " ";
  preOrder(tree->left);
  preOrder(tree->right);
  }
  }

template
void RBTree::preOrder()
{
preOrder(mRoot);
}

/*

• 中序遍历"红黑树"
  /
  template
  void RBTree::inOrder(RBTNode tree) const
  {
  if (tree != NULL)
  {
  inOrder(tree->left);
  cout << tree->key << " ";
  inOrder(tree->right);
  }
  }

template
void RBTree::inOrder()
{
inOrder(mRoot);
}

/*

• 后序遍历"红黑树"
  /
  template
  void RBTree::postOrder(RBTNode tree) const
  {
  if (tree != NULL)
  {
  postOrder(tree->left);
  postOrder(tree->right);
  cout << tree->key << " ";
  }
  }

template
void RBTree::postOrder()
{
postOrder(mRoot);
}

/*

• (递归实现)查找"红黑树x"中键值为key的节点
  /
  template
  RBTNode RBTree::search(RBTNode* x, T key) const
  {
  if (x == NULL || x->key == key)
  return x;

  if (key < x->key)
  return search(x->left, key);
  else
  return search(x->right, key);
  }

template
RBTNode* RBTree::search(T key)
{
search(mRoot, key);
}

/*

• (非递归实现)查找"红黑树x"中键值为key的节点
  /
  template
  RBTNode RBTree::iterativeSearch(RBTNode* x, T key) const
  {
  while ((x != NULL) && (x->key != key))
  {
  if (key < x->key)
  x = x->left;
  else
  x = x->right;
  }

  return x;
  }

template
RBTNode* RBTree::iterativeSearch(T key)
{
iterativeSearch(mRoot, key);
}

/*

• 查找最小结点：返回tree为根结点的红黑树的最小结点。
  /
  template
  RBTNode RBTree::minimum(RBTNode* tree)
  {
  if (tree == NULL)
  return NULL;

  while (tree->left != NULL)
  tree = tree->left;
  return tree;
  }

template
T RBTree::minimum()
{
RBTNode* p = minimum(mRoot);
if (p != NULL)
return p->key;

return (T)NULL;

}

/*

• 查找最大结点：返回tree为根结点的红黑树的最大结点。
  /
  template
  RBTNode RBTree::maximum(RBTNode* tree)
  {
  if (tree == NULL)
  return NULL;

  while (tree->right != NULL)
  tree = tree->right;
  return tree;
  }

template
T RBTree::maximum()
{
RBTNode* p = maximum(mRoot);
if (p != NULL)
return p->key;

return (T)NULL;

}

/*

• 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
  /
  template
  RBTNode RBTree::successor(RBTNode* x)
  {
  // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
  if (x->right != NULL)
  return minimum(x->right);

  // 如果x没有右孩子。则x有以下两种可能：
  // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
  // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
  RBTNode* y = x->parent;
  while ((y != NULL) && (x == y->right))
  {
  x = y;
  y = y->parent;
  }

  return y;
  }

/*

• 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
  /
  template
  RBTNode RBTree::predecessor(RBTNode* x)
  {
  // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
  if (x->left != NULL)
  return maximum(x->left);

  // 如果x没有左孩子。则x有以下两种可能：
  // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
  // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
  RBTNode* y = x->parent;
  while ((y != NULL) && (x == y->left))
  {
  x = y;
  y = y->parent;
  }

  return y;
  }

/*

• 对红黑树的节点(x)进行左旋转
• 左旋示意图(对节点x进行左旋)：

•  px                              px
  

• /                               /
  

• x y
• / \ --(左旋)--> / \ #
• lx y x ry

• /   \                       /  \
  

• ly ry lx ly

/
template
void RBTree::leftRotate(RBTNode& root, RBTNode* x)
{
// 设置x的右孩子为y
RBTNode* y = x->right;

// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
    y->left->parent = x;

// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;

if (x->parent == NULL)
{
    root = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
}
else
{
    if (x->parent->left == x)
        x->parent->left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
    else
        x->parent->right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}

// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;

}

/*

• 对红黑树的节点(y)进行右旋转
• 右旋示意图(对节点y进行左旋)：

•        py                               py
  

•       /                                /
  

•      y                                x
  

•     /  \      --(右旋)-->            /  \                     #
  

•    x   ry                           lx   y
  

•   / \                                   / \                   #
  

•  lx  rx                                rx  ry
  

/
template
void RBTree::rightRotate(RBTNode& root, RBTNode* y)
{
// 设置x是当前节点的左孩子。
RBTNode* x = y->left;

// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y->left = x->right;
if (x->right != NULL)
    x->right->parent = y;

// 将 “y的父亲” 设为 “x的父亲”
x->parent = y->parent;

if (y->parent == NULL)
{
    root = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
}
else
{
    if (y == y->parent->right)
        y->parent->right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
    else
        y->parent->left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}

// 将 “y” 设为 “x的右孩子”
x->right = y;

// 将 “y的父节点” 设为 “x”
y->parent = x;

}

/*

• 红黑树插入修正函数
• 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
• 目的是将它重新塑造成一颗红黑树。
• 参数说明：

• root 红黑树的根
  

• node 插入的结点        // 对应《算法导论》中的z
  

/
template
void RBTree::insertFixUp(RBTNode& root, RBTNode* node)
{
RBTNode* parent, * gparent;

// 若“父节点存在，并且父节点的颜色是红色”
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
    gparent = rb_parent(parent);

    //若“父节点”是“祖父节点的左孩子”
    if (parent == gparent->left)
    {
        // Case 1条件：叔叔节点是红色
        {
            RBTNode<T>* uncle = gparent->right;
            if (uncle && rb_is_red(uncle))
            {
                rb_set_black(uncle);
                rb_set_black(parent);
                rb_set_red(gparent);
                node = gparent;
                continue;
            }
        }

        // Case 2条件：叔叔是黑色，且当前节点是右孩子
        if (parent->right == node)
        {
            RBTNode<T>* tmp;
            leftRotate(root, parent);
            tmp = parent;
            parent = node;
            node = tmp;
        }

        // Case 3条件：叔叔是黑色，且当前节点是左孩子。
        rb_set_black(parent);
        rb_set_red(gparent);
        rightRotate(root, gparent);
    }
    else//若“z的父节点”是“z的祖父节点的右孩子”
    {
        // Case 1条件：叔叔节点是红色
        {
            RBTNode<T>* uncle = gparent->left;
            if (uncle && rb_is_red(uncle))
            {
                rb_set_black(uncle);
                rb_set_black(parent);
                rb_set_red(gparent);
                node = gparent;
                continue;
            }
        }

        // Case 2条件：叔叔是黑色，且当前节点是左孩子
        if (parent->left == node)
        {
            RBTNode<T>* tmp;
            rightRotate(root, parent);
            tmp = parent;
            parent = node;
            node = tmp;
        }

        // Case 3条件：叔叔是黑色，且当前节点是右孩子。
        rb_set_black(parent);
        rb_set_red(gparent);
        leftRotate(root, gparent);
    }
}

// 将根节点设为黑色
rb_set_black(root);

}

/*

• 将结点插入到红黑树中
• 参数说明：

• root 红黑树的根结点
  

• node 插入的结点        // 对应《算法导论》中的node
  

/
template
void RBTree::insert(RBTNode& root, RBTNode* node)
{
RBTNode* y = NULL;
RBTNode* x = root;

// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != NULL)
{
    y = x;
    if (node->key < x->key)
        x = x->left;
    else
        x = x->right;
}

node->parent = y;
if (y != NULL)
{
    if (node->key < y->key)
        y->left = node;
    else
        y->right = node;
}
else
    root = node;

// 2. 设置节点的颜色为红色
node->color = RED;

// 3. 将它重新修正为一颗二叉查找树
insertFixUp(root, node);

}

/*

• 将结点(key为节点键值)插入到红黑树中
• 参数说明：

• tree 红黑树的根结点
  

• key 插入结点的键值
  

/
template
void RBTree::insert(T key)
{
RBTNode z = NULL;

// 如果新建结点失败，则返回。
if ((z = new RBTNode<T>(key, BLACK, NULL, NULL, NULL)) == NULL)
    return;

insert(mRoot, z);

}

/*

• 销毁红黑树
  /
  template
  void RBTree::destroy(RBTNode& tree)
  {
  if (tree == NULL)
  return;

  if (tree->left != NULL)
  destroy(tree->left);
  if (tree->right != NULL)
  destroy(tree->right);

  delete tree;
  tree = NULL;
  }

template
void RBTree::destroy()
{
destroy(mRoot);
}

/*

• 打印"二叉查找树"
• key -- 节点的键值
• direction -- 0，表示该节点是根节点;

•           -1，表示该节点是它的父结点的左孩子;
  

•            1，表示该节点是它的父结点的右孩子。
  

/
template
void RBTree::print(RBTNode tree, T key, int direction)
{
if (tree != NULL)
{
if (direction == 0) // tree是根节点
cout << setw(2) << tree->key << "(B) is root" << endl;
else // tree是分支节点
cout << setw(2) << tree->key << (rb_is_red(tree) ? "(R)" : "(B)") << " is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;

    print(tree->left, tree->key, -1);
    print(tree->right, tree->key, 1);
}

}

template
void RBTree::print()
{
if (mRoot != NULL)
print(mRoot, mRoot->key, 0);
}

int main()
{
system("chcp 65001");
int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
int check_insert = 1; // "插入"动作的检测开关(0，关闭；1，打开)
int check_remove = 0; // "删除"动作的检测开关(0，关闭；1，打开)
int i;
int ilen = (sizeof(a)) / (sizeof(a[0]));
RBTree* tree = new RBTree();

cout << "== 原始数据: ";
for (i = 0; i < ilen; i++)
    cout << a[i] << " ";
cout << endl;

for (i = 0; i < ilen; i++)
{
    tree->insert(a[i]);
    // 设置check_insert=1,测试"添加函数"
    if (check_insert)
    {
        cout << "== 添加节点: " << a[i] << endl;
        cout << "== 树的详细信息: " << endl;
        tree->print();
        cout << endl;
    }

}

cout << "== 前序遍历: ";
tree->preOrder();

cout << "\n== 中序遍历: ";
tree->inOrder();

cout << "\n== 后序遍历: ";
tree->postOrder();
cout << endl;

cout << "== 最小值: " << tree->minimum() << endl;
cout << "== 最大值: " << tree->maximum() << endl;
cout << "== 树的详细信息: " << endl;
tree->print();

// 销毁红黑树
tree->destroy();
delete tree;

}
/*

*/

[whoamiR]

有关红黑树和一些算法导论中的数据结构的内容可以查看我的项目 https://github.com/whoamiR/the-Algorithms-on-Introduction-to-Algorithms/tree/main/Advanced_Data_Structure

[clxisclx]

感觉挺清楚的，期待加入红黑树

[KLYkl]

我个人对平衡二叉树旋转的理解：
（1）如果失衡的节点的树是一颗左偏树，得看他左子树：
①如果左子树是一颗左偏树或者平衡树，那么使用对失衡节点右旋的方法。
②如果左子树是一颗右偏树，那么对左子节点进行左旋，然后对失衡节点进行右旋。（我的理解是，先把这颗左子树是偏右的树左旋转变成左子树是偏左的树或者平衡的树，然后就可以使用①的方式来对失衡节点旋转，即右旋。）
（2）同理，如果失衡的节点的树是一颗右偏树，得看他右子树：
①如果右子树是一颗右偏树或者平衡树，那么使用对失衡节点左旋的方法。
②如果右子树是一颗左偏树，那么对右子节点进行右旋，然后对失衡节点进行左旋。（我的理解是，先把这颗右子树是偏左的树右旋转变成右子树是偏右的树或者平衡的树，然后就可以使用①的方式来对失衡节点旋转，即左旋。）
这个是我根据（表 7-3 四种旋转情况的选择条件）的个人理解，如果我的理解有问题，请大佬慷慨指出，认真向您学习，谢谢。