数据结构中红黑树的插入

红黑树是一种自平衡二叉搜索树，其中树的每个节点都用红色或黑色着色。我们可以在红黑树上执行三种类型的操作——搜索、插入和删除。

假设我们必须在下面的红黑树中插入一个元素。

要在红黑树中插入元素，想法非常简单——我们执行插入就像在常规二叉树中插入一样。我们从根节点开始检查节点的颜色并将其插入特定位置。但是，在红黑树中应该有一些额外的过程来插入一个元素。

但是，我们应该知道红黑树在满足条件时是平衡的 -

• 每个根节点必须是黑色的。

• 每个节点不是红色就是黑色。

• 如果一个节点是红色的，那么它的子节点一定是黑色的。

• 从根到末端的路径必须包含相同数量的黑色节点。

如果我们想在红黑树中插入一个新节点，那么我们可以通过查看插入步骤来实现。

在红黑树中插入元素的步骤 -

• 检查树是否为空。如果树为空，则插入一个新节点并将其着色为黑色。（因为根节点必须始终为黑色）'

• 否则，如果树不为空，则将新节点作为叶节点插入到末尾并将其着色为红色。

• 如果新节点的父节点是红色并且它的邻居（父）节点也是红色然后翻转邻居和父和祖父母的颜色（如果它不是根节点否则只翻转父和邻居的颜色）即， 黑色的。

• 如果新节点的父节点是 Red 并且其相邻（父节点）节点为空或 NULL，则旋转（左-左或左-右旋转）新节点和父节点。

有两种类型的旋转可以应用——左左旋转和左右旋转。轮换仅适用于某些情况。条件是 -

• 如果新节点的父节点为 Red 且相邻节点为空或 NULL，则向左或向右旋转。

• 在 Left-Left Rotation 中，翻转父母和祖父母的颜色。将父母设为祖父母，将祖父母设为孩子。

算法

RBTreeInsertion(root,key)

//The color of the inserted new node is Red
color[key] <- Red
while(key≠root and color (p[key]=Red))
do if p[key]= left(p[p[key]])
   Then y←right[p[p[key]]
//如果新节点的父节点是红色（如果有祖父节点
root Node) Flip the color.
   if color[y]← Red
   then color(p[key])← Black
      color(p[p[key]])← Red
      key← p[p[key]]
   else if key← right[p[key]]
      then key← p[key]
      //当新节点的父节点为红色且其兄弟节点为 NULL 时
   LeftRotate(root,key)
   color(p[key]) ← Black
   color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else exchange then left and right elements to make it balance.
color(root)← Black