数据结构七红黑树

听说红黑树很难，不知道究竟有多难，现在来试一下。

参考资料

定义

红黑树是一个自平衡的二叉查找树，每一个结点增加一个标识结点颜色的位（红色或者黑色），通过对任何一条从根节点到叶子的路径上结点着色方式的限制，红黑树保证不存在一条路径会比其他路径长两倍。红黑树不保证绝对的平衡。

nil:指的是红黑树的叶子，但是红黑树的叶子别的树不同，这里的叶子指的是空指针域，可以看作每一个child指针若为null则指向空指针域nil

性质

每一个结点是红的或者黑的。
根节点是黑色的。
空指针域为黑色的。即NULL指针看作黑色。
红色结点的孩子都是黑色的。
对于每一个结点，到以其为根的叶子结点所经过的黑色结点的数目相同。（这里的叶子结点指的是空指针域，以哨兵装入其内）

算法

左旋

将当前结点旋转为其右孩子的左孩子，并将其右孩子的左孩子设置为当前节点的右孩子。

右旋

将当前结点旋转为其左孩子的右孩子，并将其左孩子的右孩子设置为当前节点的左孩子。

插入

首先假设插入的结点为红色。因为红色结点不会影响红黑树这一条性质 对于每一个结点，到其叶子结点的所有路径上黑色结点的数目相同。

插入的结点为根节点或者父节点为黑色则直接插入即可，因为这种情况下不会影响红黑树的成立。

当插入的结点的父节点为红色的是候分以下两种情况。

父节点和叔叔都是红色的。
父节点是红色，叔叔结点是黑色的或者叔叔结点不存在。

对于第一种情况，这样处理：

将父亲和叔叔设置为黑色，将祖父设置为红色递归处理父节点。
祖父节点必为黑色，这种情况下破坏了性质4，红色结点的孩子都是黑色，所以需要将父节点进行变色为黑色来满足这条限制，但是这样的话祖父节点到其下叶节点的黑色节点数量就不一样了，所以顺便也将叔叔结点变为黑色。这样以祖父节点为根的红黑树平衡了，但是由于叔叔和父亲结点都变成了黑色，所以祖父的祖先节点就不平衡了，因为这导致了祖父这一条路上的黑色结点数量加一了，但是又考虑到祖父节点为黑色，现在父亲结点和叔叔又都是黑色，所以顺势将祖父结点变为红色不就可以了吗。于是祖父这一棵树完全平衡了，只有一点就是祖父的颜色可能不对劲，曾祖父如果是红色的话就不行，所以将祖父当作当前的结点递归进行处理。这种多个变量同是作用并且恰如其分地造成想要的结果真是精妙呀，不知道这棵树的发明者是怎样想到的。

对于第二种情况（第一种情况递归之后也可能进入这种情况），父亲和叔叔都是红色，分为以下四种情况。分别进行处理

祖父结点必为黑色,所以需要找到一种方法使得祖父节点这棵树满足条件而且变化要少。想到可以以父节点代替祖父。这样颜色和黑色结点数量都满足了。

父节点是祖父节点的左孩子
1. 当前节点是父节点的左孩子。父节点设为黑色祖父节点设为红色对祖父节点进行右旋
2. 当前节点是父节点的右孩子。将父节点设为当前节点并进行左旋。递归进行。（其实就是转化为上面这种情况）
父节点是祖父节点的右孩子
1. 当前节点是父节点的左孩子。将父节点设为当前结点并进行右旋递归（其实就是转化为下面这种情况）
2. 当前节点是父节点的右孩子。父节点设为黑色祖父设为红色并对祖父进行左旋

删除

在红黑树中当结点为空是，其颜色看作黑色。

首先按照二叉搜索树一样进行删除，之后进行fix_up即可。

BSTree 删除方法：

若删除结点时叶子的话，直接删除。
若有左孩子，则使用左子树的最大值代替，递归直到叶子。
若有右孩子，则使用右子树的最小值代替，递归直到叶子。

fix_up: 现在我们已经将要删除的结点换为一个叶子节点了。记为 del_tree 但是在正式删除之前还需要先旋转着色确保删除之后树的平衡记当前正在处理平衡的结点为 cur_tree

