AVL树
一、概念
AVL树，也称平衡二叉搜索树，AVL树是一棵二叉搜索树，并且能通过一定的平衡处理机制保证二叉搜索树的平衡，使得查询效率更高。
特点：
- AVL树是一棵二叉搜索树。
- AVL树的左右子结点也是AVL树。
- 每个结点的左右子结点的高度之差的绝对值最多为1，即平衡因子的范围为[-1,1]。
平衡处理机制：
采用旋转进行平衡处理，一共有四种形式的旋转：右单旋、左单旋、左右双旋和右左双旋。
AVL树
二、数据结构
struct AVLTreeNode {
int value;
int height;
AVLTreeNode *left;
AVLTreeNode *right;
};
三、相关操作
- 插入
- 删除
- 查找
四、实现
#include<stdio.h>
#include<malloc.h>
struct AVLTreeNode {
int value;
int height;
AVLTreeNode *left;
AVLTreeNode *right;
};
AVLTreeNode* makeEmpty(AVLTreeNode* T) {
if (T != NULL) {
makeEmpty(T->left);
makeEmpty(T->right);
free(T);
}
return NULL;
}
int height(AVLTreeNode* P) { //计算AVL结点高度
if (P == NULL) {
return -1;
} else {
return P->height;
}
}
int max(int a, int b) { //获取最大值
return a > b ? a : b;
}
int absMinus(int a, int b) { //获取相减后的绝对值
int result;
if(a >= b) {
result = a - b;
} else {
result = b - a;
}
return result;
}
/* 左边的结点单旋（即向右旋转） */
AVLTreeNode* singleRotateWithLeft(AVLTreeNode* K2) {
AVLTreeNode* K1;
K1 = K2->left;
K2->left = K1->right;
K1->right = K2;
K2->height = max(height(K2->left), height(K2->right)) + 1;
K1->height = max(height(K1->left), K2->height) + 1;
return K1;
}
/* 右边的结点单旋（即向左旋转） */
AVLTreeNode* singleRotateWithRight(AVLTreeNode* K2) {
AVLTreeNode* K1;
K1 = K2->right;
K2->right = K1->left;
K1->left = K2;
K2->height = max(height(K2->left), height(K2->right)) + 1;
K1->height = max(K2->height, height(K1->right)) + 1;
return K1;
}
/* 左边的结点双旋（即先向左旋转再向右旋转） */
AVLTreeNode* doubleRotateWithLeft(AVLTreeNode* K3) {
K3->left = singleRotateWithRight(K3->left);
return singleRotateWithLeft(K3);
}
/* 右边的结点双旋（即先向右旋转再向左旋转） */
AVLTreeNode* doubleRotateWithRight(AVLTreeNode* K3) {
K3->right = singleRotateWithLeft(K3->right);
return singleRotateWithRight(K3);
}
AVLTreeNode* insertALV(int X, AVLTreeNode* T) { //递归插入，返回根结点
if (T == NULL) {
T = (AVLTreeNode*)malloc(sizeof(AVLTreeNode));
if (T == NULL) {
printf("out of memory\n");
} else {
T->value = X;
T->height = 0;
T->left = T->right = NULL;
}
} else if (X < T->value) { /* 左子树插入新结点 */
T->left = insertALV(X, T->left); //递归插入左子树，返回根结点
if (absMinus(height(T->left), height(T->right)) == 2)
if (X < T->left->value)
T = singleRotateWithLeft(T);
else
T = doubleRotateWithLeft(T);
} else if (X > T->value) { /* 右子树插入新结点 */
T->right = insertALV(X, T->right); //递归插入右子树，返回根结点
if (absMinus(height(T->left), height(T->right)) == 2)
if (X > T->right->value)
T = singleRotateWithRight(T);
else
T = doubleRotateWithRight(T);
} else {
printf("already exist\n");
}
T->height = max(height(T->left), height(T->right)) + 1; //更新根结点高度，左右子节点高度的最大值加1
return T; //返回根结点
}
AVLTreeNode* deleteAVL(int X, AVLTreeNode* T) { //递归删除，返回根结点
if(T == NULL) {
printf("find null\n");
} else if (X < T->value) {
T->left = deleteAVL(X, T->left); //递归删除左子树，返回根结点（当前结点的右子树结点高度比较大）
if(absMinus(height(T->left), height(T->right)) == 2) {
AVLTreeNode *p = T->right;
if(height(p->left) > height(p->right)) { //当前结点的右子树结点的左子树结点高度比较大，对右边的结点双旋
T = doubleRotateWithRight(T);
} else { //当前结点的右子树结点的右子树结点高度比较大，对右边的结点单旋
T = singleRotateWithRight(T);
}
}
} else if (X > T->value) { //递归删除右子树，返回根结点（当前结点的左子树结点高度比较大）
T->right = deleteAVL(X, T->right);
if(absMinus(height(T->left), height(T->right)) == 2) {
AVLTreeNode *p = T->left;
if(height(p->left) < height(p->right)) { //当前结点的左子树结点的右子树结点高度比较大，对左边的结点双旋
T = doubleRotateWithLeft(T);
} else { //当前结点的左子树结点的左子树结点高度比较大，对左边的结点单旋
T = singleRotateWithLeft(T);
}
}
} else {
if(T->left != NULL && T->right != NULL) { //待删除的结点有两个孩子结点
if(height(T->left) > height(T->right)) { //当前结点的左子树结点高度比较大
AVLTreeNode *p = T->left;
while(p->right != NULL) { //寻找当前结点的前驱结点，用于删除
p = p->right;
}
T->value = p->value;
T->left = deleteAVL(p->value, T->left);
} else { //当前结点的右子树结点高度比较大
AVLTreeNode *p = T->right;
while(p->left != NULL) { //寻找当前结点的后继结点，用于删除
p = p->left;
}
T->value = p->value;
T->right = deleteAVL(p->value, T->right);
}
} else if(T->left == NULL && T->right == NULL){ //待删除的结点无孩子结点
T = NULL;
} else if(T->right == NULL) { //待删除的结点只有左孩子结点
AVLTreeNode *p = T;
T = T->left;
free(p);
} else { //待删除的结点只有右孩子结点
AVLTreeNode *p = T;
T = T->right;
free(p);
}
}
if(T != NULL) {
T->height = max(height(T->left), height(T->right)) + 1; //更新根结点高度，左右子节点高度的最大值加1
}
return T;
}
/* 查找X元素所在的位置 */
AVLTreeNode* findAVL(int X, AVLTreeNode* T) {
if (T == NULL) {
return NULL;
} else if (X < T->value) {
return findAVL(X, T->left);
} else if (X > T->value) {
return findAVL(X, T->right);
} else {
return T;
}
}
/* 前序遍历二叉树 */
void preorderTravel(AVLTreeNode* T) {
if (T != NULL) {
printf("%d ", T->value);
preorderTravel(T->left);
preorderTravel(T->right);
}
}
/* 中序遍历二叉树 */
void inorderTravel(AVLTreeNode* T) {
if (T != NULL) {
inorderTravel(T->left);
printf("%d ", T->value);
inorderTravel(T->right);
}
}
/* 后序遍历二叉树 */
void postorderTravel(AVLTreeNode* T) {
if (T != NULL) {
postorderTravel(T->left);
postorderTravel(T->right);
printf("%d ", T->value);
}
}
AVLTreeNode* findMin(AVLTreeNode* T) { //查找最小值
if (T == NULL) {
return NULL;
} else if (T->left == NULL) {
return T;
} else {
return findMin(T->left);
}
}
AVLTreeNode* findMax(AVLTreeNode* T) { //查找最大值
if (T == NULL) {
return NULL;
} else if (T->right == NULL) {
return T;
} else {
return findMax(T->right);
}
}
/* 先序遍历打印二叉树信息 */
void printTree(AVLTreeNode* T, int value, int direction) {
if (T != NULL) {
if (direction == 0) {
printf("%2d is root\n", T->value);
} else {
printf("%2d is %2d's %6s child\n", T->value, value, direction == 1 ? "right" : "left");
}
printTree(T->left, T->value, -1);
printTree(T->right, T->value, 1);
}
}
void main() {
AVLTreeNode* T;
T = makeEmpty(NULL);
T = insertALV(5, T);
T = insertALV(4, T);
T = insertALV(7, T);
T = insertALV(2, T);
T = insertALV(6, T);
T = insertALV(3, T);
T = insertALV(8, T);
T = insertALV(1, T);
T = insertALV(9, T);
T = insertALV(11, T);
T = insertALV(10, T);
printf("Root: %d\n", T->value);
printf("树的详细信息: \n");
printTree(T, T->value, 0);
printf("前序遍历二叉树: ");
preorderTravel(T);
printf("\n");
printf("中序遍历二叉树: ");
inorderTravel(T);
printf("\n");
printf("后序遍历二叉树: ");
postorderTravel(T);
printf("\n");
printf("最大值: %d\n", findMax(T)->value);
printf("最小值: %d\n", findMin(T)->value);
AVLTreeNode *node = findAVL(11, T);
if(node == NULL) {
printf("find null\n");
} else {
printf("find %d\n", node->value);
}
T = deleteAVL(10, T);
T = deleteAVL(1, T);
T = deleteAVL(2, T);
T = deleteAVL(4, T);
printf("树的详细信息: \n");
printTree(T, T->value, 0);
}
红黑树
一、概念
红黑树（Red Black Tree）是一种自平衡二叉搜索树。
特点：
- 红黑树是一棵二叉搜索树。
- 每个结点是红色或黑色。
- 根结点是黑色。
- 叶子结点（NIL节点）是黑色。
- 红色结点的两个子结点都是黑色（如果子结点是红色，那么父结点一定是黑色）。
- 从任意结点到其每个叶子结点的路径包含相同数目的黑色结点。
平衡处理机制：
通过变色及旋转保持黑结点平衡。
红黑树
二、数据结构
struct RBTreeNode {
int value; //value
bool isRed; //结点颜色
RBTreeNode *parent; //父结点
RBTreeNode *left; //左子树
RBTreeNode *right; //右子树
};
三、相关操作
- 插入
- 查找
- 删除
四、实现
#include <stdio.h>
#include <malloc.h>
struct RBTreeNode {
int value; //value
bool isRed; //结点颜色
RBTreeNode *parent; //父结点
RBTreeNode *left; //左子树
RBTreeNode *right; //右子树
};
/*定义叶子结点*/
RBTreeNode *nil;
/*获取祖父结点*/
RBTreeNode* getAncestor(RBTreeNode* node) {
if (node->parent == nil) {
return NULL;
} else {
return node->parent->parent;
}
}
/*获取叔父结点*/
RBTreeNode* getUncle(RBTreeNode* node) {
RBTreeNode* ancestor = getAncestor(node);
if(ancestor == NULL || ancestor == nil) {
return NULL;
} else if (ancestor->left == node->parent) {
return ancestor->right;
} else {
return ancestor->left;
}
}
/*左旋*/
RBTreeNode* rotateLeft(RBTreeNode* root, RBTreeNode* node) {
if(node->right != nil) {
//当前结点的右结点
RBTreeNode* right = node->right;
node->right = right->left;
if (right->left != nil) {
right->left->parent = node;
}
right->parent = node->parent;
if (node->parent == nil) {
//node本来为根结点，此时变化为原来node的右结点
root = right;
} else {
if (node == node->parent->left) {
node->parent->left = right;
} else {
node->parent->right = right;
}
}
right->left = node;
node->parent = right;
}
return root;
}
/*右旋*/
RBTreeNode* rotateRight(RBTreeNode* root, RBTreeNode* node) {
if (node->left != nil) {
//当前结点的左结点
RBTreeNode* left = node->left;
node->left = left->right;
if (left->right != nil) {
left->right->parent = node;
}
left->parent = node->parent;
if (node->parent == nil) {
//node本来为根结点，此时变化为原来node的左结点
root = left;
} else {
if (node == node->parent->left) {
node->parent->left = left;
} else {
node->parent->right = left;
}
}
left->right = node;
node->parent = left;
}
return root;
}
/*插入修复*/
RBTreeNode* fixInsert(RBTreeNode* root, RBTreeNode* node) {
RBTreeNode* uncle;
while(node->parent->isRed == true) {
RBTreeNode* ancestor = getAncestor(node);
if(node->parent == ancestor->left) {
uncle = ancestor->right; //获取叔父结点
if (uncle->isRed == true) { //case 1 如果叔父结点为红色(此时祖父结点一定为黑),则把父结点和叔父结点着黑,祖父结点着红,node上移到祖父结点
uncle->isRed = false;
node->parent->isRed = false;
ancestor->isRed = true;
node = ancestor;
} else {
if (node == node->parent->right) { //case 3 如果叔父结点为黑色, node为右结点, 循环变量node变为node的父亲结点,左旋转变化后的node结点, 变为case2的情况
node = node->parent;
root = rotateLeft(root, node);
}
//case 2 叔父结点为黑色,且node为左结点,node的父结点着黑,node的祖父着红,然后旋转node的祖父结点
node->parent->isRed = false;
ancestor->isRed = true;
root = rotateRight(root, ancestor);
}
} else { //对称 修复同上
uncle = ancestor->left;
if (uncle->isRed == true) {
uncle->isRed = false;
node->parent->isRed = false;
ancestor->isRed = true;
node = ancestor;
} else {
if (node == node->parent->left) {
node = node->parent;
root = rotateRight(root, node);
}
node->parent->isRed = false;
ancestor->isRed = true;
root = rotateLeft(root, ancestor);
}
}
}
//case 1中可能会把node变为root，并将node设置成红色，故需要此步确保正确
root->isRed = false;
return root;
}
/*通过value插入一个结点*/
RBTreeNode* addNodeByValue(RBTreeNode* root, int value) {
if (root == NULL) {
root = (RBTreeNode*)malloc(sizeof(RBTreeNode));
//初始化nil结点
nil = (RBTreeNode*)malloc(sizeof(RBTreeNode));
nil->isRed = false;
//设置结点的指向
root->parent = nil;
root->left = nil;
root->right = nil;
//设置结点属性,value 和color
root->value = value;
root->isRed = false;
} else {
RBTreeNode* node = root;
/*插入结点的父结点*/
RBTreeNode* p = nil;
while (node != nil) {
p = node;
if(value > node->value) {
node = node->right;
} else if (value < node->value) {
node = node->left;
} else {
return root;
}
}
node = (RBTreeNode*)malloc(sizeof(RBTreeNode));
node->parent = p;
node->left = nil;
node->right = nil;
node->value = value;
node->isRed = true;
if (value < p->value) {
p->left = node;
} else {
p->right = node;
}
root = fixInsert(root, node);
}
return root;
}
/*查找实际要删除的结点*/
RBTreeNode* getRealRemoveNode(RBTreeNode* root, RBTreeNode* node) {
//查找右结点的最小结点
RBTreeNode* p = node->right;
while (p->left != nil) {
p = p->left;
}
return p;
}
/*查找某个结点*/
RBTreeNode* findNodeByValue(RBTreeNode* node, int value) {
if (node == nil) {
return NULL;
}
if (node->value < value) {
return findNodeByValue(node->right, value);
} else if (node->value > value) {
return findNodeByValue(node->left, value);
} else {
return node;
}
}
/*删除修复*/
RBTreeNode* fixRemove(RBTreeNode* root, RBTreeNode* node) {
while (node != root && node->isRed == false) { //循环结束条件为：node为根结点或者node结点为红色
if (node == node->parent->left) {
RBTreeNode* brother = node->parent->right; //brother为node的兄弟结点
if (brother->isRed == true) { //case 1 兄弟结点为红色（先让兄弟结点变黑色）
brother->isRed = false;
node->parent->isRed = true;
root = rotateLeft(root, node->parent);
brother = node->parent->right; //brother一定为黑色，因为node->parent为红色
}
//brother一定为黑色
if (brother == nil) { //兄弟结点为叶子结点，说明当前结点也为叶子结点，循环结束。
break;
} else if (brother->left->isRed == false && brother->right->isRed == false) { //case2 兄弟结点的两个子结点都为黑
brother->isRed = true;
node = node->parent;
} else if (brother->left->isRed == true) { //case3 兄弟结点的左子树为红色,右子树为黑色
brother->isRed = true;
brother->left->isRed = false;
root = rotateRight(root, brother);
brother = node->parent->right;
} else {
//case 4 兄弟结点的右子树为红色
brother->isRed = node->parent->isRed;
node->parent->isRed = false;
brother->right->isRed = false;
root = rotateLeft(root, node->parent);
node = root; //循环的出口
}
} else { //对称 修复同上
RBTreeNode* brother = node->parent->left;
if (brother->isRed == true) { //case 1
brother->isRed = false;
node->parent->isRed = true;
root = rotateRight(root, node->parent);
brother = node->parent->left;
}
if (brother == nil) {
break;
} else if (brother->left->isRed == false && brother->right->isRed == false) { //case 2
brother->isRed = true;
node = node->parent;
} else if (brother->right->isRed == true) { //case 3
brother->isRed = true;
brother->right->isRed = false;
root = rotateLeft(root, brother);
brother = node->parent->left;
} else { //case 4
brother->isRed = node->parent->isRed;
node->parent->isRed = false;
brother->left->isRed = false;
root = rotateRight(root, node->parent);
node = root; //循环的出口
}
}
}
//case 2中，当前结点的兄弟结点的两个子结点都为黑色，将兄弟结点设置为红色（即兄弟结点所在子树黑色结点数减1，与当前结点所在子树黑色结点数保持平衡），此时还需要将当前结点上升到父结点继续处理黑色结点数的平衡。
//当前结点上升到父结点后，如果该结点为红色，则结束循环，并将该结点设置为黑色即可（当前结点所在子树黑色结点数加1，与删除时减1保持了平衡）。
node->isRed = false;
return root;
}
RBTreeNode* removeNode(RBTreeNode* root, RBTreeNode* node) {
if (node == NULL) {
return root;
}
RBTreeNode* y; //实际要删除的结点
RBTreeNode* x; //实际要删除结点的子结点
if (node->left == nil || node->right == nil) {
y = node;
} else {
y = getRealRemoveNode(root, node);
}
if (y->left != nil) {
x = y->left;
} else {
x = y->right;
}
//注意：当结点y无左右子结点时，其子结点x为叶子结点nil
//删除结点y
//if(x != nil) {
//注意：该判断条件需要去掉。
//虽然叶子结点nil无父结点，但是对于删除操作，需要通过被删除结点（y）的子结点（x）,找到结点（y）被删除后，子结点（x）的兄弟结点。
//而子结点（x）的兄弟结点是通过子结点（x）的父结点查找的，因此即使子节点（x）为叶子结点（nil），也需要有父指针。
x->parent = y->parent;
//}
if (y->parent == nil) { //删除的是根结点
if(x == nil) { //根结点无子结点
free(root);
free(nil);
return NULL;
} else { //根结点有子结点
root = x;
}
} else { //删除的不是根结点
if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
}
if (y != node) {
//替换node和y的value
//由于本来要删除node，现在转换为删除node右结点的最小结点y，再把node的value换为y的value即可
node->value = y->value;
}
//如果删除的结点是黑色,违法了性质5,要进行删除修复
if (y->isRed == false) {
root = fixRemove(root, x);
}
free(y);
return root;
}
RBTreeNode* removeNodeByValue(RBTreeNode* root, int value) {
//root为指向根结点的指针
root = removeNode(root, findNodeByValue(root, value));
return root;
}
/*打印结点，先序遍历*/
void printRBTree(RBTreeNode* root) {
if (root != nil && root != NULL) {
printf("%d (%s)\n", root->value, root->isRed ? "红" : "黑");
printRBTree(root->left);
printRBTree(root->right);
}
}
void main() {
RBTreeNode* root = NULL;
root = addNodeByValue(root, 5);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 4);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 7);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 2);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 6);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 3);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 8);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 1);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 9);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 11);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 10);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 1);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 2);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 9);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 7);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 8);
printRBTree(root);
printf("\n");
/*
root = addNodeByValue(root, 5);
printRBTree(root);
printf("\n");
root = addNodeByValue(root, 6);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 5);
printRBTree(root);
printf("\n");
root = removeNodeByValue(root, 6);
printRBTree(root);
printf("\n");
*/
}
红黑树与AVL树的比较
- AVL树要求任意结点的左右子树的高度差的绝对值小于等于1，插入和删除结点时通过结点旋转保持树的平衡。而红黑树则要求黑色结点数保持平衡，插入和删除结点时通过结点旋转和变色保持树的平衡。
- AVL树的最大高度为1.44logn。而红黑树的最大高度为2log(n+1)，对于给定的黑色高度为N的红黑树，从根到叶子节点的最短路径长度为N-1，最长路径长度为2*(N-1)。
- 对于插入结点导致树失衡的情况，红黑树和AVL树都是最多2次结点旋转来实现复衡，旋转的量级是O(1)。
- 对于删除结点导致树失衡的情况，AVL树需要维护从被删除结点到根节点这条路径上所有结点的平衡，旋转的量级为O(logn)。而红黑树最多只需要旋转3次实现复衡，旋转的量级为O(1)。
- 在实际应用中，如果搜索的次数远远大于插入和删除的次数，那么选择AVL树。如果搜索、插入和删除的次数几乎差不多，那么选择红黑树。
网友评论