数据结构之红黑树详解

红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分应用了红黑树的变体。本文介绍了红黑树的基本性质和基本操作。红黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。红黑树的定义也是它的性质，有以下五条：。这五个性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。然而，红黑树上的插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量的颜色变更和不超过三次树旋转。[1] 如果P是黑色的，则整棵树不必调整便是红黑树。