结点为根节点，直接返回。结点为红色，设为黑色，直接返回。若兄弟结点为空，则如果父结点为红色则父结点变为黑色，直接返回。若父结点为黑色，则递归处理父结点。
结点为黑色
1. 结点为其父节点的左孩子
  1. 兄弟结点是红色
    
    父节点设为红色兄弟结点设为黑色对父节点进行左旋递归处理当前结点
  2. 兄弟结点为黑色
    1. 兄弟结点的右孩子为红色，左孩子任意
      
      将兄弟颜色设为为父节点的颜色父节点设为黑色兄弟结点的右孩子设为黑色对父节点进行左旋结束
    2. 兄弟结点的右孩子为黑色或者不存在，左孩子为红色
      
      兄弟设为红色兄弟的左孩子设为黑色对兄弟结点进行右旋此时得到上面这种情况当前处理结点不变递归
    3. 兄弟结点的孩子都是黑色
      
      将兄弟结点设为红色父节点设为当前结点递归
2. 结点为其父节点的右孩子
  1. 兄弟结点为红色
    
    父节点设为红色兄弟结点设为黑色对父节点进行右旋递归处理当前结点
  2. 兄弟结点为黑色
    1. 兄弟结点的左孩子为红色右孩子任意
      
      将兄弟结点设为父节点的颜色父节点设为黑色兄弟结点的左孩子对父节点进行右旋结束
    2. 兄弟结点的左孩子为黑或者不存在，右孩子为红
      
      兄弟结点设为红色兄弟结点的右孩子设为黑色对兄弟结点进行左旋当前处理结点不变递归
    3. 兄弟结点的孩子都是黑色
      
      兄弟结点设为红色父节点设为当前结点递归

代码实现

接口声明

// 红黑树

#ifndef BRTREE_H
#define BRTREE_H

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <deque>
#include <vector>
#include <iostream>

enum COLOR
{
    RED,
    BLACK
};

typedef struct BRTREE
{
    int key;
    struct BRTREE *parent;
    struct BRTREE *left;
    struct BRTREE *right;
    enum COLOR color;
} * BRTree, BRTree_Node;

BRTree init(BRTree tree);

BRTree create_node(int key, BRTree parent, BRTree left, BRTree right, enum COLOR color);

void preorder(BRTree tree);
void inorder(BRTree tree);
void postorder(BRTree tree);

BRTree search(BRTree tree, int key);

//将树层序遍历打印出来
void print_brtree(BRTree tree, int dir, int last_key);

BRTree insert(BRTree tree, int key);

BRTree fix_up(BRTree tree, BRTree tree_cur);

//左旋
BRTree l_rotation(BRTree tree, BRTree cur);
//右旋
BRTree r_rotation(BRTree tree, BRTree cur);

BRTree delete_brtree(BRTree tree, int key);

BRTree fix_up_del(BRTree tree, BRTree cur_tree);
BRTree delete_node(BRTree tree, BRTree del_tree);
BRTree successor(BRTree tree);
BRTree maximum(BRTree tree);
BRTree minimum(BRTree tree);
//从 leaf 到 root 的路径上的black结点数量。
int black_num(BRTree root, BRTree leaf);
void save_balck_num(BRTree root, BRTree leaf, std::vector<int> &balck);
bool check_balck_num_valid(BRTree tree);
void destroy(BRTree tree);

#endif

接口实现

#include "BRTree.h"

BRTree init(BRTree tree)
{
    return NULL;
}

BRTree create_node(int key = -1, BRTree parent = NULL, BRTree left = NULL, BRTree right = NULL, enum COLOR color = RED)
{
    BRTree tree = (BRTree)malloc(sizeof(struct BRTREE));
    tree->color = color;
    tree->key = key;
    tree->left = left;
    tree->right = right;
    tree->parent = parent;
    return tree;
}

void preorder(BRTree tree)
{
    if (tree)
    {
        printf("%d ", tree->key);
        preorder(tree->left);
        preorder(tree->right);
    }
}
void inorder(BRTree tree)
{
    if (tree)
    {

        inorder(tree->left);
        //if (tree->left && tree->right && tree->left->color == RED && tree->right->color == RED && tree->color == RED)
        printf("%d, ", tree->key);
        inorder(tree->right);
    }
}
void postorder(BRTree tree)
{
    if (tree)
    {

        postorder(tree->left);
        postorder(tree->right);
        printf("%d ", tree->key);
    }
}

