即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

平衡搜索树之AVLTree

编程语言 blight_888 10℃ 0评论
本文目录
[隐藏]

1.什么是AVL树?

AVLTree又称为高度平衡的二叉搜索树,是1962年由俄罗斯的数学家G.M.Adelson-Velskii 和 E.M.Landis提出来的。他能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。

AVL树的性质


1.左子树和右子树的平均高度差的绝对值不超过1;


2.树中的每个左子树和右子树都是AVL树;


3.每个节点都有一个平衡因子(balance factor–bf),任一节点的平衡因子是-1, 1, 0, (每个节点的平衡因子等于右子树的高度减去左子树的高度)

AVL树的效率


一个AVL树有N个节点,其高度可以保持在log 2N, 插入/删除/查找的时间复杂度也是log2N.(这个也是我们之所以会有AVL的原因,搜索树在特定情况下的效率并不尽如人意)。

下边我们以图形和代码来看看AVL树到底是怎么实现和运用的。


(对于AVL树我们只关注增/删/查/改)以插入为例。


AVL树之所以能保持平衡的原因是他在插入和删除的时候如果破坏了本身的平衡性的时候会在不改变搜索树性质的前提下进行一定的旋转。总结起来共有四种旋转方式:

1.左单旋


这里写图片描述

2.右单旋


这里写图片描述

3.左右双旋(先左后右旋转)


这里写图片描述

4.右左双旋(先右后左双旋)


这里写图片描述

接下来我们可以写代码了,对于AVL属的代码画图很重要。

#pragma once
#include <iostream>
using namespace std;

template<class K, class V>

struct AVLTreeNode
{
    K _key;
    V _value;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;

    int _bf;//平衡因子

    AVLTreeNode(const K& key, const V& value)
        : _key(key)
        , _value(value)
        , _left(NULL)
        , _right(NULL)
        , _bf(0)
    {}
};

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    AVLTree()
        :_root(NULL)
    {}

    bool Insert(const K& key, const V& value)
    {
        if (_root == NULL)
        {
            _root = new Node(key, value);
            return true;
        }

        Node* cur = _root;
        Node* parent = NULL;
        while (cur)
        {
            if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key, value);
        if (parent->_key < key)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

        //平衡调节
        while (parent)
        {
                //由于平衡因子 = | 右子树高度 - 左子树高度|
                //所以在父节点的左树插入就让父节点的平衡因+1
            //在右树插入就让父节点的平衡因子-1
            if (cur == parent->_left)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }
            if (0 == parent->_bf)//平衡因子为0,则不用动  
            {
                break;
            }
            else if (parent->_bf == -1 || parent->_bf == 1)
            {
                cur = parent;
                parent {


                    if (cur->_bf == 1)
                    {
                        RotateL(parent);   //图1详解
                    }
                    else
                    {
                        RotateRL(parent); //图2详解
                    }
                }
                else
                {
                    if (cur->_bf == -1)
                    {
                else
                    {
                        RotateRL(parent);
                    }
                }
                else
                {
                    if (cur->_bf == -1)
                    {
                        RotateR(parent)
                    }
                    else
                    {
                        RotateLR(parent)
                    }
                }
                break;
            }
        }
        return true;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }


        Node* pparent = parent->_parent; 
        subR->_left = parent;
        parent->_parent = subR;
        if (pparent == NULL)
        {
            _root = subR;
        }
        else
        {
            if (pparent->_left == parent)
            {
                pparent->_left = subR;
            }
            else
            {
                pparent->_right = subR;
            }
        }
        subR->_parent = pparent;
        subR->_bf = parent->_bf = 0;
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }

        Node* pparent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (pparent == NULL)
        {
            _root = subL;
        }
        else
        {
            if (pparent->_left == parent)
            {
                pparent->_left = subL;
            }
            else
            {
                pparent->_right = subL;
            }
        }
        subL->_parent = pparent;
        subL->_bf = parent->_bf = 0;
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subL->_bf;

        RotateL(parent->_left);
        RotateLR(parent);

        if (1 == bf)
        {
             //图3详解
            parent->_bf = 0;
            subL->_bf = -1;
        }
        else if (-1 == bf)
        {
            parent->_bf = -1;
            subL->_bf = 0;
        }
        else
        {
            parent->_bf = subL->_bf = 0;
        }
        subLR->_bf = 0;
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        if (1 == bf)
        {
            parent->_bf = -1;
            subR->_bf = 0;
        }
        else if (-1 == bf)
        {
            parent->_bf = 0;
            subR->_bf = 1;
        }
        else
        {
            parent->_bf = subR->_bf = 0;
        }
        subRL->_bf = 0;
    }

    void InOrder()
    {
        _InOrder(_root);
    }

    bool IsBalance()
    {
        int depth = 0;
        return _IsBalance(_root, depth);
    }

    int Depth(Node* root)
    {
        if (root == NULL)
            return 0;
        int left = Depth(root->_left);
        int right = Depth(root->_right);

        return left > right ? left + 1: right + 1;
    }
private:
    void _InOrder(Node* root)
    {
        if (root == NULL)
            return;

        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }

    //bool _IsBalance(Node* root)  
    //{
    //  if (root == NULL)
    //  {
    //      return true;
    //  }
    //  int left = _IsBalance(root->_left);
    //  int right = _IsBalance(root->_right);

    //  return abs(left - right) < 2
    //      && _IsBalance(root->_left)
    //      && _IsBalance(root->_right)
    //}

    bool _IsBalance(Node* root, int& depth)
    {
        if (root == NULL)
        {
            depth = 0;
            return true;
        }
        int leftDepth, rightDepth;
        if (_IsBalance(root->_left, leftDepth) == false)
            return false;
        if (_IsBalance(root->_right, rightDepth) == false)
            return false;
        if ((leftDepth - rightDepth) != root->_bf)
        {
            cout << "异常" << root->_key << endl;
        }

        depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
        return abs(leftDepth - rightDepth) < 2;
    }

protected:
    Node* _root;
};

void TestAVLTree()
{
`
    AVLTree tree;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (size_t i = 0; i < sizeof(int) / sizeof(a[0]); i++)
    {
        tree.Insert(a[i], i);
        //cout << a[i] << "IsBalance?" << tree.IsBalance() << endl;
    }
    tree.InOrder();
    cout << "IsBalance?" << tree.IsBalance() << endl;
}

图1

这里写图片描述

图2

这里写图片描述

图3

这里写图片描述

2.总结:

AVL树是在搜索二叉树的基础上为了降低时间复杂度而设立了平衡因子而实现的,好处就是大大提高了效率O(lg N)在数据很大的情况下优势很明显,但也有一个缺点,就是每个节点的平衡因子维护起来很复杂,出错的话很不好找(建议实现代码前先画图),所以后边就有了更高效和更实用的红黑树,我们后边再了解。

转载请注明:CodingBlog » 平衡搜索树之AVLTree

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情