二叉树-平衡二叉搜索树

AVL树又称为平衡二叉搜索树平衡二叉排序树，AVL树是二叉搜索树，可以通过一定的平衡处理机制确保二叉搜索树的平衡平衡二叉排序树，使查询效率更高.

功能:

余额处理机制:

旋转用于余额处理. 旋转有四种类型: 向右单旋转，向左单旋转，向左和向右双旋转以及向左和向右双旋转.

AVL树

struct AVLTreeNode {
    int value;
    int height;
    AVLTreeNode *left;
    AVLTreeNode *right;
};

AVL树相关操作

#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);
}

红黑树是一种自平衡的二进制搜索树.

功能:

余额处理机制:

通过更改颜色并旋转以保持黑色节点的平衡.

红黑树

struct RBTreeNode {
    int value;           //value
    bool isRed;          //结点颜色
    RBTreeNode *parent;  //父结点
    RBTreeNode *left;    //左子树
    RBTreeNode *right;   //右子树
};

与红黑树相关的操作-1

与红黑树相关的操作-2

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-269097-1.html