红黑树简介

红黑树

红黑树五个性质：

（1）节点是红色或者黑色

（2）根节点为黑色

（3）每个叶子节点为黑色

（4）每个红色节点的两个子节点均为黑色

（5）从任意节点到每个叶子节点的所有路径均包含相同数目的黑色节点。

红黑树最重要的性质：

从根到叶子节点的最长可能路径不多于最短可能路径的两倍长。红黑树大致上是平衡的，因此插入、删除和查找操作的最坏情况时间与树的高度成比例，因此其时间复杂度为O（logn），因此红黑树最坏情况下的插入、删除和查找操作的效率优于普通的二叉查找树。