本文已参加「新人创作礼」活动，一起敞开创作之路。

红黑树的性质

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用处是实现相关数组。它在1972年由鲁道夫贝尔创造，被称为”对称二叉B树”，它现代的名字源于Leo J. Guibas和罗伯特塞奇威克于1978年写的一篇论文。红黑树的结构杂乱，但它的操作有着良好的最坏情况运行时刻，并且在实践中高效：它可以在{\displaystyle {\text{O}}(\log n)}时刻内完结查找、刺进和删去，这儿的{\displaystyle n}是树中元素的数目。

1. 黑红树肯定是一个二叉排序树，但不一定是平衡二叉树
2. 性质口诀：左根右，根叶黑，不红红，黑路同
   • 满意二叉排序树，则左结点 < 根节点 < 右结点（左根右）
   • 每个结点是赤色或许黑色
     • 根结点一定是黑色
     • 叶子结点（一般是虚拟的外部结点、NULL结点）一定是黑色
   • 不存在两个相邻的红结点（一个红结点的父结点和子结点一定是黑色）
   • 对每个结点，从该结点就任一叶子结点的简略途径上，所含黑结点的数量相同
3. 结论
   • 从根到叶结点的最长途径不大于(≤)最短途径的2倍
   • 有n个内部结点的红黑树的高度 h ≤ 2log2(n+1)

这儿看不懂问题不大，对照着例子来理解即可

红黑树的刺进

1. 规矩

   

举例说明（完整版）

这儿只刺进了5个元素，但是后续的刺进操作与当时的差不多。

需要知道的是红黑树是根据平衡二叉树的刺进操作的，所以想要学好红黑树的刺进的条件是理解平衡二叉树的刺进