为什么STL系统的底层图应用到红黑树上呢？

请回答为什么将底图应用到红黑树上。

参考答案：

1。红黑树：

红黑树是二叉查找树，但每个节点都增加了一个存储位来表示该节点的颜色，可以是红色也可以是黑色（黑色不是红色）。通过限制从根到叶的所有路径中每个节点的着色方式，红黑树可确保没有路径的长度是另一条路径的两倍。因此，红黑树是一种弱二叉树，相对于要求严格的AVL树来说，旋转次数较少，所以当查找、插入和删除次数较多时，常采用红黑树。

属性：

1。每个节点都是红色或黑色

2。底座为黑色；

3。每个叶子节点（叶子节点是NULL指针或树底部的NULL节点）都是黑色的；

4。如果一个节点是红色的，那么它的子节点必须是黑色的。

5。对于所有节点，叶点树中到NULL指针的每条路径都包含黑色节点的数量；

2。平衡二叉树（AVL树）：AVL树中推荐使用红黑树。

平衡二叉树，也称为AVL树，是一种特殊的二叉分类树。左右子树是平衡二叉树，左右树的高度差的绝对值不大于1。所有作为根的节点不大于1。AVL树。那么平衡二叉树中任意节点的平衡因子可以分别为-1、0、1。如果二叉树中某个节点的平衡系数的绝对值大于1，则该二叉树是不平衡的。

3。红黑木相对AVL木的优点：

AVL木非常平衡。频繁的插入和删除会造成频率不平衡，导致效率下降；红黑木不是很平衡，可以认为是木头。共识，包括两轮，删除三轮。

所以进行红黑树查找、插入和删除都是O(logn)，而且性能流畅，所以STL中很多系统，包括map的实现，都使用红黑。