平衡树包括很多种类,常见的有B树、AVL树、红黑树等。
这些树都大致平衡,能保证最坏情况下为O(logN)的性能,因此广受大家的欢迎。 但是由于平衡机制的不同,这些树都有着不同的应用场景和不同的统计性能,其中B树主要用于文件系统、数据库等方面,而AVL树和红黑树多用于检索领域。
由于红黑树在平衡机制上比较灵活,因此能取得最好的统计性能,在Linux内核、STL源码中广为使用。
1)红黑树的定义 红黑树是指满足下列条件的二叉搜索树。
性质1:每个节点要么是红色,要么是黑色(后面将说明)。
性质2:所有的叶节点都是空节点,并且是黑色的。
性质3:如果一个节点是红色的,那么它的两个子节点都是黑色的。
性质4:节点到其子孙节点的每条简单路径都包含相同数目的黑色节点。
性质5:根节点永远是黑色的。
标签:黑色,AVL,红黑树,平衡,节点,性质 From: https://www.cnblogs.com/cnetsa/p/17004027.html