红黑树都可以这么细？面试官还能怎么说.

2021-05-25 478

女：你一点都不注重细节；
男：你说我不都细节？？你看看下面的红黑树讲解，，你说我不够细节？？
随后男发送下面红黑树代码发给女朋友之后；
女：哇，哥哥果然好细；
男：细节拉满，关注又是一个细节；
当然也不能太细，这样也不太好；

代码+图解

红黑树的性质：

首先记住它的性质：

在增删节点时需要调整满足性质

根节点是黑色的;
如果一个节点是红色的，则它的两个孩子结点是黑色的;
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点;
每个叶子结点都是黑色的(此处的叶子结点指的是空结点);

对颜色进行定义：

//我们用枚举表示表示出两种颜色  
//枚举默认第一个参数 BLACK 为 0 ，第二个参数 RED 为 1；
enum COLOR {
    BLACK,
    RED
};

红黑树的节点表示：

看图说节点
红黑树的节点参数，

一个指向上面的节点定义为_parent
一个指向左边的节点的节点指针 _left
一个指向右边的 _right
一个pair类型的值
一个颜色的识别

当然这么写参数那得来个构造函数了，“细节”。

template<class K,class V>
struct RBNode {
    //各个节点
    RBNode<K, V>* _parent;
    RBNode<K, V>* _left;
    RBNode<K, V>* _right;
    //key-value
    pair<K, V> _kv;
    //颜色
    COLOR _color;
    RBNode(const pair<K, V>& kv = pair<K, V>())
        :_parent(nullptr)
        , _left(nullptr)
        , _right(nullptr)
        , _kv(kv)
        //新申请的节点定义为RED，黑色的加入，会导致其他所有路径的黑色都遭到破坏；
        , _color(RED) {
    }
};

对树的类进行定义：

红黑树的头节点——`header`

指向如图上图：具体下面再写

template<class K,class V>
class RBTree {
public:
    //类型定义,用Node表示RBNode<K,V>
    typedef RBNode<K,V> Node;

    RBTree()
        :_header(new Node) {
        //创建空树
        _header->_left = _header->_right = _header;
    }
private:
    Node* _header;
};

红黑树的插入：

当插入c节点时，为了满足性质，需要对节点进行调整，为了保证调整最优；
如果插入节点的父节点（u）和叔叔节点（u）为红色，那么只需要改变叔叔节点（u）和父节点（p）颜色为黑色，祖父节（g）为黑色即可；
当然如果祖父节点（g) 为根节点，再把其变为黑色；

不是根节点，向上调整；

结构右旋：

写一个左旋的操作，在树结构变化时可高效的改变保证结构性质；
如果
当出现情况1：
插入节点为c，当它的叔叔节点为黑色，或者叔叔节点不存在，操作相同；

记录三个节点，只有这三个节点指向变化；
由图：
用parent表示g，
用subL表示p，
用subLR表示p的右子节点即c；
用pparent表示g的父节点；

    //        parent
    //  subL
    //          subLR   
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        //改变节点指向：
        subL->_right = parent;
        parent->_left = subLR;
        //如果存在父节点存在，如果为nullptr则没有父节点；
        if (subLR)
            subLR->_parent = parent;
        //判断根
        if (parent == _header->_parent) {
            _header->_parent = subL;
            subL->_parent = _header;
        }
        //不是根
        else {
            Node* pparent = parent->_parent;
            subL->_parent = pparent;
            if (pparent->_left == parent)
                pparent->_left = subL;
            else
                pparent->_right = subL;
        }
        //先要将parent的父节点赋值出去，才能改变paremt的父节点；
        parent->_parent = subL;
    }

结构左旋：

：如图顺序（未画完全，子节点仍然有且满足性质）

记录三个节点，只有这三个节点指向变化；（操作和右旋思路相同）
由图：
用pparent表示p的父节点；
    //          parent
    //                  subR
    //          subRL               
    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        subR->_left = parent;
        parent->_right = subRL;
        if (subRL) {
            subRL->_parent = parent;
        }
        if (_header->_parent == parent) {
            _header->_parent = subR;
            subR->_parent = _header;
        }
        else {
            Node* pparent = parent->_parent;
            subR->_parent = pparent;
            if (pparent->_left == parent)
                pparent->_left = subR;
            else
                pparent->_right = subR;
        }
        parent->_parent = subR;
    }

