红黑树插入和删除原理

48 阅读 0 评论 32 点赞

我是靠谱客的博主稳重舞蹈，最近开发中收集的这篇文章主要介绍红黑树插入和删除原理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

红黑树本质是一颗二叉查找树，增加了着色以及相关的性质，使得红黑树的查找，插入，删除的时间复杂度最坏为O(log n)。

一、红黑树相对二叉查找树来说，有以下五个性质。

a.红黑树的节点不是红色就是黑色

b.红黑树中根节点必是黑色。

c.红黑树上的节点时红色，它的两个子节点必须是黑色

d.树中任意一个节点到叶子结点的路径上的黑色节点数目相同

f.每个叶子节点都是黑色

二、理解左旋与右旋

当对红黑树进行删除或者是插入工作时，为了保证树的平衡与性质，必须要对红黑树进行调整，调整时可能需要进行旋转操作。通过对节点的着色以及树的旋转操作，来对红黑树进行插入或者是删除节点等操作。当父节点颜色为红色，需要通过旋转或者是颜色改变来维护红黑树的性质。

1.左旋,以下是左旋转的C++源码（来源于STL源码剖析）

inline void _rb_tree_rotate_left(_rb_tree_node_base*x,_rb_tree_node_base*&root)

{

x为旋转点

_rb_tree_node_base*y=x->right;//令y为旋转点的右节点

x->right=y->left;

if(y->left!=0)

{

y->left->parent=x;//设定父节点

}

//令y完全顶替x的地位

y->parent=x->parent;

if(x==root) //如果x为根节点

root=y;

else if(x==x->parent->left)//如果x为其父节点的左节点

x->parent->left=y;

else //如果x为父节点的右节点

x->parent->left=y;

y->left=x;

x->parent=y;

}

2.右旋,以下是右旋转的C++源码（来源于STL源码剖析）

inline void _rb_tree_rotate_left(_rb_tree_node_base*x,_rb_tree_node_base*&root)

{

x为旋转点

_rb_tree_node_base*y=x->left;//令y为旋转点的右节点

x->left=y->right;

if(y->right!=0)

{

y->right->parent=x;//设定父节点

}

//令y完全顶替x的地位

y->parent=x->parent;

if(x==root) //如果x为根节点

root=y;

else if(x==x->parent->lright)//如果x为其父节点的左节点

x->parent->right=y;

else //如果x为父节点的右节点

x->parent->left=y;

y->right=x;

x->parent=y;

}

如果用到双旋转，只是左旋和右旋转的结合应用，这里不一一细描述。树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。

三、红黑树的插入节点

通过红黑树的性质的分析，插入节点会产生四种不同的典型情况，分析以下图RB-Tree分别插入3,8,35,75根据二叉查找树的规则，我们分别得到以下图的插入位置，我们发现它们都破坏了红黑树的规则，我们必须调整树形，也就是旋转树形以及改变节点颜色。（以下灰色为红色，深色为黑色）。

以上1.2.3.4为四种不符合红黑树的四种情况，破外了红黑树的性质，我们必须通过旋转树或者是调整节点颜色。为了方便定义，让我们首先为了这些特殊节点定义一些代名，以下讨论将沿用这些代名。假设新节点为X,其父节点为P,祖父节点为G，伯父节点（父亲之兄弟节点）为S，曾祖父节点为GG，现在根据二叉查找树的规则，新节点必然是叶节点。根据红黑树规则4，X必为红色。若P为红色（这就违反了规则3，必须调整树形）则G为黑色（原为RB-tree,必须遵循规则3）。于是，根据X的插入位置以及外围的节点（S和GG）的颜色，有四种以下典型情况。

1.S为黑且X为外侧插入。对此情况，我们队P，G做了一次但旋转，并更改P,G颜色，即可重新满足红黑树的规则3。见下图