红黑树上篇

1.基本概念

红黑树是一棵自平衡的二叉搜索树，因此在学习红黑树之前，我们需要回顾一下之前所学的知识二叉搜索树和平衡二叉树。

2.二叉搜索树

二叉搜索树又叫二叉查找树或者二叉排序树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）左、右子树也分别为二叉搜索树

3.平衡二叉树 （AVL树）

二叉搜索树解决了许多问题，比如可以快速的查找最大值和最小值，可以快速找到排名第几位的值，快速搜索和排序等等。
但普通的二叉搜索树有可能出现极不平衡的情况（斜树），这样我们的时间复杂度就有可能退化成 O(N) 的情况。
比如我们现在插入的数据是 [1,2,3,4,5,6,7] 转换为二叉树如下：接近链表了。

由于普通的二叉搜索树会出现极不平衡的情况，那么我们就必须得想想办法了，这个时候平衡二叉树就能帮到我们了。
什么是平衡二叉树？
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），
且具有以下性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树有一个很重要的性质：
左右两个子树的高度差的绝对值不超过1。那么解决方案就是如果二叉树的【左右高度超过 1】 ，
我们就把当前树调整为一棵平衡二叉树。
这就涉及到左旋、右旋、先右旋再左旋、先左旋再右旋。

---

4.红黑树的特性： 接近平衡的二叉树，还是一棵自平衡的树。

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(nil 或 NULL)的叶子节点！]
空节点也是黑色的。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。 ------从而保证树是接近平衡的二叉树。树的高度差 不会超过2倍。
可以是两个连着的黑节点。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 ------重要概念。

上面2个定义，保证了红黑数，是接近平衡的二叉树。
因为树之间的【高度差，不会超过2倍】. 所以红黑树，也是接近平衡的二叉树。
最深的情况是一黑一红；最浅的情况是两个黑。
所以：最深的情况，是最浅情况的两倍。

c++的map，multimap，
hashmap，treemap都是用的红黑树。

双红问题解决：
1.父节点颜色是黑色的，不要解决。
2.叔叔节点是红色的，把叔叔节点染黑，把父亲节点染黑，然后指针回溯至爷爷节点（交给爷爷去处理），把爷爷染红。
3.如果叔叔是黑色的，
3.2 把父节点染黑，把爷爷染红，右旋爷爷节点。
3.1 还需要分情况讨论，如果当前节点是父亲的右儿子，就把父亲节点左旋， 先变成上面的情况3.2。

新增的思想：

新增红色节点，解决双红问题，挪动到隔壁的树上面去。但是挪动时不打破 性质4 和 性质5.
最终满足红黑树。

5.红黑树的新增逻辑和代码实现。

红黑树使用场景：
equals- hashcode- hashMap/hashTab区别- ConcurrentHashMap。
hashMap jdk1.8后改进。

---

6. 代码部分

// native-lib.cpp
#include <jni.h>
#include <string>
#include "map.hpp"
#include <android/log.h>

void visit(int key, int value, bool isRed) {
    if (isRed) {
        __android_log_print(ANDROID_LOG_ERROR, "TAG", "key = %d , value = %d , color = %s", key, value,"红");
    } else {
        __android_log_print(ANDROID_LOG_ERROR, "TAG", "key = %d , value = %d , color = %s", key, value,"黑");
    }
}

extern "C"
JNIEXPORT jstring
JNICALL
Java_com_example_hcdarren_ndk_1day47_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {

    map<int, int> *map = new ::map<int, int>();
    map->insert(3, 3);
    map->insert(2, 2);
    map->insert(1, 1);
    map->insert(4, 4);
    map->insert(5, 5);
    map->insert(-5, -5);
    map->insert(-15, -15);
    map->insert(-10, -10);
    map->insert(6, 6);
    map->insert(7, 7);

    map->levelTraverse(visit);
    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}

// map.hpp
// 红黑树，实现插入操作。

#ifndef NDK_DAY47_MAP_H
#define NDK_DAY47_MAP_H
#include <queue>
using namespace std;

// 能用到的语法用一用，使用bool定义。别名rb_color
typedef bool rb_color;
#define black false // 黑色
#define red true //  红色