BRTree search(BRTree tree, int key)
{
    if (tree)
    {
        if (key == tree->key)
            return tree;
        if (key < tree->key)
            return search(tree->left, key);
        if (key > tree->key)
            return search(tree->right, key);
    }
    return tree;
}
//将树层序遍历打印出来
void print_brtree(BRTree tree, int dir, int last_key)
{
    if (!tree && dir == 0)
    {
        printf("树空\n");
    }
    if (tree)
    {
        //根节点
        if (dir == 0)
        {
            printf("%d root", tree->key);
            if (tree->color == RED)
                printf(" RED\n");
            else
                printf(" BLACK\n");
            print_brtree(tree->left, -1, tree->key);
            print_brtree(tree->right, 1, tree->key);
        }
        //左孩子
        if (dir == -1)
        {
            printf("%d is %d 's left", tree->key, last_key);
            if (tree->color == RED)
                printf(" RED\n");
            else
                printf(" BLACK\n");
            print_brtree(tree->left, -1, tree->key);
            print_brtree(tree->right, 1, tree->key);
        }
        //右孩子
        if (dir == 1)
        {
            printf("%d is %d 's right", tree->key, last_key);
            if (tree->color == RED)
                printf(" RED\n");
            else
                printf(" BLACK\n");
            print_brtree(tree->left, -1, tree->key);
            print_brtree(tree->right, 1, tree->key);
        }
    }
}

BRTree insert(BRTree tree, int key)
{
    //首先生成一个结点，染成红色并按照 BStree一样插入进去。
    BRTree pos = tree;
    BRTree tree_to_insert = create_node(key);
    //查找插入位置
    //空树
    if (tree == NULL)
    {
        //根节点的颜色为黑色
        tree_to_insert->color = BLACK;
        return tree_to_insert;
    }
    //非空树
    pos = tree;
    while (pos)
    {
        if (key == pos->key)
        {
            return tree;
        }
        //左
        if (key < pos->key)
        {
            if (pos->left == NULL)
            {
                pos->left = tree_to_insert;
                tree_to_insert->parent = pos;
                break;
            }
            else
                pos = pos->left;
        }
        //右
        if (key > pos->key)
        {
            if (pos->right == NULL)
            {
                pos->right = tree_to_insert;
                tree_to_insert->parent = pos;
                break;
            }
            else
                pos = pos->right;
        }
    }
    //插入成功，进行调整到合格的红黑树。
    return fix_up(tree, tree_to_insert);
}

