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

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