前言

　　11.1新的一月加油！这个购物狂欢的季节，一看，已囊中羞涩！赶紧来恶补一下红黑树和2-3树吧!红黑树真的算是大名鼎鼎了吧？即使你不了解它，但一定听过吧？下面跟随我来揭开神秘的面纱吧！

　　一、2-3树

　　1、抢了红黑树的光环？

　　今天的主角是红黑树，是无疑的，主角光环在呢！那2-3树又是什么鬼呢？学习2-3树不仅对理解红黑树有帮助，对理解B类树，也是有巨大帮助的，所以学习2-3树很必要！

　　2、基本性质

　　2-3树满足二分搜索树的基本性质，但节点可以存放一个元素或两个元素！如下图，就是2-3树：

　　

　　说明：2-3树一颗绝对平衡的树（绝对平衡：对于任意一个节点，左右子树高度相同）

　　3、维护绝对平衡

　　2-3树在插入过程中如何维护绝对平衡呢？进行画图演示，实在有点不好画，如下图：

　　

　　说明：

　　1、不能将新节点插入到空节点

　　　　因为那样如上图，就不满足绝对平衡了，所以可以将37和42合并，2-3支持3节点。

　　2、不支持4节点，进行拆分

　　　　再插入12时，也不能插入空节点，也要合并，但2-3树不支持4节点，所以进行进行拆分。

　　3、子节点达到3节点，合并到父节点

　　　　再依次插入18、6，达到4节点，进行拆分，但不符合绝对平衡了怎么办？将12和37合并，就形成了最后3节点的图了

　　总结：讲到这里，应该对2-3树如何维护绝对平衡，应该了解了吧？理解2-3树，对于再理解红黑树，是非常有帮助的，其实，它们有等价性的，接下来会说明的。

　　二、红黑树

　　1、红黑树和2-3树的等价性

　　也想达到像2-3树那样的绝对平衡，但2-3树的实现比较麻烦，所以产生了红黑树；那么,红黑树和2-3树有怎么样的等价性呢？如下图：

　　

　　说明：红黑树最开始想用红线区别b、c，但实现起来比较困难，然后用红黑来表示节点，就比较好实现了！

　　红黑树和2-3树总体对比图，可以参考一下：

　　

　　2、红黑树5个重要性质

　　1、引自《算法导论》

　　红黑树有五个重要性质，引自算法界一本圣洁《算法导论》中的内容，如下：

　　

　　是不是看着有点晕，下面我进行解释。

　　2、5个重要性质

　　1、每一个节点或者红色的，或是黑色的

　　2、根节点是黑色的

　　3、每一个叶子节点（最后的空节点）是黑色的

　　4、如果一个节点是红色的，那么它的孩子节点都是黑色的

　　5、从任意节点到叶子节点，经过的黑色节点是一样的

　　

　　解释：最重要的性质是第五条，前4条在理解2-3树之后，就很好理解了，第5条性质说明了：红黑树是保持“黑平衡”的二叉树；

严格意义上来说，红黑树不是平衡二叉树，最大高度：2logn，但是时间复杂度仍然是O（logn），因为2是常数，但比AVL树查询要稍微慢一些。

　　三、红黑树添加元素

　　红黑树添加元素，比较繁琐，因为要保持上面的五个性质，要不然就不是红黑树了；

　　1、保持根节点为节点

　　红黑树的节点类也可以从二分搜索树上进行修改，但要新增“color”成员变量，来标注节点颜色，节点类如下：

template<typename Key, typename Value>

class RBTree {

private:

    static const bool RED = true;

    static const bool BLACK = false;

    struct Node {

        Key key;

        Value value;

        Node *left;

        Node *right;

        bool color;

        Node(Key key, Value value) {

            this->key = key;

            this->value = value;

            this->left = this->right = nullptr;

            color = RED;　　//默认初始化为红色

        }

        Node(Node *node) {

            this->key = node->key;

            this->value = node->value;

            this->left = node->left;

            this->right = node->right;

            this->color = node->color;

        }

    };

    Node *root;

    int size;

}

　　因为红黑树性质1要求根节点为黑色，所以要保持根节点为黑色；

　　2、左旋转

　　像AVL树一样，红黑树也需要左旋和右旋，如下图就需要左旋转，因为“红色节点是左倾斜的”：

　　

　　说明：图中黑色字体标识黑色节点，红色表示红色节点，并演示了旋转过程，最后还要改变节点颜色。

　　3、左旋转代码实现

　　代码如下：

　　

Node *leftRotate(Node *node) {

        Node *x = node->right;

        node->right = x->left;

        x->left = node;

        x->color = node->color;

        node->color = RED;

        return x;

    }

　　4、颜色反转

　　下面这种情况就需要颜色反转，如下图：

　　

　　

　　5、颜色反转代码实现

　　代码如下：

void flipColors(Node *node) {

        node->color = RED;

        node->left->color = BLACK;

        node->right->color = BLACK;

    }

　　6、右旋转

　　下面情况需要右旋转，如下图：

　　

　　　　旋转之后，如下图：

　　

　　　7、右旋转代码如下

　　代码如下：

　　

Node *rightRotate(Node *node) {

        Node *x = node->left;

        node->left = x->right;

        x->right = node;

        x->color = node->color;

        node->color = RED;

        return x;

    }

