什么是红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

树的旋转

当我们在对红黑树进行插入和删除等 *** 作时，对树做了修改，那么可能会违背红黑树的性质。

为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋 *** 作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等 *** 作时，红黑树依然能保持它特有的性质（五点性质）。

红黑树的原理是通过进行插入和删除 *** 作时通过特定 *** 作保持二叉查找树的平衡，从而实现关联数组，存储有序的数据。它是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，其典型的用途就是实现关联数组。

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。

而由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

行为特征

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

性质1、节点是红色或黑色。

性质2、根节点是黑色。

性质3、所有叶子都是黑色。（叶子是NUIL节点）

性质4、每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

性质5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。