平衡二叉树

左手的ㄟ右手 2022-07-21 00:17 27阅读 0赞

# AVL树的简介 #

AVL树（即平衡二叉树）是自平衡的二分查找树。在AVL树中任何节点的两个子树的高度差值为一。因此，**它也是一个棵在二分查找树（BST）且为二分查找树的改进版**。

注：AVL树的“AVL”来自于两位前苏联的发明者Georgy Adelson-Velsky 和 Evgenii Landis。

## 特点 ##

1.  AVL树以一棵**二分查找树（BST）**
2.  自平衡：每个节点的左右子树高度相差绝对值不超过1

# AVL树的实现 #

// avl树节点的定义
    typedef struct AvlNode 
    {
            int key;
            struct AvlNode *left;
            struct AvlNode *right;
            int height;
    
    } AvlNode, *PAvlNode, *AvlTree; 
    
    // avl节点生成方法
    PAvlNode _makeAvlNode(int key)
    {
            PAvlNode pAvlNode = (PAvlNode)malloc(sizeof(AvlNode));
            pAvlNode->key = key;
            pAvlNode->left = pAvlNode->right = NULL;
            pAvlNode->height = 0;
    
            return pAvlNode;
    }
    // avl树高度大小比较
    int Max(int h1, int h2)
    {
            return h1 > h2 ? h1 : h2;
    }

// avl树高度
    int Height(AvlTree tree) 
    {
            if (tree) {
                    return tree->height;
            }
    
            return 0;
    }
    
    // LL旋转
    AvlTree SingleRotateWithLeft(AvlTree tree)
    {
            AvlTree t = tree->left;
            tree->left = t->right;
            t->right = tree;
    
            // 旋转之后，重新设置节点高度，即左子树或右子树高度最大值加1（本节点的高度1）
            tree->height = Max(Height(tree->left), Height(tree->right)) + 1;
            t->height = Max(Height(t->left), Height(t->right)) + 1;
    
            return t;
    }
    // RR旋转
    AvlTree SingleRotateWithRight(AvlTree tree)
    {
            AvlTree t = tree->right;
            tree->right = t->left;
            t->left = tree;
    
            tree->height = Max(Height(tree->left), Height(tree->right)) + 1;
            t->height = Max(Height(t->left), Height(t->right)) + 1;
    
            return t;
    }
    // RL旋转
    AvlTree DoubleRotateLeft(AvlTree tree)
    {
            tree->left = SingleRotateWithRight(tree->left);
    
            return SingleRotateWithLeft(tree);
    }
    // LR旋转
    AvlTree DoubleRotateRight(AvlTree tree)
    {
            tree->right = SingleRotateWithLeft(tree->right);
    
            return SingleRotateWithRight(tree);
    }
    
    // avl树节点插入方法
    /*
        [参数]
        tree : avl树根节点指针
        key  : 插入avl树的关键字
    
        [返回值]
        返回关键字插入位置的指针         
    */
    AvlTree Insert(AvlTree tree, int key)
    {
            if (tree == NULL) {
                    tree = _makeAvlNode(key);
                    return tree;
            } else {
                    if (key < tree->key) {
    
                            tree->left = Insert(tree->left, key);
    
                            if (Height(tree->left)
                                    - Height(tree->right) == 2) {
    
                                    if (key < tree->left->key)
                                            tree = SingleRotateWithLeft(tree);
                                    else
                                            tree = DoubleRotateLeft(tree);           
                            }
                    } else if (key > tree->key) {
                            tree->right = Insert(tree->right, key);
    
                            if (Height(tree->right)
                                    - Height(tree->left) == 2) {
    
                                    if (key > tree->right->key)
                                           tree = SingleRotateWithRight(tree);
                                    else
                                            tree = DoubleRotateRight(tree);
                            }
                    }
    
            }
    
            tree->height = Max(Height(tree->left), Height(tree->right)) + 1;
    
            return tree;
    }
    
    // 单节点旋转
    // 需要判断节点的左右子树是否平衡，不平衡进行旋转操作
    AvlTree Rotate(AvlTree tree)
    {
            if (Height(tree->left) - Height(tree->right) == 2) {
                    if (Height(tree->left->left)
                            >= Height(tree->left->right)) {
                            tree = SingleRotateWithLeft(tree);
                    } else {
                            tree = DoubleRotateLeft(tree);
                    }
            }
    
            if (Height(tree->right) - Height(tree->left) == 2) {
                    if (Height(tree->right->right)
                            >= Height(tree->right->left)) {
                            tree = SingleRotateWithRight(tree);
                    } else {
                            tree = DoubleRotateRight(tree);
                    }
            }
    
            return tree;
    }
    
    // avl树节点删除
    AvlTree Delete(AvlTree tree, int key)
    {
            if (tree == NULL)
                    return NULL;
    
            if (tree->key == key) { // 被删除节点的左右子树调整
                    if (tree->right == NULL) {
                            AvlTree t = tree;
                            tree = tree->left;
                            free(t);
                    } else {
                            AvlTree t = tree->right;
                            while (t->left)
                                    t = t->left;
    
                            tree->key = t->key;
                            tree->right = Delete(tree->right, tree->key);
                            tree->height = Max(Height(tree->left), Height(tree->right)) + 1;
                    }
    
                    return tree;
            } else if (key > tree->key) {
                    tree->right = Delete(tree->right, key);
            } else {
                    tree->left = Delete(tree->left, key);
            }
    
            // 删除节点后，重新设置其父节点的高度
            tree->height = Max(Height(tree->left), Height(tree->right)) + 1;
            // 删除节点后，逐级调整被删除节点的父节点
            if (tree->left)
                    tree->left = Rotate(tree->left);
            if (tree->right)
                    tree->right = Rotate(tree->right);
            if (tree)
                    tree = Rotate(tree);
    
            return tree;
    }
    
    // avl树遍历方法
    void Traversal(AvlTree tree)
    {
            if (tree) {
                    if (tree->left)
                            Traversal(tree->left);
    
                    printf(" %d", tree->key);
    
                    if (tree->right)
                            Traversal(tree->right);
            }
    
            return;
    }

