请你回答一下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底层实现都是使用的红黑树。
-
本文向大家介绍请介绍一下红黑树？相关面试题，主要包含被问及请介绍一下红黑树？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时
-
本文向大家介绍请你回答一下epoll怎么实现的？相关面试题，主要包含被问及请你回答一下epoll怎么实现的？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： Linux epoll机制是通过红黑树和双向链表实现的。 首先通过epoll_create()系统调用在内核中创建一个eventpoll类型的句柄，其中包括红黑树根节点和双向链表头节点。然后通过epoll_ctl()系统调用，向epol
-
本文向大家介绍请你说一说map和unordered_map的底层实现？相关面试题，主要包含被问及请你说一说map和unordered_map的底层实现？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： map底层是基于红黑树实现的，因此map内部元素排列是有序的。而unordered_map底层则是基于哈希表实现的，因此其元素的排列顺序是杂乱无序的。
-
本文向大家介绍请你回答一下野指针是什么？相关面试题，主要包含被问及请你回答一下野指针是什么？时的应答技巧和注意事项，需要的朋友参考一下 野指针就是指向一个已删除的对象或者未申请访问受限内存区域的指针。
-
本文向大家介绍请你说明一下TreeMap的底层实现？相关面试题，主要包含被问及请你说明一下TreeMap的底层实现？时的应答技巧和注意事项，需要的朋友参考一下 考点：集合 TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。 红黑树的插入、删除、遍历时间复杂度都为O(lgN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑
-
本文向大家介绍请你回答一下map和unordered_map优点和缺点？相关面试题，主要包含被问及请你回答一下map和unordered_map优点和缺点？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 对于map，其底层是基于红黑树实现的，优点如下： 1)有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作 2)map的查找、删除、增加等一系列操作时间复杂度稳定