template<class K, class V>
class map {
private:
    struct TreeNode; // 节点
    int count;
    TreeNode *root; // 根节点，必须黑色

public:
    map() : root(NULL) {
        count = 0;
    }
public:
    struct iterator; // 迭代器
    TreeNode *parent(TreeNode *pNode) { // 父节点
        return pNode ? pNode->parent : NULL;
    }
    TreeNode *left(TreeNode *pNode) { // 左右子树
        return pNode ? pNode->left : NULL;
    }
    TreeNode *right(TreeNode *pNode) {
        return pNode ? pNode->right : NULL;
    }
    TreeNode *brother(TreeNode *pNode) { // 兄弟节点：当前节点是右儿子节点，拿左儿子节点；当前节点是左儿子节点，拿右儿子节点。
        return left(parent(pNode)) == pNode ? right(parent(pNode)) : left(parent(pNode));
    }

    rb_color getColor(TreeNode *pNode) { // 获取节点颜色,设置节点颜色
        return pNode ? pNode->color : black;
    }
    void setColor(TreeNode *pNode, rb_color color) {
        if (pNode) {
            pNode->color = color;
        }
    }

    TreeNode *L_Rotation(TreeNode *pNode) { // 左旋
        // avl 左旋 , 多了一个父亲节点
        TreeNode *right = pNode->right; // 右节点作为新的根节点
        pNode->right = right->left;     // 新根节点原来的左孩子，作为原根节点的右孩子。
        right->left = pNode;            // 原根节点，作为新根节点的左孩子。

        // 调整 pNode 父亲的儿子指向
        if (pNode->parent == NULL) {
            root = right; // 成为根节点
        } else if (pNode->parent->left == pNode) { // pNode原来是父亲的左儿子
            pNode->parent->left = right;
        } else {
            pNode->parent->right = right;
        }

        // 调整各大节点的父亲
        right->parent = pNode->parent;
        if (pNode->right) {
            pNode->right->parent = pNode;
        }
        pNode->parent = right;

        return right;
    }

    TreeNode *R_Rotation(TreeNode *pNode) {
        TreeNode *left = pNode->left;
        pNode->left = left->right;
        left->right = pNode;

        // 调整 pNode 父亲的儿子指向
        if (pNode->parent == NULL) {
            root = left;
        } else if (pNode->parent->left == pNode) {
            pNode->parent->left = left;
        } else {
            pNode->parent->right = left;
        }

        // 调整各大节点的父亲
        left->parent = pNode->parent;
        if (pNode->left) {
            pNode->left->parent = pNode;
        }
        pNode->parent = left;

        return left;
    }

    // 双红修正：不能违背性质4和5，基于这两点来解决。
    void solveDoubleRed(TreeNode *pNode) {
        while (pNode->parent && pNode->parent->color == red) { // 情况1
            if (getColor(brother(parent(pNode))) == red) { // 情况 2
                // 2.叔叔节点是红色的，把叔叔节点染黑，把父亲节点染黑，然后指针回溯至爷爷节点（交给爷爷去处理），把爷爷染红。
                setColor(parent(pNode), black);
                setColor(brother(parent(pNode)), black);
                setColor(parent(parent(pNode)), red);
                pNode = parent(parent(pNode));
            } else { // 情况 3：叔叔节点是黑色
                if (left(parent(parent(pNode))) == parent(pNode)) { // 爷爷的左儿子，是我的父节点。
                    if (right(parent(pNode)) == pNode) { // 情况 3.1: 先以父节点左旋
                        pNode = parent(pNode);
                        L_Rotation(pNode); // 以父节点左旋
                    }
                    // 情况 3.2  把我父亲这棵子树上的红色节点，挪动到我的叔叔的那棵树上
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    R_Rotation(parent(parent(pNode)));

                } else { // 爷爷的右儿子，是我的父节点。
                    if (left(parent(pNode)) == pNode) { // 情况 3.1
                        pNode = parent(pNode);
                        R_Rotation(pNode);
                    }
                    // 情况 3.2  把我父亲这棵子树上的红色节点，挪动到我的叔叔的那棵树上
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    L_Rotation(parent(parent(pNode)));
                }
            }
        }
        root->color = black; // 根节点是黑色
    }

