1. 2-3-4树介绍
2-3-4是四阶的B树，他属于一种多路查找树，他的结构有以下限制：
所有叶子结点都拥有相同的深度。
结点只能是2-结点，3-结点，4-结点之一。
- 2-结点：包含1个元素的结点，有2个子结点。
- 3-结点：包含2个元素的结点，有3个子结点。
-
4-结点：包含3个元素的结点，有4个子结点。
所有节点必须至少包含1个元素。
元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子树结点，小于右子树结点。而且结点有多个元素时，每个元素大于他左边和他左子树的元素。
下图是一个典型的2-3-4树：
2-3-4树
2-3-4树的生成
234树添加数据，有两种情况。
第一种：添加数据的节点的数据个数小于3个直接添加。
第二种：添加数据的节点的数据个数等于3个，需要将节点的3个数据分成3个234树节点，中间的数据成为左右两边数据的双亲节点，然后根据添加数据的大小加到左右两边的子节点中。
这种向上分裂添加数据的有点在于能够保证左右子树高度一致，无需平衡234树的左右高度。
2-3-4树和红黑树的等价关系
2-3-4树转化为红黑树
2. 红黑树
红黑树，Red-Black Tree「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:
1.每个节点要么是黑色，要么是红色。
2.根节点是黑色。
3.每个叶子节点(NIL)是黑色。
4.每个红色结点的两个子结点一定都是黑色。
5.任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
红黑树能自平衡，它靠的是什么?三种操作:左旋、右旋和变色
enum RBColor{
BLACK,
RED
};
typedef int KEY_TYPE;
typedef struct RBNode{
struct RBNode *parent;
struct RBNode *left;
struct RBNode *right;
enum RBColor color;
KEY_TYPE key;
void *value;
}RBNode, *RBTree;
//左旋转
void leftRotate(RBTree *root,RBNode *node)
{
RBNode *parent = node->parent;
RBNode *right = node->right;
RBNode *rleft = right->left;
right->left = node;
node->parent = right;
node->right = rleft;
if(rleft)
rleft->parent = node;
right->parent = parent;
if(parent == NULL){
*root = right;
}else if(parent->left == node)
parent->left = right;
else if (parent->right == node)
parent->right = right;
}
//右旋转
void rightRotate(RBTree *root,RBNode *node)
{
RBNode *parent = node->parent;
RBNode *left = node->left;
RBNode *lright = left->right;
left->right = node;
node->parent = left;
node->left = lright;
if(lright)
lright->parent = node;
left->parent = parent;
if(parent == NULL)
*root = left;
else if (parent->left == node)
parent->left = left;
else if (parent->right == node)
parent->right = left;
}
enum RBColor colorOf(RBNode *node)
{
return node!=NULL ? node->color : BLACK;
}
void setColor(RBNode *node, enum RBColor color)
{
if(node == NULL)
return;
node->color = color;
}
插入操作
1. 3结点插入结点情况
3结点插入子结点
3结点插入子结点情况
以下情况需要调整：
四种情况需要调整
第一种调整情况
第二种调整情况
- 第二种先左旋然后跟第一种情况相同
- 后两种调整情况跟这两种相同，只是方向相反而已。
2. 4结点插入子结点情况
4节点插入子结点
4结点插入子结点情况
- 这些情况都需要调整
第一种调整情况
- 其他三种情况都是将父结点和叔叔结点变成黑色，爷爷结点变红色
void fixAfterInsert(RBTree *root,RBNode* node);
//二叉树插入操作，非递归
void insert(RBTree root,KEY_TYPE key, void *value)
{
RBNode *t = root;
if(t == NULL)
{
root = (RBNode *)malloc(sizeof(RBNode));
root->key = key;
root->value = value;
root->parent = NULL;
return;;
}
int cmp;
//1.找到插入位置(找到新增结点的父结点)
RBNode *parent;
do {
parent = t;
cmp = key - t->key;
if(cmp < 0)
t = t->left;
else if (cmp > 0)
t = t->right;
else
{
t->value = value;
return;
}
} while (t != NULL);
RBNode *node = (RBNode *)malloc(sizeof(RBNode));
node->key = key;
node->value = value;
node->parent = parent;
if(cmp < 0)
parent->left = node;
else
parent->right = node;
//旋转和变色 调整红黑树的平衡
fixAfterInsert(&root, node);
}
void fixAfterInsert(RBTree *root,RBNode* node)
{
node->color = RED;
// 2结点不用调整，3 4结点才需要调整
while(node != NULL && node != *root && node->parent->color == RED){
if(node->parent == node->parent->parent->left){
//需要调整的只剩下4种情况，有叔叔节点和没有叔叔节点
RBNode *uncle = node->parent->parent->right;
if(colorOf(uncle) == RED){
//叔叔节点如果是红色，表示有叔叔节点
//变色+循环
//父亲和叔叔变为黑色 爷爷变为红色
setColor(node->parent, BLACK);
setColor(uncle, BLACK);
setColor(node->parent->parent, RED);
//循环往上处理
node = node->parent->parent;
}else{ //没有叔叔节点
if(node == node->parent->right){
//如果是右节点需要将父结点向左旋转
node = node->parent;
leftRotate(root, node);
}
//父亲变为黑色 爷爷变为红色
setColor(node->parent, BLACK);
setColor(node->parent->parent, RED);
//爷爷结点向右旋转
rightRotate(root, node->parent->parent);
}
}else{
//需要调整的也是4种情况，刚好和上面4种情况左右相反
RBNode *uncle = node->parent->parent->left;
if(colorOf(uncle) == RED){
setColor(node->parent, BLACK);
setColor(uncle, BLACK);
setColor(node->parent->parent, RED);
//循环往上处理
node = node->parent->parent;
}else{
if(node == node->parent->left){
node = node->parent;
rightRotate(root, node);
}
//父亲变为黑色 爷爷变为红色
setColor(node->parent, BLACK);
setColor(node->parent->parent, RED);
//爷爷结点向左旋转
leftRotate(root, node->parent->parent);
}
}
}
setColor(*root,BLACK);
}
红黑树的删除操作
- 删除规则按二叉搜索树的删除规则：
- 要删除的结点是叶子结点：直接删除，并将父结点指针置为NULL
- 要删除的结点有一个孩子结点：删除该结点，并将父结点的指针指向这个孩子结点
- 要删除的结点有左右子树：用另一个结点替代被删除的结点：左子树最大元素或右子树的最小元素
-
红黑树删除和调整：
二叉树的删除转换为2-3-4树的删除删除的其实就是2-3-4树的最底层
其实就是删除2节点3节点4节点
删除3和4节点的时候可以通过本身的替换处理掉但是删除2节点的时候，自己是不能够处理的
- 删除节点自己能够搞定
- 删除节点自己搞不定，向兄弟节点借 兄弟节点借
- 删除节点自己搞不定，向兄弟节点借 兄弟节点不借
情况2的调整
情况3的调整
RBNode *Find(RBTree root, KEY_TYPE key)
{
RBNode *node = root;
while (node) {
if(key < node->key)
node = node->left;
else if (key > node->key)
node = node->right;
else
break;
}
return node;
}
RBNode *FindMax(RBNode *RBT)
{
if(RBT)
while (RBT->right) {
RBT = RBT->right;
}
return RBT;
}
RBNode *FindMin(RBNode *RBT)
{
if(RBT)
while (RBT->left) {
RBT = RBT->left;
}
return RBT;
}
void fixAfterDelete(RBTree root,RBNode *node);
void* delete(RBTree *root, KEY_TYPE key)
{
RBNode *node = Find(*root, key);
RBNode *tmp ,*parent,*child=NULL;
if(node == NULL)
return NULL;
void *oldValue = node->value;
if(node->left != NULL && node->right != NULL)
{
RBNode *rightMin = FindMin(node->right);
node->key = rightMin->key;
node->value = rightMin->value;
node = rightMin;
}
tmp = node;
parent = node->parent;
child = node->left ? node->left : node->right;
if(child){
child->parent = parent;
if(parent == NULL)
*root = child;
else if(parent->left == node)
parent->left = child;
else if(parent->right == node)
parent->right = child;
if(colorOf(node) == BLACK)
{
fixAfterDelete(*root,child);
}
}else{
if(colorOf(node) == BLACK)
{
fixAfterDelete(*root,node);
}
if(parent == NULL)
*root = child;
else if(parent->left == node)
parent->left = child;
else if(parent->right == node)
parent->right = child;
}
free(node);
return oldValue;
}
/**
删除结点后的调整工作
2-3-4树删除操作
1. 删除3/4结点 自己能搞定的
2. 删除2结点 自己搞不定，需要兄弟节点借，兄弟节点借
父亲结点下去，兄弟节点找个结点替换父亲结点位置
3. 删除2结点 自己搞不定，需要兄弟借 兄弟不接
*/
void fixAfterDelete(RBTree root,RBNode *node)
{
//情况2和3
while (node != root && colorOf(node) == BLACK){
//判断node是父结点的左孩子还是右孩子
if(node == node->parent->left){
//1.找到兄弟节点
RBNode *rNode = node->parent->right;
//判断是不是真正的兄弟节点
if(colorOf(rNode) == RED){
//不是真正的兄弟结点 变色 旋转
setColor(rNode, BLACK);
setColor(node->parent, RED);
leftRotate(&root, node->parent);
rNode = node->parent->right;
}
//当兄弟结点一个子结点都没有 不借
if(colorOf(rNode->left) == BLACK && colorOf(rNode->right) == BLACK){
//3.兄弟结点 不借
setColor(rNode, RED);
node = node->parent;
}else{
//2.兄弟结点 借
//如果兄弟节点的子结点是其左子结点 需要先变色 右转一次
if(colorOf(rNode->right) == BLACK){
//右子节点为空，左节点不为空
setColor(rNode->left, BLACK);
setColor(rNode, RED);
rightRotate(&root, rNode);
rNode = node->parent->right;
}
//需要根据父结点做一次左旋操作 变色
setColor(rNode, colorOf(node->parent));
setColor(node->parent, BLACK);
setColor(rNode->right, BLACK);
leftRotate(&root, node->parent);
node = root;
}
}else{
//1.找到兄弟节点
RBNode *lNode = node->parent->left;
//判断是不是真正的兄弟节点
if(colorOf(lNode) == RED){
//不是真正的兄弟结点 变色 旋转
setColor(lNode, BLACK);
setColor(node->parent, RED);
leftRotate(&root, node->parent);
lNode = node->parent->left;
}
//当兄弟结点一个子结点都没有 不借
if(colorOf(lNode->left) == BLACK && colorOf(lNode->right) == BLACK){
//3.兄弟结点 不借
setColor(lNode, RED);
node = node->parent;
}else{
//2.兄弟结点 借
//如果兄弟节点的子结点是其右子结点 需要先变色 左转一次
if(colorOf(lNode->left) == BLACK){
//左子节点为空，右节点不为空
setColor(lNode->right, BLACK);
setColor(lNode, RED);
leftRotate(&root, lNode);
lNode = node->parent->left;
}
//需要根据父结点做一次左旋操作 变色
setColor(lNode, colorOf(node->parent));
setColor(node->parent, BLACK);
setColor(lNode->right, BLACK);
rightRotate(&root, node->parent);
node = root;
}
}
}
//情况1：替换的结点为红色 我们只需要变色为黑色即可
setColor(node, BLACK);
}
