数据结构算法之红黑树

作者: Peakmain | 来源:发表于2019-04-09 11:32 被阅读0次

(313)红黑树-java实现
数据结构与算法之美-25讲红黑树（上）
数据结构与算法之美-26讲红黑树（下）
数据结构 - 红黑树
红黑树笔记
数据结构红黑树添加、修改原理分析
数据结构与算法-AVL 红黑树
数据结构&算法之《红黑树》
数据结构算法之红黑树
无标题文章

红黑树的特性

（1）每个节点要么是黑色，要么是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。树高度差不会超过两倍
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树新增

比如新增的数：[3，2，1，4，5，-5，-15，-10，6，7]

image.png

第一步：3，2，1添加完成之后，我们会发现，1，2都是红色的情况（简称双红情况），此时违背了性质4，我们这时候需要将它进行右旋，并且两边染红，根据性质2，根节点染黑，结果如右图（4是新增的）

image.png

第二步：新增4之后又出现了双红情况，这时候我们发现它的付清节点3的兄弟节点1也是红色节点，所以我们的做法是将它的父节点和它的父节点的兄弟节点染黑，爷爷节点染红，但是因为此时它的爷爷节点2是根节点，所以染黑，结果就是中间这种情况（5是新增节点），之后新增节点5之后进行左旋就可以了，结果如右图

image.png

第三步：添加-5，-15，-10之后就是中间图，-15，1是兄弟节点且都是红色，此时两个都进行染黑，并将爷爷节点染红，继续新增6.7等，步骤类似不阐述

image.png

总结：1、首先判断父节点是否是黑色，是直接返回
2、判断叔父节点(父节点的兄弟节点)是否为红色，红色，将父节点和叔父节点染黑，祖父节点染红
3、叔父节点不为红色，进行相应的旋转

删除

分情况讨论：

1.如果兄弟节点是红色的，把兄弟节点染黑，父节点染红，左/右旋父节点；
2.如果兄弟节点是黑色的，并且两个侄子节点都是黑色的，将兄弟节点染红，指针回溯至父亲节点；
3.如果兄弟节点是黑色的并且远侄子是黑色，将进侄子染黑，兄弟染红，左/右旋兄弟节点，进入下面情况 4 ；
4.如果兄弟节点是黑色的并且远侄子是红色的，将兄弟节点染成父亲节点的颜色，父亲节点染黑，远侄子染黑，左/右旋父亲节点。

image.png

比如上图，我们删除1，首先判断当前节点位于左结点还是右结点，判断它的兄弟节点-15是否是红色,很明显是黑色，判断-15的左结点是否是黑色，如果是将-15染红，-15的右结点染黑，然后进行左旋，随后对-15的父节点和左结点染黑，右旋，终止循环即可。

image.png

假设设置的是-15节点，那么直接将-10进行替代，然后将-10这个节点染黑就可以了

代码

//
// Created by asus on 2019/4/4.
//

#ifndef NDK_MAP_H
#define NDK_MAP_H


#include <queue>


using namespace std;

