• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

数据结构与算法 :AVL平衡二叉树C语言实现

互联网 diligentman 2周前 (11-19) 8次浏览

C语言实现AVL平衡二叉树

1结构体
//这里定义一个取较大值的MAX宏
#define MAX(a,b) ((a)>(b)?(a):(b))

typedef struct AVLTreeNode {
    int data; //数据域
    int height; //数据域
    struct AVLTreeNode *left; //左子结点
    struct AVLTreeNode *right; //右子结点
} AVLTreeNode;
2.1右单旋
/**
 * 右单旋
 *          8                  4
 *       4     12           2     8
 *    2    6         =>  1      6   12
 * 1                                
 */
AVLTreeNode *right_rotation(AVLTreeNode *root)
{
    struct AVLTreeNode *new_root;
    new_root         = root->left;
    root->left       = new_root->right;
    new_root->right  = root;
    //旋转完重新计算高度
    root->height     = MAX(Height(root->left) + 1, Height(root->right));
    new_root->height = MAX(Height(new_root->left) + 1, Height(new_root->right));
    return new_root;
}
2.2左单旋
/**
 * 左单旋
 *          8                         12
 *       4     12                  8     50  
 *           9    50      =>    4    9      70
 *                   70                      
 */
AVLTreeNode *left_rotation(AVLTreeNode *root)
{
    struct AVLTreeNode *new_root;
    new_root         = root->right;
    root->right      = new_root->left;
    new_root->left   = root;
    //旋转完重新计算高度
    root->height     = MAX(Height(root->right) + 1, Height(root->left));
    new_root->height = MAX(Height(new_root->right) + 1, Height(new_root->left));
    return new_root;
}
2.3左右旋
/**
 * 左右旋 先对root->left左旋 再对root右旋
 *           8                         8                     6
 *       4      12                  6     12             4       8
 *    2     6            =>      4              =>    2     5       12
 *        5                   2    5          
 */
AVLTreeNode *left_right_rotation(AVLTreeNode *root){
    root->left = left_rotation(root->left);
    return right_rotation(root);
}
2.3右左旋
/**
 * 右左旋 先对root->right右旋 再对root左旋
 *           8                         8                       10
 *       4      12                  4     10                8     12
 *           10    14      =>           9    12       =>  4   9       14
 *         9                                    14
 */
AVLTreeNode *right_left_rotation(AVLTreeNode *root){
    root->right = right_rotation(root->right);
    return left_rotation(root);
}
3 自平衡
AVLTreeNode *rebalance(AVLTreeNode *root, int data)
{
    if (Height(root->right) - Height(root->left) == 2)
    {
        if (data > root->right->data)//左单旋的情况
        {
            printf("left_rotation n");
            root = left_rotation(root);
        }else{
            printf("right_left_rotation n");//右左旋的情况
            root = right_left_rotation(root);
        }
    }
    if (Height(root->left) - Height(root->right) == 2)
    {
        if (data < root->left->data)//右单旋的情况
        {
            printf("right_rotation n");
            root = right_rotation(root);
            }else{
            printf("left_right_rotation n");//左右旋的情况
            root = left_right_rotation(root);
        }
    }
    return root;
}
4 插入
AVLTreeNode *insert(AVLTreeNode *root, int data)
{
    if (NULL == root)
    {
        struct AVLTreeNode *node;
        node = (struct AVLTreeNode *)malloc(sizeof(struct AVLTreeNode));
        if (node == NULL)
        {
            printf("malloc error n");
            return NULL;
        }
        node->data  = data;
        node->right = NULL;
        node->left  = NULL;
        return node;
    }
    
    if (data >= root->data)
    {
        root->right  = insert(root->right, data);
        root->height = MAX(Height(root->left), Height(root->right) + 1);//相比于二叉搜索树多了高度判断
    }else{
        root->left   = insert(root->left, data);
        root->height = MAX(Height(root->left) + 1, Height(root->right));
    }
    root = rebalance(root, data);
    return root;
}
5.1 查找最大/小节点
AVLTreeNode *FindMin(AVLTreeNode *root)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (root->left == NULL)
    {
        return root;
    }else{
        return FindMin(root->left);
    }
}
AVLTreeNode *FindMax(AVLTreeNode *root)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (root->right == NULL)
    {
        return root;
    }else{
        return FindMax(root->right);
    }
}
5.2删除
AVLTreeNode *Delete(AVLTreeNode *root, int target)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (target > root->data)
    {
        root->right = Delete(root->right, target);
        if (Height(root->left) - Height(root->right) == 2)
        {
            AVLTreeNode *l =  root->left;
            if (Height(l->right) > Height(l->left))
                root = left_right_rotation(root);
            else
                root = left_rotation(root);
        }
    }else if(target < root->data){
        root->left  = Delete(root->left, target);
        if (Height(root->right) - Height(root->left) == 2)
        {
            AVLTreeNode *r =  root->right;
            if (Height(r->left) > Height(r->right))
                root = left_right_rotation(root);
            else
                root = right_rotation(root);
        }
    }else{
        //相等的情况
        if (root->left && root->right)
        {
            if (Height(root->left) > Height(root->right))
            {
                //左子树比右子树高
                AVLTreeNode *max = FindMax(root->left);
                root->data = max->data;
                root->left = Delete(root->left, max->data);
            }else{
                AVLTreeNode *min = FindMin(root->right);
                root->data = min->data;
                root->right = Delete(root->right, min->data);
            }
        }else{
            struct AVLTreeNode *tmp;
            tmp = root;
            if (root->left == NULL)
            {
                root = root->right;
            }else if(root->right == NULL){
                root = root->left;
            }else{
                root = NULL;//删除自身
            }
        }
    }
    return root;
}

测试:

int main()
{ 
    struct AVLTreeNode *node;
    node = NULL;
    node = insert(node, 8);
    node = insert(node, 4);
    node = insert(node, 12);
    node = insert(node, 10);
    node = insert(node, 14);
    node = insert(node, 9);
    printf("***前序***:  n");
    preOrderTraverse(node);
    node = Delete(node, 10);
    printf("***前序***:  n");
    preOrderTraverse(node);
}

数据结构与算法 :AVL平衡二叉树C语言实现


喜欢 (0)