数据算法(红黑树)

每日福利

还在为智商过多而烦恼吗?还在为无处装逼而郁闷吗?赶紧抓起手上的电话,打开微信秘籍酷,查看今天的装逼巅峰话题红黑树!今天林药师亲自调制,无色无味,居家旅行装逼必备良品,服一剂神清气爽,服两剂目瞪口呆!

先来看一棵什么是树:

逻辑上的树,指的是组织结构的一种特殊关系,具体来说指的就是:这一堆数据中包含一个称之为根的节点,其他的节点又组成了若干棵树,成为根节点的后继。

再来看什么是程序逻辑中的树:

仔细观察上面这棵树,你会发现,虽然他有良好的“搜索”特性,也就是:你可以利用其节点之间的大小关系,很容易地从根节点开始往下走找到你要的节点,但他却无法保证这种搜索所需要的时间的长短,因为建立这棵树时节点的随机性可能会导致他极其“不平衡”,什么叫不平衡呢?请看:

像上面这样的一条腿太长的树,就是不平衡的,那怎么才能平衡呢?噔噔噔,红黑树隆重出场,首先是定义:

1,树中的节点都是有颜色的,要么红色,要么黑色。

2,树根节点的颜色是黑色的。

3,空节点的颜色算做黑色。

4,不能有连续的红色节点。

5,从任意一个节点开始到叶子的路径包含的黑色节点的个数相等

如果一棵二叉树满足以上条件,就会使得他不可能有出现:一条路径的长度是另一条路径的两倍以上,这个结论只需看一下4和5两点限制就明白了。这就是保证红黑树相对平衡的秘籍。请看:

在数据处理中,红黑树是另一位备受宠爱的明星,他不仅是Linux中非线性数据结构的标准算法,而且是JAVA中TreeMap、TreeSet机制、C++中的STL这些经典工具背后的强大逻辑支撑。

当然,像红黑树这样算法比较复杂的逻辑,是很难在三言两语中就搞透的,本文只是引入 一些基本概念,深入的逻辑分析、代码实现可以在我的书里看到。点击阅读原文可以找到。

本文分享自微信公众号 - 秘籍酷(mijiku040)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券