typedef bool rb_color;
#define  red true
#define black false

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) {
        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->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;
    }

    /**
     * 解决新增的时候的节点问题
     */
    void solveDoubleRed(TreeNode *pNode) {
        while (pNode->parent && pNode->parent->color == red) {//双红情况
            //兄弟节点是否为红色
            if (getColor(brother(parent(pNode))) == red) {
                //将父节点和兄弟节点设置成黑色
                setColor(parent(pNode), black);
                setColor(brother(parent(pNode)), black);
                //将爷爷节点设置成红色
                setColor(parent(parent(pNode)), red);
                //归宿到爷爷节点
                pNode = parent(parent(pNode));
            } else {
                //兄弟节点为黑色
                //左结点
                if (left(parent(parent(pNode))) == parent(pNode)) {
                    //判断是否需要先左旋
                    if (right(parent(pNode)) == pNode) {
                        pNode = parent(pNode);
                        L_Rotation(pNode);
                    }
                    //父节点变成黑色
                    setColor(parent(pNode), black);
                    //爷爷节点变成红色
                    setColor(parent(parent(pNode)), red);
                    R_Rotation(parent(parent(pNode)));
                } else {
                    if (left(parent(pNode)) == pNode) {
                        pNode = parent(pNode);
                        R_Rotation(pNode);
                    }
                    //父节点为黑色
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    L_Rotation(parent(parent(pNode)));
                }
            }
        }
        //根节点设置为黑色
        root->color = black;
    }

    iterator insert(K key, V value) {
        //性质2：根节点是黑色
        if (root == NULL) {
            root = new TreeNode(NULL, NULL, NULL, key, value, black);
            count = 1;
            return iterator(root);
        }
        //性质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) {//大于的放到右结点
                node = node->right;
            } else {
                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);
        count++;
        return iterator(new_node);
    };

    TreeNode *findTree(K key) {
        TreeNode *node = root;
        while (node) {
            if (key == node->key) {
                return node;
            } else if (key > node->key) {
                node = node->right;
            } else {
                node = node->left;
            }
        }
        return NULL;
    }

    /**
     * 解决删除的时候的节点的问题
     */
    void solveLostBlack(TreeNode *pNode) {
        //判断当前删除的节点不为根节点，且是黑色
        while (pNode != root && pNode->color == black) {
            if (left(parent(pNode)) == pNode) {// 当前节点是父亲节点的左节点
                //获取它的兄弟节点
                TreeNode *sib = brother(pNode);
                if (getColor(sib) == red) { //兄弟节点是红色
                    //将兄弟节点染黑
                    setColor(sib, black);
                    //父节点染红
                    setColor(parent(pNode), red);
                    L_Rotation(parent(pNode));
                    sib = brother(pNode);
                }
                //兄弟的左右节点都是黑色
                if (getColor(left(sib)) == black && getColor(right(sib)) == black) {
                    //将兄弟节点染红
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {
                    if (getColor(right(sib)) == black) {
                        setColor(sib, red);
                        setColor(left(sib), black);
                        R_Rotation(sib);
                        sib = brother(pNode);
                    }

                    setColor(sib, getColor(parent(pNode)));
                    setColor(parent(pNode), black);
                    setColor(right(sib), black);
                    L_Rotation(parent(pNode));

                    pNode = root;
                }
            } else {// 当前节点是父亲节点的右节点
                TreeNode *sib = brother(pNode);
                //兄弟节点是否是红色
                if (getColor(sib) == red) {
                    setColor(sib, black);
                    setColor(parent(pNode), red);
                    R_Rotation(parent(pNode));
                    sib = brother(pNode);
                }

                if (getColor(left(sib)) == black && getColor(right(sib)) == black) {
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {

                    if (getColor(left(sib)) == black) {
                        setColor(sib, red);
                        setColor(right(sib), black);
                        L_Rotation(sib);
                        sib = brother(pNode);
                    }

                    setColor(sib, getColor(parent(pNode)));
                    setColor(parent(pNode), black);
                    setColor(left(sib), black);
                    R_Rotation(parent(pNode));
                    pNode = root;
                }
            }
        }
        // 当遇到一个红色节点，把红色节点染黑即可
        pNode->color = black;
    }


    bool remove(K key) {
        //删除一个红色节点不影响
        //假如删除一个黑色节点，肯定会破坏性质5
        //假设左右节点都不为空的情况，需要找到后继节点代替，其实删除的是后继点
        //假设删除的左右两棵子树上有一方不为空的情况，会找左右的一棵子树代替
        TreeNode *current = findTree(key);
        if (current == NULL) {
            return false;
        }
        //左右节点都不为空
        if (current->left != NULL && current->right != NULL) {
            //找到它的后继
            TreeNode *successor = current->successor();
            //将当前的节点变成后继的节点
            current->key = successor->key;
            current->value = successor->value;
            current = successor;
        }
        TreeNode *replace = current->left ? current->left : current->right;
        //有没有左右子树
        if (replace != NULL) {
            if (current->parent == NULL) {//根节点
                root = replace;
            } else if (current->parent->left == current) {
                //当前节点被替换成当前节点的左结点
                current->parent->left = replace;
            } else {
                //当前节点被替换成当前节点的右结点
                current->parent->right = replace;
            }
            replace->parent = current->parent;
            //如果删除的是黑色的节点，需要处理黑色节点的问题
            if (current->color == black) {
                solveLostBlack(replace);
            }
            //删除当前节点
            delete (current);
        } else if (current->parent == NULL) {
            delete (root);
            root = NULL;
        } else {
            //修正的时候需要去获取叔叔和侄子节点来分情况判断
            if (current->color == black) {
                solveLostBlack(current);
            }
            if (current->parent) {
                if (current->parent->left) {
                    current->parent->left = NULL;
                } else {
                    current->parent->right = NULL;
                }
            }
            delete (current);
        }
        count--;
        return true;
    }

    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() {
        if (left) {
            TreeNode *precursor = left;
            while (precursor->right) {
                precursor = precursor->right;
            }
            return precursor;
        } else {
            TreeNode *precursor = this;
            while (precursor->parent && precursor->parent->left == precursor) {
                precursor = precursor->parent;
            }
            return precursor->parent;
        }
    }

    //找到后继
    TreeNode *successor() {
        if (right) {
            TreeNode *successor = right;
            while (successor->left) {
                successor = successor->left;
            }
            return successor;
        } else {
            TreeNode *successor = this;
            while (successor->parent && successor->parent->right == successor) {
                successor = successor->parent;
            }
            return successor->parent;
        }
    }

};


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_MAP_H