红黑树的定义与运用场景
一、定义
红黑树的五个性质:
一般的,红黑树(一棵自平衡的排序二叉树),满足以下性质,即只有满足以下性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
抓住了红黑树的那5个性质,分开记忆。
如,
1.红黑红黑,要么是红,要么是黑;
2.根结点是黑;
3.每个叶结点是黑;
4.一个红结点,它的俩个儿子必然都是黑的;
5.每一条路径上,黑结点的数目等同。
五条性质,合起来,来句顺口溜就是:(1)红黑 (2)黑 (3)黑 (4&5)红->黑 黑
二、运用场景
java中的TreeSet,TreeMap,广泛用在C++的STL中。如map和set都是用红黑树实现的