初学红黑树

面试当中经常会问到红黑树,由于自身数据结构基础不扎实,现在补补红黑树。

参考文章:高性能服务器开发公众号,好好学算法系列文章。

什么是红黑树?
红黑树是一种特殊的二叉搜索树,红黑树的每个节点上都有存储位表示节点的颜色,红或者黑。
什么是二叉搜索树?
就是树的所有节点满足:左孩子的值小于父结点,右孩子的值大于父结点。

红黑树的特性:
1.节点要么是红色,要么是黑色
2.根节点是黑色
3.叶子节点是黑色(NULL)
4.如果一个节点是红色,则它的孩子一定是黑色
5.每条从节点到叶子节点的路径上黑色节点的数目是相同的     思考:这个特性有什么用呢?

红黑树已经应用在了一些地方:
Java: TreeSet,TreeMap
C++ STL: set, Map
Linux: epoll模型中据说也使用到了红黑树





全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-18 18:30
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务