BRTree fix_up(BRTree tree, BRTree tree_cur)
{
    //调整树直到符合红黑树的要求。
    if (!tree || !tree_cur)
        return tree;
    //cur为根节点将其颜色变为黑色直接返回
    if (tree_cur->parent == NULL)
    {
        tree_cur->color = BLACK;
        return tree;
    }
    //父节点是根节点则直接返回
    if (tree_cur->parent->parent == NULL)
        return tree;
    //1. 父节点是黑色 直接返回。
    if (tree_cur->parent->color == BLACK)
        return tree;
    //2. 父节点是红色
    if (tree_cur->parent->color == RED)
    {
        BRTree grandpa = tree_cur->parent->parent;

        //叔叔结点存在才可能是红色，否则为黑色
        if (grandpa->left && grandpa->right)
        {
            //1. 父节点和叔叔结点都是红色
            if (grandpa->left->color == RED && grandpa->right->color == RED)
            {
                //将父节点 叔叔 设为黑色 将祖父节点设为红色，递归继续处理祖父结点
                grandpa->left->color = BLACK;
                grandpa->right->color = BLACK;
                grandpa->color = RED;
                return fix_up(tree, grandpa);
            }
            //2. 父节点红 和叔叔结点黑
            else if (grandpa->left->color == BLACK || grandpa->right->color == BLACK)
            {
                // 当前结点的父节点是祖父节点的左孩子
                if (tree_cur->parent->parent->left == tree_cur->parent)
                {
                    // 当前结点是父节点的左孩子
                    if (tree_cur->parent->left == tree_cur)
                    {
                        // 父节点设为黑色 祖父节点设为红色 对祖父节点进行右旋
                        tree_cur->parent->color = BLACK;
                        tree_cur->parent->parent->color = RED;
                        tree = r_rotation(tree, tree_cur->parent->parent);
                        return tree;
                    }
                    // 当前结点是父节点的右孩子
                    if (tree_cur->parent->right == tree_cur)
                    {
                        // 将父节点设为当前节点并进行左旋。递归进行。
                        tree_cur = tree_cur->parent;
                        tree = l_rotation(tree, tree_cur);
                        return fix_up(tree, tree_cur);
                    }
                }
                // 当前结点的父节点是祖父节点的右孩子
                else if (tree_cur->parent->parent->right == tree_cur->parent)
                {
                    // 当前结点是父节点的左孩子
                    if (tree_cur->parent->left == tree_cur)
                    {
                        // 将父节点设为当前结点并进行右旋 递归
                        tree_cur = tree_cur->parent;
                        tree = r_rotation(tree, tree_cur);
                        return fix_up(tree, tree_cur);
                    }
                    // 当前结点是父节点的右孩子
                    if (tree_cur->parent->right == tree_cur)
                    {
                        // 父节点设为黑色 祖父设为红色 并对祖父进行左旋
                        tree_cur->parent->color = BLACK;
                        tree_cur->parent->parent->color = RED;
                        tree = l_rotation(tree, tree_cur->parent->parent);
                        return tree;
                    }
                }
            }
        }
        //叔叔结点不存在 为黑色
        else
        {
            // 当前结点的父节点是祖父节点的左孩子
            if (tree_cur->parent->parent->left == tree_cur->parent)
            {
                // 当前结点是父节点的左孩子
                if (tree_cur->parent->left == tree_cur)
                {
                    // 父节点设为黑色 祖父节点设为红色 对祖父节点进行右旋
                    tree_cur->parent->color = BLACK;
                    tree_cur->parent->parent->color = RED;
                    tree = r_rotation(tree, tree_cur->parent->parent);
                    return tree;
                }
                // 当前结点是父节点的右孩子
                if (tree_cur->parent->right == tree_cur)
                {
                    // 将父节点设为当前节点并进行左旋。递归进行。
                    tree_cur = tree_cur->parent;
                    tree = l_rotation(tree, tree_cur);
                    return fix_up(tree, tree_cur);
                }
            }
            // 当前结点的父节点是祖父节点的右孩子
            else if (tree_cur->parent->parent->right == tree_cur->parent)
            {
                // 当前结点是父节点的左孩子
                if (tree_cur->parent->left == tree_cur)
                {
                    // 将父节点设为当前结点并进行右旋 递归
                    tree_cur = tree_cur->parent;
                    tree = r_rotation(tree, tree_cur);
                    return fix_up(tree, tree_cur);
                }
                // 当前结点是父节点的右孩子
                if (tree_cur->parent->right == tree_cur)
                {
                    // 父节点设为黑色 祖父设为红色 并对祖父进行左旋
                    tree_cur->parent->color = BLACK;
                    tree_cur->parent->parent->color = RED;
                    tree = l_rotation(tree, tree_cur->parent->parent);
                    return tree;
                }
            }
        }
    }
    return tree;
}
//左旋
BRTree l_rotation(BRTree tree, BRTree cur)
{
    if (!tree || !cur)
        return tree;
    //设置傀儡头节点使根节点是其左孩子
    BRTree preroot = create_node(-1, NULL, tree);
    tree->parent = preroot;
    //左旋 将当前结点旋转为其右孩子的左孩子，并将其右孩子的左孩子设置为当前节点的右孩子。
    BRTree root = cur;
    BRTree right = root->right;
    if (!right)
        return tree;
    if (root->parent->left == root)
        root->parent->left = right;
    else if (root->parent->right == root)
        root->parent->right = right;
    right->parent = root->parent;

    root->parent = right;
    root->right = right->left;
    if (right->left)
        right->left->parent = root;
    right->left = root;

    tree = preroot->left;
    tree->parent = NULL;
    free(preroot);
    return tree;
}
//右旋
BRTree r_rotation(BRTree tree, BRTree cur)
{
    if (!tree || !cur)
        return tree;
    //设置傀儡头节点使根节点是其左孩子
    BRTree preroot = create_node(-1, NULL, tree);
    tree->parent = preroot;
    //右旋 将当前结点旋转为其左孩子的右孩子，并将其左孩子的右孩子设置为当前节点的左孩子。
    BRTree root = cur;
    BRTree left = root->left;
    if (!left)
        return tree;
    if (root->parent->left == root)
        root->parent->left = left;
    else if (root->parent->right == root)
        root->parent->right = left;
    left->parent = root->parent;

    root->parent = left;
    root->left = left->right;
    if (left->right)
        left->right->parent = root;
    left->right = root;

    tree = preroot->left;
    tree->parent = NULL;
    free(preroot);
    return tree;
}