// avl树测试方法
    int main()
    {
            int a[] = {
       8, 2, 10, 3, 7, 1, 6};
            size_t count = sizeof(a)/sizeof(a[0]);
            AvlTree tree = NULL;
            for (size_t i = 0; i < count; i++) {
                    tree = Insert(tree, a[i]);
            }
    
            Traversal(tree);
            printf("\n");
    
            Delete(tree, 7);
            Traversal(tree);
            printf("\n");           
    
            return 0;
    }

# AVL树的性能 #

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

# BST、AVL和RBTree #

1.  二分查找树（BST）比较简单，但是很容易产生不平衡的问题而丧失了二分查找树的优势。
2.  AVL树规定了左右孩子树的高度差超过1则为不平衡，为了维持平衡，在插入和删除子节点后，必须进行相应的旋转。
3.  还有一种著名的红黑树，红黑树放宽了平衡的要求，从而减少了操作的次数。

由此AVL和RBTree都是BST的改进版。

# 参考 #

1 [AVL树的旋转操作 图解 最详细][AVL_ _]  
2 [AVL树][AVL]  
3 [平衡二叉树(AVL)实现(3)-删除][AVL_3_-]  
4 [数据结构 – 二叉树(BST, AVLTree, RBTree, SplayTree)][_ _BST_ AVLTree_ RBTree_ SplayTree]

[AVL_ _]: http://blog.csdn.net/collonn/article/details/20128205
[AVL]: http://blog.csdn.net/xiaofan086/article/details/8294382
[AVL_3_-]: http://www.cnblogs.com/Clingingboy/archive/2010/10/09/1846865.html
[_ _BST_ AVLTree_ RBTree_ SplayTree]: http://philoscience.iteye.com/blog/1346424