头节点指向的左右节点：

如图：header头节点指向最左最右的节点；

找红黑树的最左节点：

    //最左节点
    Node* leftMost() {
        Node* cur = _header->_parent;
        while (cur && cur->_left) {
            cur = cur->_left;
        }
        return cur;
    }

找红黑树的最右节点：

//最右节点
    Node* rightMost() {
        Node* cur = _header->_parent;
        while (cur && cur->_right) {
            cur = cur->_right;
        }
        return cur;
    }

红黑树的插入情况分析：

情况1：插入节点的父节点颜色为黑色；

处理1：直接插入;
情况2：插入节点的父节点为红色，叔叔节点存在且为红色；

处理2：插入后叔叔节点和父节点颜色变黑，祖父节点颜色变红，向上遍历查看情况；
情况3：父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的左子树，父节点为祖父节点的左子树；

处理3：进行结构右旋操作（RotateR）；
情况4：和情况3的结构调整相反父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的右子树，父节点为祖父节点的右子树；

处理4：进行结构左旋操作（RotateL）；
情况5：和情况6结构调整相反父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的左子树，父节点为祖父节点的右子树；

处理5：先以父节点为根，先右旋操作（RotateR），再以祖父节点为根，左旋操作（RotateL）；
情况6：父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的右子树，父节点为祖父节点的左子树；

处理6：先以父节点为根，左旋操作（RotateL），再以祖父节点为根，右旋操作（RotateR）；

上图:（个情况）

情况1：
情况2：
情况3：
情况4：
和情况3相反，自己画去；
情况5：
情况6相反，自己画去；

情况6 在这里插入图片描述

上代码：

//插入
bool insert(const pair<K,V>& kv) {
    //1.搜索树颜色
    //空树：_header->parent:nullptr
    if (_header->_parent == nullptr) {
        //创建根节点
        Node* root = new Node(kv);

        _header->_parent = root;
        root->_parent = _header;
        _header->_left = _header->_right = root;
        //根节点是黑色
        root->_color = BLACK;
        return true;
    }

    //从根节点开始搜索
    //正常插入
    Node* cur = _header->_parent;
    Node* parent = nullptr;
    while (cur) {
        parent = cur;
        //和key值进行比较
        //kv： pair<K,V>, key:pair.first
        if (cur->_kv.first == kv.first) {
            //key值存在，不允许插入
            return false;
        }

        else if (cur->_kv.first > kv.first) {
        //向小的找,左子树去找
            cur = cur->_left;
        }
        else {
        //向大的找,右子树去找
            cur = cur->_right;
        }
    }//找到了

    //创建待插入节点
    cur = new Node(kv);
    if (parent->_kv.first > cur->_kv.first)
        parent->_left = cur;//比较大小，插在左右那个位置；
    else
        parent->_right = cur;
    cur->_parent = parent;

    //2.调整结构或者修改颜色
//判断是否至少有三层；
    while (cur != _header->_parent && cur->_parent->_color == RED) {
        parent = cur->_parent;
        Node* gfather = parent->_parent;
        //可能出现情况6，情况3
        if (gfather->_left == parent) {
            Node* uncle = gfather->_right;
            //情况2：uncle存在，并且都是红色
            if (uncle && uncle->_color == RED) {
                parent->_color = uncle->_color = BLACK;
                gfather->_color = RED;
                //继续向上更新
                cur = gfather;
            }
            //
            else {
                cout << "Rotate" << endl;
                //双旋结构
                //情况6：
                if (cur == parent->_right) {
                    RotateL(parent);
                    swap(cur, parent);
                }
//经过第一次左旋后，情况6 与情况3 只有cur节点和父节点的指向不一样，
//经过swap两者后，接下来操作相同都为右旋；
                RotateR(gfather);
                parent->_color = BLACK;
                gfather->_color = RED;
                break;
            }
        }
        else {
            //gfather->_right=parent的情况；
            //情况4，情况5,；
            //处理与情况3，情况6相反；
            Node* uncle = gfather->_right;
            //uncle存在，且都是红色，最简
            if (uncle && uncle->_color == RED) {
                parent->_color = uncle->_color = BLACK;
                gfather->_color = RED;
                cur = gfather;
            }
            //情况3：uncle不存在，或者uncle存在为黑色
            //双旋结构
            else {
                //      gfather
                //  uncle       parent  
                //           cur
                //
                if (cur == parent->_left) {
                    RotateR(parent);
                    swap(cur, parent);
                }
                RotateL(gfather);
                parent->_color = BLACK;
                gfather->_color = RED;
                break;
            }
        }
    }
    //根节点的颜色改成黑的；
    _header->_parent->_color = BLACK;
    //更新header左右指向
    _header->_left = leftMost();
    _header->_right = rightMost();
}

