STL中map和set的原理(关联式容器)

map和set的底层实现主要通过红黑树来实现

红黑树是一种特殊的二叉查找树

1)每个节点或者是黑色,或者是红色 

2)根节点是黑色

3) 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]

4)如果一个节点是红色的,则它的子节点必须是黑色的

5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

特性4)5)决定了没有一条路径会比其他路径长出2倍,因此红黑树是接近平衡的二叉树。


更多精选文章
标签: 黑色、节点、叶子、nil、红黑树
一个创业中的苦逼程序员
笔试题


刷题


简历模板


AI算法


大数据


内推


推荐阅读:
阿里巴巴笔试面试大全
腾讯笔试面试大全
百度笔试面试大全
今日头条笔试面试大全
网易笔试面试大全
Google笔试面试大全
更多笔试面试大全
隐藏