【分享】红黑树的性质与实现思路

[复制链接]
查看3089 | 回复12 | 2021-12-13 21:57:51 | 显示全部楼层 |阅读模式

①红黑树(RBT)的Search,Insert,Delete操作的时间复杂度与平衡二叉树(AVL Tree)相同,皆是O(㏒2n)

②平衡二叉树适用以查为主,很少插入/删除的场景
红黑树适用于频繁插入、删除的场景,实用性更强
                ●图一

③红黑树相比普通二叉查找树相比,有以下要求
    ㈠每个结点或是红色或是黑色的
    ㈡根节点是黑色的
    ㈢叶节点(外部结点、NULL结点、失败结点)均是黑色的
          (注:此处的叶节点跟普通二叉树的叶子结点不同,需要注意,红黑树的叶节点只是一个空指针)
    ㈣不存在两个相邻的红结点(即红结点的父节点和孩子结点均为黑色)
    ㈤对每个结点,从该结点到任一叶结点的简单路径上,所含黑结点的数目相同
    这五个点简单来说就是:
            左根右,根叶黑,不红红,黑路同
             ●图二
      如图二,图二不满足㈣,它就不是一个红黑树

④结点的黑高:(即bh参数)指从某结点出发(不含该结点)到达任一空结点的路径上黑结点总数

例如:图一17号的bh值就为2

⑤红黑树的插入:
        先查找,确定插入位置(原理同二叉排序树),插入新结点
       新结点是根--染为黑色
       新结点非根--染为红色(原因:保证黑路同这一特性)
       若插入新结点后依然满足红黑树定义,则插入结束
       若插入新结点后不满足红黑树定义,需要调整,使其重新满足红黑树定义
       如何调整:看新结点叔叔的脸色
      
       例:图一中27是新结点的话,27的叔叔就是27的父亲(25)的左兄弟(15)

        如果叔叔是黑色:旋转+染色
        ●LL型:右单旋,父换爷+染色
        ●RR型:左单旋,父换爷+染色
        ●LR型:左、右双旋,儿换爷+染色
        ●RL型:右、左双旋,儿换爷+染色
        注:LL,RR,LR,RL为新结点所处的位置,例27号的位置就为RR
        如果叔叔是红色:染色+变新
        ●叔父爷染色,爷变为新结点

叔叔为黑色,且为LL型时交换例子如下:
叔叔为红色,违反不红红时情况如图
叔叔为黑色,违反不红红,且为RR时情况如图
叔叔为黑色,违反不红红,且为LR时情况如图:
RL情况跟LR具体情况相同。

⑥从根节点到叶节点的最长路径不大于最短路径的2倍

⑦有n个内部节点的红黑树高度h≤2㏒2(n+1)
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
千面萌萌 | 2021-12-14 10:52:48 | 显示全部楼层
我是个凑数的。。。
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

无量科技 | 2021-12-14 14:55:42 | 显示全部楼层
回个帖子,下班咯~
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

liqiang24 | 2021-12-14 22:05:14 | 显示全部楼层
路过 帮顶 嘿嘿
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

伴我多久 | 2021-12-14 22:24:19 | 显示全部楼层
LZ帖子不给力,勉强给回复下吧
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

天镜盗梦 | 2021-12-15 08:34:30 | 显示全部楼层
顶起顶起顶起
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

68079330 | 2021-12-15 09:21:19 | 显示全部楼层
站位支持
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

梦影 | 2021-12-15 11:16:09 | 显示全部楼层
看帖要回,回帖才健康,在踩踩,楼主辛苦了!
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

半度微凉 | 2021-12-15 12:49:10 | 显示全部楼层
前排顶,很好!
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

yichong | 2021-12-16 09:09:08 | 显示全部楼层
顶起出售广告位
aaaa
村长黑科技是专业提供项目资源的服务的村长黑科技平台,如合购网赚项目、引流推广软件、软件程序开发等项目就选村长黑科技平台,参与或发布项目定制各种软件就来村长黑科技平台
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则