中序遍历进行打印：

//对中序遍历进行封装：
void inorder() {
    _inorder(_header->_parent);
    cout << endl;
}
//使用递归从叶子节点开始；
//1.打印最左节点，
//2.打印此节点
//3.打印右节点
void _inorder(Node* root) {
    if (root) {
        _inorder(root->_left);
        cout << root->_kv.first << "--->" << root->_kv.second << endl;
        _inorder(root->_right);
    }
}

判断是否满足红黑树的性质：

//红黑树：
//1.根：黑色
//2.每条路径黑色个数相同
//3.红色不能连续
bool isBalance() {
    if (_header->_parent == nullptr)
        return true;//只有头节点也是满足红黑树
    Node* root = _header->_parent;
    //1.判断根节点的颜色
    if (root->_color == RED)
        return false;
    //统计一条路劲的黑色节点个数
    int bCount = 0;
    Node* cur = root;
    while (cur) {
        if (cur->_color == BLACK)
            ++bCount;
        cur = cur->_left;
    }
    //遍历每一条路径
    int curBCount = 0;
    return _isBalance(root, bCount, curBCount);
}
bool _isBalance(Node* root, int& bCount, int curBCount) {
    //当root为空，一条路径遍历结束
    if(root == nullptr){
    //判断黑色节点个数是否相同
    if (bCount != curBCount)
        return false;
    else
        return true;
    }
    //判断是否为黑节点
    if (root->_color == BLACK)
        ++curBCount;
    //判断红色节点是否有连续
    if (root->_parent && root->_color == RED
        && root->_parent->_color == RED) {
        cout << "data: " << root->_kv.first << "--->" << root->_kv.second << endl;
        return false;
    }
    return _isBalance(root->_left, bCount, curBCount) 
        && _isBalance(root->_right,bCount, curBCount);
}

完整代码如下：可直接调试

#include<iostream>
#include<iostream>
#include<utility>
using namespace std;

//设置颜色属性
enum COLOR {
    BLACK,
    RED
};
template<class K,class V>
struct RBNode {
    //typedef bool color;
    //各个节点
    RBNode<K, V>* _parent;
    RBNode<K, V>* _left;
    RBNode<K, V>* _right;
    //key-value
    pair<K, V> _kv;
    //颜色
    COLOR _color;
    RBNode(const pair<K, V>& kv = pair<K, V>())
        :_parent(nullptr)
        , _left(nullptr)
        , _right(nullptr)
        , _kv(kv)
        , _color(RED) {
    }
};
template<class K,class V>
class RBTree {
public:
    //类型定义
    typedef RBNode<K,V> Node;

