map和set的底层实现主要通过红黑树来实现
红黑树是一种特殊的二叉查找树
1)每个节点或者是黑色,或者是红色
2)根节点是黑色
3) 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
4)如果一个节点是红色的,则它的子节点必须是黑色的
5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
特性4)5)决定了没有一条路径会比其他路径长出2倍,因此红黑树是接近平衡的二叉树。
标签: 黑色、节点、叶子、nil、红黑树
笔试题
刷题
简历模板
AI算法
大数据
内推