二进制搜索树是一种用于存储具有快速搜索功能的项目的数据结构。 这个想法是简单而巧妙的：“少留下，多留对”。 这是简单性结束的地方，平衡树的复杂问题开始了，因此它不会变成长分支。
在本文中，我们将给出一个定义，列出将元素放置在红黑树中的规则，考虑一种平衡算法，并整合示例中的内容。 我们将在“开发人员算法”课程中更详细地研究此主题以及其他类型的二进制搜索树。
红黑树是一种自平衡的二叉搜索树，它保证了树的高度从节点数到对数增长，并且可以快速执行搜索树的基本操作：添加，删除和搜索节点。
红黑树并不完全平衡，在某些地方其高度几乎可以变化两倍。 这样的假设不会渐进地影响元素搜索的速度，但是可以显着加快新元素的放置速度，因为您不必每次添加元素时都“摇一摇”树，有时候添加一个红色元素而不用触摸其他元素并且不改变“黑色高度”就足够了。
在红黑树中放置元素的规则
- 每个节点为红色或黑色； NIL叶子始终为黑色。
- 树的根总是黑的
- 每个红色节点的后代均为黑色
- 从任何节点到任何后代叶子的路径均包含相同数量的黑色节点。
插入新元素时，它会分配为红色。 要满足前两个规则，只需将新顶点重新绘制为所需的颜色即可。
考虑实施3分和4分的平衡规则。
在每个图中，假定我们已经添加了违反3规则的元素X，我们需要更改树的结构，以便执行3规则，并且不违反4。
顶点图例：
- X-违反规则第3段的添加元素。
- P-爸爸项目X
- G-元素X的祖父，元素P的父亲
- U是元素X的叔叔，元素P的兄弟，元素G的第二个儿子。
案例一-红叔叔
如果父亲和叔叔都是红色，那么我们可以将黑色从祖父级别“降低”到父亲级别，然后重新绘制节点，如图所示。 在这种情况下，“黑色高度”将保持不变，但是有可能违反元素G的规则3，因此，有必要递归调用此节点的进一步平衡。
案例二-一个黑人叔叔-父亲和祖父在不同的方向。
当父亲和祖父朝同一个方向走时，必须将这种结构引入第三种情况。 为此，您需要从儿子X到父亲做一个小转弯（本文不考虑转弯规则），并为元素R调用3种情况。
案例三-黑叔叔-父亲和祖父在同一边
在这种情况下，我们已经可以从父亲到祖父，再到黑人叔叔，并用黑色重涂P和红色重涂G。 作为该旋转的结果，将满足3规则。
确保也满足第四个规则。 假设在大转弯之前，元素G的黑色高度为N + 2。 然后，“已暂停”元素的高度将如下所示：
A = N + 1
B = N + 1
C = N + 1
D = N
E =N。
亲自了解一下，转动4条规则对所有元素都是正确的。
具体例子
现在，我们将考虑顺序插入元素1、2、3、4、5和6形成红黑树的过程。
由于元素1是根，因此我们只需对其重新粉刷即可满足规则1。
添加元素2后，将执行所有规则。
当添加元素3时，我们违反了规则3。 由于我们有一个黑人叔叔，一方面是祖父和父亲，所以我们使用第三个案例-转弯并重新粉刷。
添加元素4时，我们再次违反了规则3。 这次我们的叔叔是红色的，因此我们将第一种情况应用了重新粉刷-树的黑色高度将增加1。请注意。 平衡算法是针对祖父元素2额外启动的，元素2像根一样简单地重新涂成黑色。
插入元素5时，我们再次应用3格-大转弯并重新绘制顶点。 请注意，黑色高度没有改变。
添加元素6时，我们再次违反了规则3。 由于我们的叔叔是红色的，因此我们将第一种情况应用于重新粉刷，因此黑色高度没有改变。 平衡调用4个元素不会更改树中的任何内容，因为此元素不违反规则。
因此，我们在
“开发人员算法”课程中详细了解了平衡红黑树的问题，并详细介绍了该主题的算法示例以及其他各种二叉搜索树。