    RBTree()
        :_header(new Node) {
        //创建空树
        _header->_left = _header->_right = _header;
    }
    //插入
    bool insert(const pair<K,V>& kv) {
        //1.搜索树颜色
        //空树：_header->parent:nullptr
        if (_header->_parent == nullptr) {
            //创建根节点
            Node* root = new Node(kv);

            _header->_parent = root;
            root->_parent = _header;
            _header->_left = _header->_right = root;

            //根节点是黑色
            root->_color = BLACK;
            return true;
        }
        //从根节点开始搜索
        //正常插入
        Node* cur = _header->_parent;
        Node* parent = nullptr;
        while (cur) {
            parent = cur;
            //和key值进行比较
            //kv： pair<K,V>, key:pair.first
            if (cur->_kv.first == kv.first) {
                //key值不允许重复
                return false;
            }
            else if (cur->_kv.first > kv.first) {
                cur = cur->_left;
            }
            else {
                cur = cur->_right;
            }
        }
        //创建待插入节点
        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;
        cur->_parent = parent;

        //2.修改颜色或者调整结构
        while (cur != _header->_parent && cur->_parent->_color == RED) {
            parent = cur->_parent;
            Node* gfather = parent->_parent;

            if (gfather->_left == parent) {
                Node* uncle = gfather->_right;
                //1.uncle存在，并且都是红色
                if (uncle && uncle->_color == RED) {
                    parent->_color = uncle->_color = BLACK;
                    gfather->_color = RED;
                    //继续更新
                    cur = gfather;
                }

                else {
                    cout << "Rotate" << endl;
                    //双旋结构
                    if (cur == parent->_right) {
                        RotateL(parent);
                        swap(cur, parent);
                    }
                    RotateR(gfather);
                    parent->_color = BLACK;
                    gfather->_color = RED;
                    break;
                }
            }
            else {
                //gfather->_right=parent;
                Node* uncle = gfather->_right;
                //uncle存在，且都是红色，最简
                if (uncle && uncle->_color == RED) {
                    parent->_color = uncle->_color = BLACK;
                    gfather->_color = RED;
                    cur = gfather;
                }
                //uncle不存在，或者uncle存在为黑色
                //双旋结构
                else {
                    //      gfather
                    //  uncle       parent  
                    //           cur
                    //
                    if (cur == parent->_left) {
                        RotateR(parent);
                        swap(cur, parent);
                    }
                    RotateL(gfather);
                    parent->_color = BLACK;
                    gfather->_color = RED;
                    break;
                }
            }
        }
        //根节点的颜色改成黑的；
        _header->_parent->_color = BLACK;
        //更新header左右指向
        _header->_left = leftMost();
        _header->_right = rightMost();
    }
    //          parent
    //                  subR
    //          subRL               
    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        subR->_left = parent;
parent->_right = subRL;
if (subRL) {
    subRL->_parent = parent;
}
if (_header->_parent == parent) {
    _header->_parent = subR;
    subR->_parent = _header;
}
else {
    Node* pparent = parent->_parent;
    subR->_parent = pparent;
    if (pparent->_left == parent)
        pparent->_left = subR;
    else
        pparent->_right = subR;

}
parent->_parent = subR;
    }
    //        parent
    //      subL
    //          subLR   
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        subL->_right = parent;
        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;
        //判断根
        if (parent == _header->_parent) {
            _header->_parent = subL;
            subL->_parent = _header;
        }
        //不是根
        else {
            Node* pparent = parent->_parent;
            subL->_parent = pparent;
            if (pparent->_left == parent)
                pparent->_left = subL;
            else
                pparent->_right = subL;
        }
        parent->_parent = subL;

    }
    //最左节点
    Node* leftMost() {
        Node* cur = _header->_parent;
        while (cur && cur->_left) {
            cur = cur->_left;
        }
        return cur;
    }
    //最右节点
    Node* rightMost() {
        Node* cur = _header->_parent;
        while (cur && cur->_right) {
            cur = cur->_right;
        }
        return cur;
    }
    void inorder() {
        _inorder(_header->_parent);
        cout << endl;
    }
    void _inorder(Node* root) {
        if (root) {
            _inorder(root->_left);
            cout << root->_kv.first << "--->" << root->_kv.second << endl;
            _inorder(root->_right);
        }
    }

    //红黑树：
    //1.根：黑色
    //2.每条路径黑色个数相同
    //3.红色不能连续
    bool isBalance() {
        if (_header->_parent == nullptr)
            return true;
        Node* root = _header->_parent;

        if (root->_color == RED)
            return false;
        //统计一条路劲的黑色节点个数
        int bCount = 0;
        Node* cur = root;
        while (cur) {
            if (cur->_color == BLACK)
                ++bCount;
            cur = cur->_left;
        }
        //遍历每一条路径
        int curBCount = 0;
        return _isBalance(root, bCount, curBCount);
    }
    bool _isBalance(Node* root, int& bCount, int curBCount) {
        //当root为空，一条路径遍历结束
        if(root == nullptr){
        //判断黑色节点个数是否相同
        if (bCount != curBCount)
            return false;
        else
            return true;
        }
        //判断是否为黑节点
        if (root->_color == BLACK)
            ++curBCount;
        //判断红色节点是否有连续
        if (root->_parent && root->_color == RED
            && root->_parent->_color == RED) {
            cout << "data: " << root->_kv.first << "--->" << root->_kv.second << endl;
            return false;
        }
        return _isBalance(root->_left, bCount, curBCount) 
            && _isBalance(root->_right,bCount, curBCount);
    }
