首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Java面试:2021.05.13

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外,还要满足下面的性质: 性质1:每个节点要么是黑色,要么是红色。 性质2:根节点是黑色。 性质3:每个叶子节点(NIL)是黑色。 性质4:每个红色结点的两个子结点一定都是黑色。 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 应用: 1、java8 hashmap中链表转红黑树。 优势: 时间复杂度从O(n)-->O(logn) ,且自旋开销较其他树较低(不用整体平衡)。 2、epoll在内核中的实现,用红黑树管理事件块(文件描述符)。 优势: 因为内核态需要维护一个长久存放fd的数据结构,而fd变动十分频繁,且需要支持快速查询,且所以红黑树很适合。 红黑树可以判断是否是重复的fd。 3、Java的TreeMap实现 相对与hashMap优势,内部key保持有序,且支持自定义排序比较器。 适用场景,对数据需要排序统计。 4、linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

04
您找到你想要的搜索结果了吗?
是的
没有找到
领券