初学红黑树

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

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

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

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

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





全部评论

相关推荐

zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
07-22 11:12
门头沟学院 Java
不是,我就随手投的怎么还真发面试啊
皮格吉:大厂特别快的——来自已经被共享中
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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