private:
    Node* _header;
};
void test()     {
    RBTree<int, int> rbt;
    int n;
    cin >> n;
    for (int i = n; i > 0; --i) {
        rbt.insert(make_pair(i, i));
    }
    rbt.inorder();
    cout << rbt.isBalance();
}
int main() {
    test();
    return 0;
}

微信关注我们

原文链接：https://blog.51cto.com/u_14982125/2807896

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

飞猪基于 Serverless 的云+端实践与思考

作者 | 王恒飞（承荫）来源 | 阿里巴巴云原生公众号本文整理自飞猪旅行前端技术专家--王恒飞（承荫）在【阿里云 Serverless Developer Meetup 上海站】上的分享。点击查看直播回放：https://developer.aliyun.com/live/246653。过去两年，飞猪前端一直在积极地进行 Serverless 建设和实践，2019 年 - 2020 年我们和集团 Node 架构组、研发平台一起完成了基础能力的建设和业务试点，成为集团率先落地 Serverless 实践的 BU，2020 年 - 2021 年我们开始大规模地在飞猪推广使用 Serverless 的能力，从导购全链路到核心中后台，都能够看到 Serverless 的身影，这一年我们完成了 Serverless 从业务试点到生产力工具的转变，本文将主要分享飞猪基于 Serverless 的实践成果以及未来想要做的事情。 Serverless 的使用规模 2020 年 - 2021 年飞猪 Serverless 的规模和重要度都有很大的变化，主要表现在三方面：一是函数组规模增长一倍...

2021-05-25

497

本文可看做是前文《鸿蒙系统的启动流程v2.0》的第四阶段的补充和验证。首先请看我的环境：HiSpark AI Camera开发板(Hi3516dv300) + DevEco的HPM新建工程[Hi3516]编译的软件，项目代码默认打印的大部分log被我临时关掉了，按我自己的风格在关键点重新打印的log，log基本样例为： [system_init] SystemInit[20-18]: system_console_init[full shell]：[system_init] //在system_init.c 文件内: SystemInit[20-18] //在SystemInit()函数内，大概有20步主要动作，这是第18步：system_console_init[full shell] //这一步做了哪些事，或者打印关键信息附件的log，是我在Hi3516开发板上抓的，大概从内核创建 Init 进程前一点点，到系统启动稳定的全过程，最后一段是点击相机应用打开摄像头的log。我将其分成若干段，下面一步步分析其启动细节。 1. 创建 /bin/init 前：Line3~7 [syst...

2021-05-25

761

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

红黑树都可以这么细？面试官还能怎么说.

代码+图解

红黑树的性质：

红黑树的节点表示：

对树的类进行定义：

红黑树的头节点——`header`

红黑树的插入：

结构右旋：

结构左旋：

头节点指向的左右节点：

找红黑树的最左节点：

找红黑树的最右节点：

红黑树的插入情况分析：

上图:（个情况）

上代码：

中序遍历进行打印：

判断是否满足红黑树的性质：

完整代码如下：可直接调试

飞猪基于 Serverless 的云+端实践与思考

鸿蒙系统框架层的启动细节

相关文章

发表评论

资源下载

优质分享App

Mario

Spring

Sublime Text

欢迎您！

红黑树 都可以这么细？面试官还能怎么说.

代码+图解

红黑树的性质：

红黑树的节点表示：

对树的类进行定义：

红黑树的头节点——header

红黑树的插入：

结构右旋：

结构左旋：

头节点指向的左右节点：

找红黑树的最左节点：

找红黑树的最右节点：

红黑树的插入情况分析：

上图:（个情况）

上代码：

中序遍历进行打印：

判断是否满足红黑树的性质：

完整代码如下：可直接调试

飞猪基于 Serverless 的云+端实践与思考

鸿蒙系统框架层的启动细节

相关文章

发表评论

资源下载

优质分享App

Mario

Spring

Sublime Text

欢迎您！

红黑树都可以这么细？面试官还能怎么说.

红黑树的头节点——`header`