　　8、总体流程图

　　

　　9、总体代码

　　总体代码如下，供参考和学习：

#ifndef RED_BLACK_TREE_RBTREE_H

#define RED_BLACK_TREE_RBTREE_H

#include <iostream>

#include <vector>

template<typename Key, typename Value>

class RBTree {

private:

    static const bool RED = true;

    static const bool BLACK = false;

    struct Node {

        Key key;

        Value value;

        Node *left;

        Node *right;

        bool color;

        Node(Key key, Value value) {

            this->key = key;

            this->value = value;

            this->left = this->right = nullptr;

            color = RED;

        }

        Node(Node *node) {

            this->key = node->key;

            this->value = node->value;

            this->left = node->left;

            this->right = node->right;

            this->color = node->color;

        }

    };

    Node *root;

    int size;

public:

    RBTree() {

        root = nullptr;

        size = ;

    }

    ~RBTree() {

        destroy(root);

    }

    int getSize() {

        return size;

    }

    int isEmpty() {

        return size == ;

    }

    bool isRed(Node *node) {

        if (node == nullptr) {

            return BLACK;

        }

        return node->color;

    }

    void add(Key key, Value value) {

        root = add(root, key, value);

        root->color = BLACK;

    }

    bool contains(Key key) {

        return getNode(root, key) != nullptr;

    }

    Value *get(Key key) {

        Node *node = getNode(root, key);

        return node == nullptr ? nullptr : &(node->value);

    }

    void set(Key key, Value newValue) {

        Node *node = getNode(root, key);

        if (node != nullptr) {

            node->value = newValue;

        }

    }

private:

    // 向以node为根的二叉搜索树中,插入节点(key, value)

    // 返回插入新节点后的二叉搜索树的根

    Node *add(Node *node, Key key, Value value) {

        if (node == nullptr) {

            size++;

            return new Node(key, value);

        }

        if (key == node->key) {

            node->value = value;

        } else if (key < node->key) {

            node->left = add(node->left, key, value);

        } else {

            node->right = add(node->right, key, value);

        }

        if (isRed(node->right) && !isRed(node->left)) {

            node = leftRotate(node);

        }

        if (isRed(node->left) && isRed(node->left->left)) {

            node = rightRotate(node);

        }

        if (isRed(node->left) && isRed(node->right)) {

            flipColors(node);

        }

        return node;

    }

    // 在以node为根的二叉搜索树中查找key所对应的Node

    Node *getNode(Node *node, Key key) {

        if (node == nullptr) {

            return nullptr;

        }

        if (key == node->key) {

            return node;

        } else if (key < node->key) {

            return getNode(node->left, key);

        } else {

            return getNode(node->right, key);

        }

    }

    void destroy(Node *node) {

        if (node != nullptr) {

            destroy(node->left);

            destroy(node->right);

            delete node;

            size--;

        }

    }

    Node *leftRotate(Node *node) {

        Node *x = node->right;

        node->right = x->left;

        x->left = node;

        x->color = node->color;

        node->color = RED;

        return x;

    }

    Node *rightRotate(Node *node) {

        Node *x = node->left;

        node->left = x->right;

        x->right = node;

        x->color = node->color;

        node->color = RED;

        return x;

    }

    void flipColors(Node *node) {

        node->color = RED;

        node->left->color = BLACK;

        node->right->color = BLACK;

    }

};

#endif //RED_BLACK_TREE_RBTREE_H

　　总结　　

　　面试时99.9%不会让手写一下红黑树的添加过程，除非你面试算法工程师，那就打扰了！主要理解红黑树的性质、左旋和右旋等。

　　欢迎点赞和评论，感谢支持！

最新文章

  1. Android基础总结（七）
  2. ORACLE建表练习
  3. ORCFILE,ParquetFile,CubeFile使用场景区别
  4. pushState与replaceState区别
  5. 关于HTML编辑页面（1）
  6. &lt;转&gt;ASP.NET学习笔记之理解MVC底层运行机制
  7. Navicat Premium 11.0.x（for Mac）激活方法
  8. Hadoop之——又一次格式化hdfs系统的方法
  9. Android触控屏幕Gesture(GestureDetector和SimpleOnGestureListener的使用教程)
  10. php循环删除checkbox
  11. Java Annotation详解 理解和使用Annotation
  12. Bytom信息上链教程
  13. Java学习笔记（十七）：构造器和setter方法选用
  14. python - classs内置方法 solt
  15. tomcat apr
  16. RISC-V架构简介
  17. 内核态与用户态通信 之 sockopt
  18. tensorflow-可视化
  19. ArcGIS API for Silverlight 的重要内容******重要
  20. 解决tableView中cell动态加载控件的重用问题

热门文章

  1. 集合-Table
  2. Telerik控件集-2019.R1.SP1.All
  3. 一线互联网企业常见的14个Java面试题，Java面试题集大全等你拿，颤抖吧程序员！
  4. 视频当道的时代，这些珍藏的优质 Python 播客值得推荐
  5. WebGL three.js学习笔记 阴影与实现物体的动画
  6. 面试前必须要知道的Redis面试题
  7. Git操作GitHub时的Proxy配置
  8. Linux 系统调用过程详细分析
  9. 关于ef+codefirst+mysql/dapper(dbFirse)（入门）
  10. 有源点最短路径--Dijkstra算法