高级数据结构和算法5：2-3查找树、红黑树

完美平衡（Perfect balance）：每条从根节点到叶节点的路径的高度都是一样的（Every path from root to leaf has same length）。也就是每个节点的平衡因子为0.

1. 2-3查找树

和二叉树不一样，2-3树每个节点保存1个或者2个的key。对于普通的2节点(2-node)，要有1个key和左右两个子节点。对应3节点(3-node)，要有两个Key和三个子节点。

No.	名称	key个数	子节点个数
1	2节点(2-node)	1	2（二叉）
2	3节点(3-node)	2	3（三叉）`

2-3查找树的定义如下：

要么为空，要么：
对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key有效，有节点也是一个2-3节点，所有的值比key要大。
对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。

如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。

操作

查找

2-3树的查找和二叉查找树类似，要确定一个树是否属于2-3树，我们首先和其跟节点进行比较，如果相等，则查找成功；否则根据比较的条件，在其左中右子树中递归查找，如果找到的节点为空，则未找到，否则返回。

插入

往一个2-node节点插入
往2-3树中插入元素和BST插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。
如果查找后未找到的节点是一个2-node节点，只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。
往一个3-node节点插入
往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况。
只包含一个3-node节点

Insert into a single 3-node

节点是3-node，父节点是2-node
和第一种情况一样，我们也可以将新的元素插入到3-node节点中，使其成为一个临时的4-node节点，然后，将该节点中的中间元素提升到父节点即2-node节点中，使其父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置。

节点是3-node，父节点也是3-node

当插入的节点是3-node的时候，将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。

根节点分裂

当根节点到字节点都是3-node节点的时候，这是如果要在字节点插入新的元素的时候，会一直查分到跟节点，在最后一步的时候，跟节点变成了一个4-node节点，这个时候，就需要将跟节点查分为两个2-node节点，树的高度加1。

本地转换

将一个4-node拆分为2-3node涉及到6种可能的操作。这4-node可能在跟节点，也可能是2-node的左子节点或者右子节点。或者是一个3-node的左，中，右子节点。所有的这些改变都是本地的，不需要检查或者修改其他部分的节点。所以只需要常数次操作即可完成2-3树的平衡。

2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。

性质

这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。

AVL与2-3查找树比较

2. 红黑树(Red-Black Tree)

红黑树是一种具有红色和黑色链接的BST。

《算法导论》中对红黑树的定义（针对的是节点颜色）：

节点是红色或黑色。

根节点和叶子节点（NIL节点）都是黑色。

每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点，也就是没有5-node)

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。(黑色节点完美平衡)

《算法》中对红黑树的定义（针对的是线的颜色）：

红色的线永远是左侧链接。（强行的规定）

没有一个节点同时链了两条红色的线。（也就是没有4-node）

任何从根到叶子节点的路径上有相同颜色的黑线。(黑线节点完美平衡)

红黑树

红黑树节点颜色


int Depth(Node* node){
    if(NULL == node) return 0;
    return max(Depth(node->right),Depth(node->left))+(IsRed(node)?0:1);
}
bool Check(Node* node,int maxKey,int minKey){
    if(NULL == node) return true;
    if(IsRed(node->right)) return false;
    if(IsRed(node->left) && IsRed(node->left->left)) return false;
    if(Depth(node->right) != Depth(node->left)) return false;
    if(node->key > maxKey) return false;
    if(node->key < minKey) return false;
    return Check(node->right,maxKey,node->key) && Check(node->left,node->key,minKey);
}
bool Check(Node* node){
    return Check(node,INT_MAX,INT_MIN);
}

背景

2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂。红黑树是一种简单实现2-3树的数据结构。

红黑树平衡

红黑树转2-3树

本质：红黑树是对2-3查找树进行编码。

对2-3查找树中的3-nodes节点添加额外的信息。
红黑树中将节点之间的链接分为两种不同类型。

红色链接：链接两个2-nodes节点来表示一个3-nodes节点。
黑色链接：链接普通的2-3节点。

使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。

从边的颜色到节点的颜色
BST的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。

红节点的含义

操作

平衡化

与AVL相同，红黑树也需要通过旋转保持平衡；不同的是旋转后，需要改变节点的颜色。

旋转(Rotate)

左旋:将一个向右倾斜的红色链接旋转为向左链接,将红线链接的两个节点中的一个较大的节点移动到根节点上。

左旋

右旋:将一个向左倾斜的红色链接旋转为向右链接,将红线链接的两个节点中的一个较大的节点移动到根节点上。

暂时的旋转

旋转颜色变化规律：上升节点(旋转节点)变为原来父节点的颜色，下降节点变为红色。

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 获取旋转节点
    root->right = pivot->left; // 旋转节点的子节点替换父节点的旋转节点
    pivot->left = root;        // 旋转节点父节点做旋转节点子节点

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋转节点 
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 获取旋转节点
    root->left = pivot->right; // 旋转节点的子节点替换父节点的旋转节点
    pivot->right = root;       // 旋转节点父节点做旋转节点子节点

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋转节点
}

AVL和红黑树比较

颜色反转(Color Flip)
当出现一个临时的4-node的时候，即一个节点的两个子节点均为红色。子节点颜色为黑色，父节点的颜色设置为红色；反之亦然。

颜色反转

// 颜色翻转：两个子节点由红色变为黑色，父节点由黑色变成红色
// 两个子节点由红色变为黑色，父节点由黑色变成红色
// 两个子节点由黑色变为红色，父节点由红色变成黑色
Node* FlipColor(Node* node){
    assert(NULL != node);
    cout<<"FlipColor"<<endl;
    if(RED == node->color){
        node->left->color = RED;
        node->right->color = RED;
        node->color = BLACK;
    }else{
        node->left->color = BLACK;
        node->right->color = BLACK;
        node->color = RED;
    }
    return node;
}

红节点转移(Move Red)

/*
 * 左移
 * 小写字母为红节点，大写字母为黑节点
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->right->left)){ // 从右子树借红结点，父结点和左结点转化成3结点
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小写字母为红节点，大写字母为黑节点
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->left->left)) node = RightRotate(node);// 从左子树借红结点，父结点和右结点转化成3结点
    return node;
}

红节点转移实质上形成一个5节点。

2-3树的平衡操作来对红黑树进行平衡操作

插入

一切为了平衡，树根到叶子节点的路径上黑边的个数(黑节点个数)决定平衡。
从上到下查找位置，插入节点为红叶子节点，然后从下到上回溯平衡。

往一个2-node节点底部插入新的节点
1. 按照BST遍历，新插入的节点标记为红色。为什么新插入节点是红色？为了保证插入后树是平衡的(每条分支黑边个数不发生改变)。
2. 如果新插入的节点在父节点的右子节点，则需要进行左旋操作

往一个2-node节点底部插入新的节点.png

往一个3-node节点底部插入新的节点
1. 插入的节点比现有的两个节点都大，新插入的节点连接到右边子树上，颜色反转。
2. 插入的节点比现有的两个节点都小，新插入的节点连接到最左侧，中间节点右旋，颜色反转。
3. 插入的节点的值位于两个节点之间，新节点插入到左侧节点的右子节点。先以中间节点左旋至情况2，再中间节点右旋，颜色反转。

往一个3-node节点底部插入新的节点

No.	值`key`的范围	操作
1	`a<b<key`	颜色反转
2	`key<a<b`	`b`右旋(变成情况1)，然后颜色反转
3	`a<key<b`	`a`左旋(变成情况2)，`b`右旋(变成情况1)，然后颜色反转

添加操作总结

3-node节点底部插入新的节点，可能会导致父节点不满足红黑树的特点(完美平衡)，可以从下往上回溯更新节点的颜色(与AVL判断平衡因子更新树高相似)，直到平衡。

3-node节点底部插入新的节点的连锁反应实例1

3-node节点底部插入新的节点的连锁反应实例2

步骤：

执行标准的二叉查找树插入操作，新插入的节点元素用红色标识。
如果需要对4-node节点进行旋转操作
如果需要，调用FlipColor方法将红色节点提升
如果需要，左旋操作使红色节点左倾。
在有些情况下，需要递归调用Case1 Case2，来进行递归操作。

平衡操作：

如果节点的右子节点为红色，且左子节点位黑色，则进行左旋操作
如果节点的左子节点为红色，并且左子节点的左子节点也为红色，则进行右旋操作
如果节点的左右子节点均为红色，则执行FlipColor操作，提升中间结点。

// 只有标志为红色的节点才是红节点(空节点也是黑节点)
bool IsRed(const Node* root){
    return NULL != root && RED == root->color; 
}
// 平衡
Node* Balance(Node* root){
    Node *res = root;
    if (IsRed(root->right) and !IsRed(root->left)) // 如果节点的右子节点为红色，且左子节点位黑色，则进行左旋操作
        res = LeftRotate(root);
    if (IsRed(root->left) and IsRed(root->left->left)) // 如果节点的左子节点为红色，并且左子节点的左子节点也为红色，则进行右旋操作
        res = RightRotate(root);
    if (IsRed(root->left) and IsRed(root->right)) // 如果节点的左右子节点均为红色，则执行FlipColor操作，提升中间结点。
        res = FlipColor(root);
    return res;
}
Node* InsertNode(Node*& node, int key){
    if(NULL == node) node = new Node(key,RED);
    if (key < node->key) node->left = InsertNode(node->left, key);
    else if (key > node->key) node->right = InsertNode(node->right,key);
    node = Balance(node); // 平衡
    return node;
}
// 插入
Node* Insert(Node*& node, int key){
    node = InsertNode(node,key);
    node->color = BLACK;// 根结点必须为黑结点
}

红黑树能够保证符号表的所有操作即使在最坏的情况下都能保证对数的时间复杂度，也就是树的高度。

升序插入构建红黑树

降序插入构建红黑树

随机插入构建红黑树

最坏情况
红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。红黑树的高度不超过2lgN

最坏情况

2-3 nodes树与RB树关系

2-3 nodes树中的4-node分裂成3个2-node，并让中间节点上移；等价于红黑树中的左右旋转；

2-3 nodes树中间节点上移与父节点融合过程；等价于红黑树中的反色操作。

查找

与BST一致。

// 查找
Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}

删除

删除需要保证删除节点是非2-node的叶子节点，即必须是3-node和4-node。所以查找过程需要把过程中的2-node转化成3-node和4-node，删除后，在把3-node和4-node还原。

/*
 * 左移
 * 小写字母为红节点，大写字母为黑节点
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->right->left)){ // 从右子树借红结点，父结点和左结点转化成3结点
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小写字母为红节点，大写字母为黑节点
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->left->left)) node = RightRotate(node);// 从左子树借红结点，父结点和右结点转化成3结点
    return node;
}

// 为了保证完美平衡，删除的叶子节点必须是3-node或者4-node
Node* RemoveNode(Node*& node, int key) {
    Node* res = NULL;
    if(NULL == node) return NULL;
    if (key < node->key) { // 左子树
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        node->left = RemoveNode(node->left, key);
    } else if(key > node->key) {
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        node->right = RemoveNode(node->right,key);
    } else if(key == node->key) {
        if(IsLeaf(node) && IsRed(node)) {
            delete node;
            return NULL;
        }
// #define DELETE_MIN
#ifdef DELETE_MIN
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        if(key == node->key) { // 借不到的情况
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = RemoveNode(node->right,p->key);
        } else {
            node->right = RemoveNode(node->right,key);
        }
#else
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        if(key == node->key) { // 借不到的情况
            Node* p = Maximum(node->left);
            node->key = p->key;
            node->left = RemoveNode(node->left,p->key);
        } else {
            node->left = RemoveNode(node->left, key);
        }
#endif
    }
    return Balance(node); // 平衡
}
// 删除
Node* Remove(Node*& node,int key){
    if(!IsRed(node->right) && !IsRed(node->left)) // 根节点左右子树不为黑节点
        node->color = RED; // 根节点暂时变为红节点
    node = RemoveNode(node,key);
    if(NULL != node) node->color = BLACK;
    return node;
}

小结

插入操作

No.	操作	目的	改变项	保持项	执行条件
1	左旋/右旋	调节平衡,使之符合红黑树规定	节点的位置和颜色	始终保持BST特点	红节点不满足红黑树规定
2	颜色反转	调节平衡,使之符合红黑树规定(等价于2-3树4节点差分)	改变节点的颜色	始终保持BST特点	红节点不满足红黑树规定

删除操作

No.	操作	目的	改变项	保持项	执行条件
1	左旋/右旋	旋转红节点到要删除的分支，便于后续删除	节点的位置和颜色	始终保持BST特点	删除右子树节点，左子树的根节点为红节点时。
2	颜色反转	增加可使用的红节点(等价于2-3树节点4节点组合)	改变节点的颜色	始终保持BST特点	左右子节点为黑节点时
3	红节点移动	移动红节点到要删除的分支，便于后续删除	节点的位置和颜色	始终保持BST特点	向下查找删除节点，当前子树连续两个黑节点时。

完整代码

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

// 节点颜色
enum NodeColor{
    RED,  ///< 红节点
    BLACK ///< 黑节点
};

// 节点
struct Node{
    int key;        ///< 键
    Node *left;     ///< 左子节点
    Node *right;    ///< 右子节点
    NodeColor color;///< 节点颜色
    Node(int key,NodeColor color) 
    :key(key),left(NULL),right(NULL),color(color){}
};

// 最大键
Node* Maximum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->right) node = node->right;
    return node;
}

// 最小键
Node* Minimum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->left) node = node->left;
    return node;
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 获取旋转节点
    root->left = pivot->right; // 旋转节点的子节点替换父节点的旋转节点
    pivot->right = root;       // 旋转节点父节点做旋转节点子节点

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋转节点
}

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 获取旋转节点
    root->right = pivot->left; // 旋转节点的子节点替换父节点的旋转节点
    pivot->left = root;        // 旋转节点父节点做旋转节点子节点

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋转节点 
}

// 颜色翻转：两个子节点由红色变为黑色，父节点由黑色变成红色
// 两个子节点由红色变为黑色，父节点由黑色变成红色
// 两个子节点由黑色变为红色，父节点由红色变成黑色
Node* FlipColor(Node* node){
    assert(NULL != node);
    cout<<"FlipColor"<<endl;
    if(RED == node->color){
        node->left->color = RED;
        node->right->color = RED;
        node->color = BLACK;
    }else{
        node->left->color = BLACK;
        node->right->color = BLACK;
        node->color = RED;
    }
    return node;
}

// 只有标志为红色的节点才是红节点(空节点也是黑节点)
bool IsRed(const Node* root){
    return NULL != root && RED == root->color; 
}

// 平衡
Node* Balance(Node* root){
    Node *res = root;
    if (IsRed(root->right) and !IsRed(root->left)) // 如果节点的右子节点为红色，且左子节点位黑色，则进行左旋操作
        res = LeftRotate(root);
    if (IsRed(root->left) and IsRed(root->left->left)) // 如果节点的左子节点为红色，并且左子节点的左子节点也为红色，则进行右旋操作
        res = RightRotate(root);
    if (IsRed(root->left) and IsRed(root->right)) // 如果节点的左右子节点均为红色，则执行FlipColor操作，提升中间结点。
        res = FlipColor(root);
    return res;
}

// 三个核心操作

Node* InsertNode(Node*& node, int key){
    if(NULL == node) node = new Node(key,RED);
    if (key < node->key) node->left = InsertNode(node->left, key);
    else if (key > node->key) node->right = InsertNode(node->right,key);
    node = Balance(node); // 平衡
    return node;
}
// 插入
Node* Insert(Node*& node, int key){
    node = InsertNode(node,key);
    node->color = BLACK;// 根结点必须为黑结点
}

// 查找
Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}

/*
 * 左移
 * 小写字母为红节点，大写字母为黑节点
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->right->left)){ // 从右子树借红结点，父结点和左结点转化成3结点
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小写字母为红节点，大写字母为黑节点
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父结点、左结点、右结点组成4结点
    if(IsRed(node->left->left)) node = RightRotate(node);// 从左子树借红结点，父结点和右结点转化成3结点
    return node;
}

// 为了保证完美平衡，删除的叶子节点必须是3-node或者4-node
Node* RemoveNode(Node*& node, int key) {
    Node* res = NULL;
    if(NULL == node) return NULL;
    if (key < node->key) { // 左子树
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        node->left = RemoveNode(node->left, key);
    } else if(key > node->key) {
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        node->right = RemoveNode(node->right,key);
    } else if(key == node->key) {
        if(IsLeaf(node) && IsRed(node)) {
            delete node;
            return NULL;
        }
// #define DELETE_MIN
#ifdef DELETE_MIN
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        if(key == node->key) { // 借不到的情况
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = RemoveNode(node->right,p->key);
        } else {
            node->right = RemoveNode(node->right,key);
        }
#else
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        if(key == node->key) { // 借不到的情况
            Node* p = Maximum(node->left);
            node->key = p->key;
            node->left = RemoveNode(node->left,p->key);
        } else {
            node->left = RemoveNode(node->left, key);
        }
#endif
    }
    return Balance(node); // 平衡
}
// 删除
Node* Remove(Node*& node,int key){
    if(!IsRed(node->right) && !IsRed(node->left)) // 根节点左右子树不为黑节点
        node->color = RED; // 根节点暂时变为红节点
    node = RemoveNode(node,key);
    if(NULL != node) node->color = BLACK;
    return node;
}
/////////////////////////////////////////////////////////////
ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key<< '[' << (curr->color==RED?'R':'B') <<']';
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}
void TestInsert(Node*& root){
    Insert(root,1);
    Insert(root,2);
    Insert(root,3);
    Insert(root,4);
    Insert(root,5);
    cout << *root << endl;
}
void TestSearch(Node* root,int key){
    cout <<"Search " << key << ":" << Search(root,key) << endl;
}
void TestRemove(Node*& root,int key){
    root = Remove(root, key);
    cout <<"Remove " << key << ":" ;
    if(NULL != root) cout << *root << endl;
    else cout << "#" << endl;
}
void TestMax(Node* root){
    Node* maxNode = Maximum(root);
    cout << "Max:"<< maxNode->key <<":"<< maxNode <<endl;
}
void TestMin(Node* root){
    Node* minNode = Minimum(root);
    cout << "Min:"<< minNode->key <<":"<< minNode <<endl;
}

int main(){
    Node* root = NULL;
    TestInsert(root);
    TestSearch(root,1);
    TestSearch(root,2);
    TestSearch(root,3);
    TestSearch(root,4);
    TestSearch(root,5);
    TestSearch(root,6);
    TestSearch(root,7);
    TestSearch(root,8);
    TestMax(root);
    TestMin(root);

    TestRemove(root, 2);
    TestRemove(root, 5);
    TestRemove(root, 4);
    TestRemove(root, 3);
    TestRemove(root, 1);
    // TestRemove(root,1);
    // TestRemove(root,2);
    // TestRemove(root,3);
    // TestRemove(root,4);
    // TestRemove(root,5);
}

最后编辑于：2021.07.27 15:45:28

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,753评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,668评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,090评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,010评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,054评论 6赞 395
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,806评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,484评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,380评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,873评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,021评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,158评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,838评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,499评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,044评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,159评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,449评论 3赞 374
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,136评论 2赞 356