简单讲一下B树B+树
这些树的作用，主要都体现于增删改查。
而为了性能的增强，从二叉树开始一步步进化，有了有序二叉树，然后到平衡二叉树，然后到了23树。
但23树依然不太优越。
假如有1w的数据，那么23树的层数就会很多，层数越多，增删改查消耗的时间也就越多。
如果我们希望它能够在数据量多的时候，层数少，那么就是每一层能够保存更多的数据，这样子虽然查找快了一些，但每一层又臃肿了一些。
不同的数据结构各有优越，要考虑不同情况使用不同的数据结构。
B树（B_ B-）：
在23树的基础上引入M值的概念，M值是变化的，相对23树而言更加灵活。
简单举例：23树就是M值为3的B树。
如图，B树和23树的原理一样，B的M为4，即表示到达4个分裂：
B+树：
B树加上2个特性。
数据只存在叶子节点上叶子节点之间用指针连接
这样之后，nb的就是第二个特性（叶子节点之间用指针连接）：
做链表一样，而上面的6和73是索引。
比如要找14，链表的话是一个一个找过去。
而这个通过索引6和73，直接找到大致区间进行搜索。
平衡二叉树优化，为红黑二叉树：
在不怎么降低AVL查找效率的情况下，大幅度优化增删效率。
红黑二叉树相对AVL树：稍微降低查找效率（不是绝对平衡），增删效率加快很多（3次旋转可以搞定）
红黑二叉树规则：
树中节点 非红即黑根和叶子都是黑节点（空节点算黑节点），枝干非红即黑红色节点的孩子必定是黑色从一个节点到这个节点的任意一个子孙节点，路径上包含相同个数的黑色节点
如图：
红黑二叉树插入步骤：
新节点统一着色为红色
情况一：新节点为根节点，着色为黑
情况二：新节点的父节点颜色为黑，啥都不干
情况三：新节点的父节点颜色为红：
3.1被插入节点父节点颜色为红色，并且叔叔节点颜色为黑色，并且插入节点是其父节点的左孩子
怎么做：3.1.1父节点设置为黑色
3.1.2爷爷节点设置为红色
3.1.3以其父节点为轴右旋
3.2被插入节点父节点颜色为红色，并且叔叔节点颜色为黑色，并且插入节点是其父节点的右孩子
怎么做：3.2.1以其父节点为轴左旋
3.2.2新节点设置为黑色
3.3被插入节点父节点颜色为红色，并且叔叔节点颜色为红色
怎么做：3.3.1父节点设置为黑色
3.3.2叔叔节点设置为黑色
3.3.3爷爷节点设置为红色
3.3.4把爷爷节点当成新节点插入
代码如下：
#include
#include
//辅助宏
#define RED 0
#define BLACK 1
//获取节点的颜色
#define COLOR(x) ((x)->color)
//获取当前节点的父节点
#define PARENTNODE(x) ((x)->parentNode)
//设置当前节点的父节点
#define SET_PARENT(x,p) ((x)->parentNode=(p))
//设置当前节点的颜色
#define SET_COLOR(x,c) ((x)->color=(c))
//设置当前节点颜色为黑色
#define SET_BLACK(x) ((x)->color=BLACK)
//设置当前节点颜色为红色
#define SET_RED(x) ((x)->color=RED)
//判断当前节点颜色是否为黑色
#define IS_BLACK(x) ((x)->color==BLACK)
//判断当前节点颜色是否为红色
#define IS_RED(x) ((x)->color==RED)
//红黑树的结构体
struct RBTreeNode
{
unsigned int color; //颜色
int key; //关键字
struct RBTreeNode* LChild;
struct RBTreeNode* RChild;
struct RBTreeNode* parentNode;
}
typedef; struct RBTreeNode NODE;
typedef struct RBTreeNode* LPNODE;
struct RBTree
{
LPNODE root;
int treeSize;
}
typedef; struct RBTree RBTREE;
typedef struct RBTree* LPRBTREE;
LPNODE createNode(int key)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
newNode->key = key;
newNode->LChild = NULL;
newNode->RChild = NULL;
newNode->parentNode = NULL;
newNode->color = BLACK;
return newNode;
}
//创建树
LPRBTREE createRBTree()
{
LPRBTREE tree = (LPRBTREE)malloc(sizeof(RBTREE));
tree->root = NULL;
return tree;
}
//左旋
void L_Rotation(LPRBTREE tree, LPNODE x)
{
//1.拿到x的右边 y怎么表示？
LPNODE y = x->RChild;
//2.y的左边成为x的右边
x->RChild = y->LChild;
//3.判断下y的左边是不是空的
//父节点的处理
if (y->LChild != NULL) {
y->LChild->parentNode = x;
}
//y替换了x ,所以x的父节点就是y的父节点
y->parentNode = x->parentNode;
//如果x是根不，循环后，红黑树的根改变
if (x->parentNode == NULL) {
tree->root = y;
}
else {
//不是根部判断x是在原来父节点左边还是右边
if (x->parentNode->LChild == x) {
x->parentNode->LChild = y;
}
else {
x->parentNode->RChild = y;
}
}
//处理一下x的位置
y->LChild = x;
x->parentNode = y;
}
//右旋
void R_Rotation(LPRBTREE tree, LPNODE y)
{
//拿到x节点
LPNODE x = y->LChild;
y->LChild = x->RChild;
if (x->RChild != NULL)
{
x->RChild->parentNode = y;
}
//处理x和y的父节点
x->parentNode = y->parentNode;
if (y->parentNode == NULL)
{
tree->root = x;
}
else
{
if (y == y->parentNode->LChild)
{
y->parentNode->LChild = x;
}
else
{
y->parentNode->RChild = x;
}
}
//
x->RChild = y;
y->parentNode = x;
}
//1.插入
//1.1 当作BST(有序二叉树)做一个插入
//1.2 调整成为红黑树
void insertAdjustTree(LPRBTREE tree, LPNODE node)
{
LPNODE parent, gparent;
while ((parent = PARENTNODE(node)) && IS_RED(parent))
{
gparent = PARENTNODE(parent);
//三种情况分析
if (parent == gparent->LChild)
{//父节点是祖父节点的左孩子
//No.1 U=RED;//对应笔记中的情况三 . 3
{
LPNODE uncle = gparent->RChild;
if (uncle && IS_RED(uncle))
{
SET_BLACK(uncle); //uncle->color=BLACK;
SET_BLACK(parent); //parent->color=BLACK;
SET_RED(gparent); //gpranet->color=RED;
node = gparent;
continue;
}
}
//No.2 u=BLACK S=R //对应笔记中 情况三.1
if (parent->RChild == node)
{
LPNODE temp;
L_Rotation(tree, parent);
temp = parent;
parent = node;
node = temp;
}
//No.3 U=BLACK S=L //对应笔记中 情况三.2
SET_BLACK(parent);
SET_RED(gparent);
R_Rotation(tree, gparent);
}
else
{//父节点是祖父节点的右孩子
//No.1 //对应笔记中的情况三 . 3
{
LPNODE uncle = gparent->LChild;
if (uncle && IS_RED(uncle))
{
SET_BLACK(uncle); //uncle->color=BLACK;
SET_BLACK(parent); //parent->color=BLACK;
SET_RED(gparent); //gpranet->color=RED;
node = gparent;
continue;
}
}
//No.2
if (parent->LChild == node) //对应笔记中 情况三.1
{
LPNODE temp;
R_Rotation(tree, parent);
temp = parent;
parent = node;
node = temp;
}
SET_BLACK(parent);//对应笔记中 情况三.2
SET_RED(gparent);
L_Rotation(tree, gparent);
}
}
SET_BLACK(tree->root);// 对应笔记中 情况一：新节点是根节点
}
//1.1 当作BST做一个插入
void insertNode(LPRBTREE tree, LPNODE node)
{
//当作BST做一个插入
LPNODE y = NULL;
LPNODE x = tree->root;
while (x != NULL)
{
y = x; //记录父节点
if (node->key < x->key)
{
x = x->LChild;
}
else
{
x = x->RChild;
}
}
//新节点应该插在y节点的下面
SET_PARENT(node, y);
if (y != NULL)
{
if (node->key < y->key)
{
y->LChild = node;
}
else
{
y->RChild = node;
}
}
else //树是空的，第一次插入节点就要成为根节点
{
tree->root = node;
}
SET_COLOR(node, RED); //插入节点着色红色
//2.按照红黑树的规则情况去调整二叉树成为红黑树
insertAdjustTree(tree, node);
}
void printCurNode(LPNODE curNode)
{
printf("%d:%s\n", curNode->key, curNode->color ? "BLACK" : "RED");
}
void preOrder(LPNODE root)
{
if (root != NULL)
{
printCurNode(root); //printf("%d:%s\n", curNode->key, curNode->color ? "BLACK" : "RED");
preOrder(root->LChild);
preOrder(root->RChild);
}
}
//2.红黑树的删除
//2.1 当做BST 去做删除
//2.2 调整
void deleteAdjustTree(LPRBTREE tree, LPNODE node, LPNODE parent)
{
LPNODE other;
while (!node || IS_BLACK(node) && node != tree->root)
{
if (parent->LChild == node) //node是其父节点的左孩子
{
other = parent->RChild;
if (IS_RED(other))//node的兄弟为红色节点
{
//No.1 xB=RED
SET_BLACK(other);
SET_RED(parent);
L_Rotation(tree, parent);
other = parent->RChild;
}
if ((!other->LChild) || IS_BLACK(other->LChild) &&
(!other->RChild) || IS_BLACK(other->RChild))
{
//No.2 xB=BLACK
SET_RED(other);
node = parent;
parent = PARENTNODE(node);
}
else
{
if (!other->RChild || IS_BLACK(other->RChild))
{
//No.3 xB=BLACK xB->LChild=RED, xB->RChild=BLACK;
SET_BLACK(other->LChild);
SET_RED(other);
R_Rotation(tree, other);
other = parent->RChild;
}
//No.4 xB=BLACK xB=RChild=RED
SET_COLOR(other, COLOR(parent));
SET_BLACK(parent);
SET_BLACK(other->RChild);
L_Rotation(tree, parent);
node = tree->root;
break;
}
}
else //node是其父节点的右孩子
{
other = parent->LChild;
if (IS_RED(other))
{
//No.1 xB=RED
SET_BLACK(other);
SET_RED(parent);
L_Rotation(tree, parent);
other = parent->LChild;
}
if ((!other->LChild) || IS_BLACK(other->LChild) &&
(!other->RChild) || IS_BLACK(other->RChild))
{
//No.2 xB=BLACK
SET_RED(other);
node = parent;
parent = PARENTNODE(node);
}
else
{
if (!other->LChild || IS_BLACK(other->LChild))
{
//No.3 xB=BLACK xB->RChild=RED, xB->LChild=BLACK;
SET_BLACK(other->RChild);
SET_RED(other);
L_Rotation(tree, other);
other = parent->LChild;
}
//No.4 xB=BLACK xB=LChild=RED
SET_COLOR(other, COLOR(parent));
SET_BLACK(parent);
SET_BLACK(other->LChild);
R_Rotation(tree, parent);
node = tree->root;
break;
}
}
}
if (node)
{
SET_BLACK(node);
}
}
//2.1 当做BST 去做删除
void deleteNode(LPRBTREE tree, LPNODE node)
{
LPNODE child, parent;
int color; //删除节点兄弟的颜色
//左右子树都存在
if ((node->LChild) != NULL && (node->RChild) != NULL)
{
LPNODE replace = node;
replace = replace->RChild; //调整树：从右子树中拿最左边
while (replace->LChild != NULL)
{
replace = replace->LChild;
}
//讨论删除节点是不是根节点
if (PARENTNODE(node))
{
if (PARENTNODE(node)->LChild == node)
{
PARENTNODE(node)->LChild = replace;
}
else
{
PARENTNODE(node)->RChild = replace;
}
}
else
{
tree->root = replace;
}
child = replace->RChild;
parent = PARENTNODE(replace);
color = COLOR(replace);
if (parent == node)
{
parent = replace;
}
else
{
if (child)
{
SET_PARENT(child, parent);
}
parent->LChild = child;
replace->RChild = node->RChild;
SET_PARENT(node->RChild, replace);
}
//调整替换节点父节点
replace->parentNode = node->parentNode;
replace->color = node->color;
replace->LChild = node->LChild;
//调整删除节点父节点
node->LChild->parentNode = replace;
if (color == BLACK)
{
//调整树：
deleteAdjustTree(tree, child, parent);
}
free(node);
return;
}
if (node->LChild != NULL)
{
child = node->LChild;
}
else
{
child = node->RChild;
}
parent = node->parentNode;
color = node->color;
if (parent)
{
if (parent->LChild == node)
{
parent->LChild = child;
}
else
{
parent->RChild = child;
}
}
else
{
tree->root = child;
}
if (color == BLACK)
{
//调整二叉树
deleteAdjustTree(tree, child, parent);
}
free(node);
}
LPNODE search(LPNODE x, int key)
{
if (x == NULL || x->key == key)
return x;
if (key < x->key)
{
return search(x->LChild, key);
}
else
{
return search(x->RChild, key);
}
}
void deleteTreeNode(LPRBTREE tree, int key)
{
LPNODE result = search(tree->root, key);
if (result != NULL)
deleteNode(tree, result);
}
int main()
{
int array[] = { 10,40,30,60,90,70,20,50,80 };
int arrayNum = 9;
LPRBTREE tree = createRBTree();
for (int i = 0; i < arrayNum; i++)
{
insertNode(tree, createNode(array[i]));
}
preOrder(tree->root);
printf("\n");
printf("删除:\n");
deleteTreeNode(tree, 10);
preOrder(tree->root);
printf("\n");
printf("删除:\n");
deleteTreeNode(tree, 80);
preOrder(tree->root);
printf("\n");
while (1);//防止闪屏
return 0;
}
好文推荐
发表评论