//删除
BRTree delete_brtree(BRTree tree, int key)
{
    BRTree del_tree = search(tree, key);
    if (!del_tree)
    {
        printf("删除失败 没有找到 %d\n", key);
        return tree;
    }
    //找到真正要删除的结点
    del_tree = delete_node(tree, del_tree);
    //删除前修正 确保删除后树平衡
    tree = fix_up_del(tree, del_tree);
    //删除del_tree
    if (!del_tree->parent)
    {
        free(del_tree);
        return NULL;
    }
    if (del_tree->parent->left == del_tree)
        del_tree->parent->left = NULL;
    if (del_tree->parent->right == del_tree)
        del_tree->parent->right = NULL;
    free(del_tree);
    return tree;
}
//删除修正 这里负责旋转，即确保删除后树平衡 但是不删除树
BRTree fix_up_del(BRTree tree, BRTree cur_tree)
{
    if (!cur_tree->parent)
        return tree;
    BRTree pa = cur_tree->parent;
    BRTree bro = pa->left == cur_tree ? pa->right : pa->left;
    //1. 结点为红色 设为黑色 直接删除
    if (cur_tree->color == RED)
    {
        cur_tree->color = BLACK;
        return tree;
    }
    //兄弟结点为空
    else if (!bro)
    {
        if (cur_tree->parent->color == RED)
        {
            cur_tree->parent->color = BLACK;
            return tree;
        }
        else
        {
            return fix_up_del(tree, cur_tree->parent);
        }
    }
    //当前结点为黑色
    else if (cur_tree->color == BLACK)
    {
        //当前结点是左孩子
        if (pa->left == cur_tree)
        {
            //兄弟结点为红
            if (bro->color == RED)
            {
                bro->color = BLACK;
                pa->color = RED;
                tree = l_rotation(tree, pa);
                //return tree;
                return fix_up_del(tree, cur_tree);
            }
            //兄弟结点为黑
            else if (bro->color == BLACK)
            {
                //兄弟结点的右子结点是红结点，左子结点任意颜色
                if (bro->right && bro->right->color == RED)
                {
                    bro->color = pa->color;
                    pa->color = BLACK;
                    bro->right->color = BLACK;
                    tree = l_rotation(tree, pa);
                    return tree;
                }
                //兄弟结点的右子结点为黑结点，左子结点为红结点
                else if ((bro->left && bro->left->color == RED) && (!bro->right || (bro->right && bro->right->color == BLACK)))
                {
                    bro->color = RED;
                    bro->left->color = BLACK;
                    tree = r_rotation(tree, bro);
                    return fix_up_del(tree, cur_tree);
                }
                else
                {
                    bro->color = RED;
                    cur_tree = pa;
                    return fix_up_del(tree, cur_tree);
                }
            }
        }
        //当前结点是右孩子
        if (pa->right == cur_tree)
        {
            //兄弟结点为红
            if (bro->color == RED)
            {
                bro->color = BLACK;
                pa->color = RED;
                tree = r_rotation(tree, pa);
                //return tree;
                return fix_up_del(tree, cur_tree);
            }
            //兄弟结点为黑
            else if (bro->color == BLACK)
            {
                //兄弟结点的左子结点是红结点，右子结点任意颜色
                if (bro->left && bro->left->color == RED)
                {
                    bro->color = pa->color;
                    pa->color = BLACK;
                    bro->left->color = BLACK;
                    tree = r_rotation(tree, pa);
                    return tree;
                }
                //兄弟结点的左子结点为黑结点，右子结点为红结点
                else if (bro->right && bro->left && bro->left->color == BLACK && bro->right->color == RED)
                {
                    bro->color = RED;
                    bro->right->color = BLACK;
                    tree = l_rotation(tree, bro);
                    return fix_up_del(tree, cur_tree);
                }
                else
                {
                    bro->color = RED;
                    cur_tree = pa;
                    return fix_up_del(tree, cur_tree);
                }
            }
        }
    }
    return tree;
}
//删除结点 返回最后删除的结点
BRTree delete_node(BRTree tree, BRTree del_tree)
{

    //1. 叶节点 直接删除
    if (!del_tree->left && !del_tree->right)
    {
        return del_tree;
    }
    //若右左孩子 使用左子树中最大的
    else if (del_tree->left)
    {
        BRTree su = maximum(del_tree->left);
        del_tree->key = su->key;
        return delete_node(tree, su);
    }
    //若有右子树 使用右子树中最小的
    else if (del_tree->right)
    {
        BRTree su = minimum(del_tree->right);
        del_tree->key = su->key;
        return delete_node(tree, su);
    }
    return del_tree;
}
BRTree successor(BRTree tree)
{
    if (!tree)
        return NULL;
    //若有右孩子，则取右孩子的最小值
    return minimum(tree->right);
    //没有右孩子向上遍历直到为父节点的左孩子，返回父节点 若父节点为空则返回空
    while (tree && tree->parent->right == tree)
    {
        tree = tree->parent;
    }
    if (!tree)
        return tree;
    else
        return tree->parent;
}
BRTree maximum(BRTree tree)
{
    if (!tree)
        return tree;
    while (tree->right)
    {
        tree = tree->right;
    }
    return tree;
}