    // 插入节点。
    iterator insert(K key, V value) {
        // 插入算法
        if (root == NULL) {
            root = new TreeNode(NULL, NULL, NULL, key, value, black);
            count = 1;
            return iterator(root);
        }

        // 最好我们插入红色节点，它不会违反性质 5 ，但是有可能会违反性质 4
        TreeNode *node = root;
        TreeNode *parent = NULL; // 循环，找到待关联的父节点
        do {
            parent = node;
            if (key == node->key) { // 找到，仅更新值
                node->value = value;
                return iterator(node);
            } else if (key > node->key) { // 新key比根节点的key大，往右边子树找
                node = node->right;
            } else { //新key比根节点的key小，往左边子树找
                node = node->left;
            }
        } while (node);

        TreeNode *new_node = new TreeNode(NULL, NULL, parent, key, value, red); // 新增红色节点
        if (key > parent->key) { // 连接起来，放在右边
            parent->right = new_node;
        } else { // 放在左边
            parent->left = new_node;
        }

        solveDoubleRed(new_node); // 解决双红节点问题。
        return iterator(new_node); // 返回迭代器
    }

    bool remove(K key) {

    }
    int size() {
        return count;
    }
    bool isEmpty() {
        return count == 0;
    }

    // 层序遍历 打印。
    void levelTraverse(void (*fun)(K, V, bool)) {
        if (root == NULL) {
            return;
        }
        TreeNode *node = root;
        queue<TreeNode *> nodes;
        nodes.push(node);
        while (!nodes.empty()) {
            node = nodes.front();
            fun(node->key, node->value, node->color);
            nodes.pop();

            if (node->left) {
                nodes.push(node->left);
            }
            if (node->right) {
                nodes.push(node->right);
            }
        }
    }
};

template<class K, class V>
struct map<K, V>::TreeNode {
public:
    TreeNode *left;   // 左子树
    TreeNode *right;  // 右子树
    TreeNode *parent; // 父节点(添加要用父节点做判断)
    K key;
    V value;
    // 节点颜色
    rb_color color;
public:
    // 构造函数，第二种方式初始化
    TreeNode(TreeNode *left, TreeNode *right, TreeNode *parent, K key, V value, rb_color color)
            :
            left(left), right(right), parent(parent), key(key), value(value), color(color) {}

    // 找到前驱（前面的点）：左边子树的最大值
    TreeNode *precursor() {
        // 参考下面successor()，做类似逻辑调整。方向相反。代码未验证。
        if(left){
            TreeNode *node = left;
            if (node->right) {
                node = node->right; // 不断往右边找
            }
            return node;
        } else {
            // 对56来讲，50才是它的前驱。
            TreeNode *successor = this;
            while (successor->parent && successor->parent->left == successor) {
                successor = successor->parent; // 一直找右上角的父节点。
            }
            return successor->parent; // 再往上走一层，找到目标。
        }
    }

    // 找后继，后面的点。
    TreeNode *successor() {
        if (right) { // 右边不为空。
            TreeNode *successor = right;
            while (successor->left) {
                successor = successor->left;
            }
            return successor;
        } else { // 不断地找父亲节点，直到找到是父亲的左儿子。在往上走一层。
            // 48找后继节点，目标要找到50，要不断地往父节点找
            TreeNode *successor = this;
            while (successor->parent && successor->parent->right == successor) {
                successor = successor->parent; // 一直找左上角的父节点
            }
            return successor->parent; // 再往上走一层，找到目标50.
        }
    }
};

template<class K, class V>
struct map<K, V>::iterator { // 迭代器，复写操作符--，++
private:
    TreeNode *node;
public:
    // 构造函数
    iterator(TreeNode *node) : node(node) {}

    iterator &operator--() {// 找前驱节点，返回迭代器，能再次--。
        node = node->precursor();
        return *this;
    }
    iterator &operator++() {// 找后继节点
        node = node->successor();
        return *this;
    }

    V operator*() { // 取节点的值
        return node->value;
    }
};
#endif //NDK_DAY47_MAP_H