说下红黑树的五个性质

扫描上方二维码  关注：七月在线实验室 

后台回复：100   免费领取【机器学习面试100题】PDF版一份

今日面试题分享

说下红黑树的五个性质

参考答案：

解析：

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

以下即为一颗红黑树。

红黑树作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下二叉查找树的一般性质。

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

    

1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

    

2.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

    

3.任意节点的左、右子树也分别为二叉查找树。

   

4.没有键值相等的节点（no duplicate nodes）。

    

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。

但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：

    

1.每个结点要么是红的要么是黑的。  

    

2.根结点是黑的。  

    

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  

    

4.如果一个结点是红的，那么它的两个儿子都是黑的。  

    

5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 

    

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

更多请参见此文：《教你初步了解红黑树》

（链接：http://blog.csdn.net/v_july_v/article/details/6105630）

题目来源：七月在线官网（www.julyedu.com）——面试题库——面试大题——数据结构

今日学习推荐

【机器学习集训营第八期】

火热报名中

2019年4月15日开课

前50人特惠价:14399 

报名加送18VIP[包2018全年在线课程和全年GPU]

且两人及两人以上组团还能各减500元

有意的亲们抓紧时间喽

咨询/报名/组团可添加微信客服

julyedukefu_02

扫描下方二维码

免费试听

☟

长按识别二维码

更

多

干

货

请猛戳右边二维码

公众号ID

julyedulab

咨询，查看课程，请点击“阅读原文”

「 点个在看吧！ 」