BRTree minimum(BRTree tree)
{
    if (!tree)
        return tree;
    while (tree->left)
    {
        tree = tree->left;
    }
    return tree;
}
//从 leaf 到 root 的路径上的black结点数量。
int black_num(BRTree root, BRTree leaf)
{
    if (!leaf || !root)
        return 0;
    int count = root->color == BLACK ? 1 : 0;
    while (leaf != root)
    {
        if (leaf->color == BLACK)
            count++;
        leaf = leaf->parent;
    }
    return count;
}
//保存一棵树到其所有叶子的黑色节点数量
void save_balck_num(BRTree root, BRTree leaf, std::vector<int> &balck)
{
    if (leaf)
    {
        save_balck_num(root, leaf->left, balck);
        if (!leaf->right && !leaf->left)
            balck.push_back(black_num(root, leaf));
        save_balck_num(root, leaf->right, balck);
    }
}

bool check_balck_num_valid(BRTree tree)
{
    if (tree)
    {
        std::vector<int> v;
        save_balck_num(tree, tree, v);
        for (int i = 0; i <= v.size() - 1; i++)
            if (v.at(i) != v.at(0))
                return false;
        return check_balck_num_valid(tree->left);

        return check_balck_num_valid(tree->right);
    }
    return true;
}

void destroy(BRTree tree);

接口测试

#include "BRTree.cpp"
#include <vector>
#define MAX_NUM 10000

#define RANGE 1000000

int test()
{
    std::vector<int> v; //= {91, 23, 74, 26, 15, 94, 13, 21, 10, 52, 60, 92, 73, 8, 47, 69, 80, 97, 48, 55};
    BRTree tree;
    tree = init(tree);

    srand(time(NULL));

    for (int i = 0; i <= MAX_NUM - 1; i += 1)
    {
        int key = rand() % RANGE;
        //int key = v.at(i);
        if (!search(tree, key))
        {
            v.push_back(key);
            tree = insert(tree, key);
        }
    }
    //printf("\n");
    //print_brtree(tree, 0, -1);
    //printf("\n");
    //inorder(tree);
    //printf("\n");

    for (int i = 0; i <= v.size() - 1; i += 1)
    {
        //printf("删除 %d \n", v.at(i));
        tree = delete_brtree(tree, v.at(i));
        //printf("\n");
        //print_brtree(tree, 0, -1);
        if (check_balck_num_valid(tree))
            ; //printf("-------------------------------------合法--------------------------------\n");
        else
        {
            printf("-------------------------------------不合法--------------------------------\n");
            for (int i = 0; i <= v.size() - 1; i++)
            {
                printf("%d, ", v.at(i));
            }

            exit(EXIT_FAILURE);
        }
    }
    //printf("\n");
    //print_brtree(tree, 0, -1);
    //printf("\n");
    //for (int i = 0; i <= v.size() - 1; i++)
    //{
    //printf("%d, ", v.at(i));
    //}
    return -1;
}

int main()
{
    while (1)
    {
        test();
        printf("text pass''''''''''''''''''''''''''''''''''''\n");
    }
}

数据结构 七 红黑树

数据结构 七 红黑树

定义

性质

算法

左旋

右旋

插入

删除

代码实现

接口声明

接口实现

接口测试

数据结构七红黑树

数据结构七红黑树