请你回答一下map底层为什么用红黑树实现?
-
参考回答:
1、红黑树:
红黑树是一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树,相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,通常使用红黑树。
性质:
\1. 每个节点非红即黑
\2. 根节点是黑的;
\3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;
\4. 如果一个节点是红色的,则它的子节点必须是黑色的。
\5. 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
2、平衡二叉树(AVL树):
红黑树是在AVL树的基础上提出来的。
平衡二叉树又称为AVL树,是一种特殊的二叉排序树。其左右子树都是平衡二叉树,且左右子树高度之差的绝对值不超过1。
AVL树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
3、红黑树较AVL树的优点:
AVL 树是高度平衡的,频繁的插入和删除,会引起频繁的rebalance,导致效率下降;红黑树不是高度平衡的,算是一种折中,插入最多两次旋转,删除最多三次旋转。
所以红黑树在查找,插入删除的性能都是O(logn),且性能稳定,所以STL里面很多结构包括map底层实现都是使用的红黑树。
-
为什么 std::map 被实现为红黑树?
2022-07-28 关注 0 浏览21 1答案
-
Hashmap底层原理?Treemap底层原理?为什么用红黑树不是平衡二叉树或者普通二叉树?
2021-09-18 关注 0 浏览211 1答案
-
请你说明一下TreeMap的底层实现?
2020-01-30 关注 0 浏览526 1答案
-
请你回答一下map和unordered_map优点和缺点?
2020-01-30 关注 0 浏览557 1答案
-
以下哪个数据结构底层是用红黑树实现的?()
2022-03-03 关注 0 浏览19 1答案
-
请介绍一下红黑树?
2020-01-31 关注 0 浏览2217 1答案
-
请你回答一下epoll怎么实现的?
2020-01-30 关注 0 浏览571 1答案
-
请你回答一下栈和堆的区别,以及为什么栈要快?
2020-01-30 关注 0 浏览455 1答案
-
请你来说一下map和set有什么区别,分别又是怎么实现的?
2020-01-05 关注 0 浏览1565 1答案
-
请你说一说map和unordered_map的底层实现?
2020-01-30 关注 0 浏览869 1答案