首页 > 代码库 > AVL树

AVL树

2024-11-03 21:14:39   204人阅读

一. 介绍

在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

AVL树的节点定义:

struct AVLNode{    int data;    Node* left;    Node* right;    char height;    Node(int _data=http://www.mamicode.com/0):data(_data),left(0),right(0){}};

这里用char来存储高度, 而不是用bool存储高度差是很合理的. 一方面, 用bool存储高度差并不能节省空间, 因为现代计算机的最小寻址单元是1byte, 小于1byte的变量会被对齐到1byte. 另一方面, 由于avl树是自平衡的, 因此当高度达到char的最大值127时, avl树的节点数已经大于2^127-1个, 这已经很庞大了, 在一般需求中无需用更大的数据类型来存储高度.

二. AVL的核心: 旋转操作

AVL树的旋转一共有四种情形，注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点(B)展开的。

1. LL型失衡

    B为左孩子, 且B的左孩子高于右孩子

技术分享

2. RR型失衡

      B为右孩子, 且B的右孩子高于左孩子

技术分享

3. LR型失衡

      B为左孩子, 且B的右孩子高于左孩子。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平衡，这时还需要再向右旋转一次。

技术分享

4. RL型失衡

      B为右孩子, 且B的左孩子高于右孩子。同样，这时需要旋转两次，旋转方向刚好同LR型相反。

技术分享

 

void AVLTree::rotateLL(AVLNode*& a){    AVLNode *b = a->left;    a->left = b->right;    b->right = a;    a->height = max(getHeight(a->left), getHeight(a->right)) + 1;    b->height = max(getHeight(a->left), getHeight(a->right)) + 1;    a = b;}void AVLTree::rotateRR(AVLNode*& a){    AVLNode *b = a->right;    a->right = b->left;    b->left = a;    a->height = max(getHeight(a->left), getHeight(a->right)) + 1;    b->height = max(getHeight(a->left), getHeight(a->right)) + 1;    a = b;}void AVLTree::rotateLR(AVLNode*& a){    rotateRR(a->left);    rotateLL(a);}void AVLTree::rotateRL(AVLNode*& a){    rotateLL(a->right);    rotateRR(a);}AVLNode* AVLTree::search(DataType x, AVLNode*& father){    AVLNode *p = root;    father = NULL;    while (p != NULL&&x != p->data)    {        father = p;        if (x > p->data)            p = p->right;        else            p = p->left;    }    return p;}char AVLTree::getHeight(AVLNode *x){    if (!x)        return -1;    //return max(getHeight(x->left), getHeight(x->right)) + 1;    char l = (x->left) ? x->left->height : -1;    char r = (x->right) ? x->right->height : -1;    return max(l, r) + 1;}

三. AVL的插入

AVL的插入是二叉搜索树的插入的扩展: 在回朔阶段添加了检查平衡性的步骤. 在实际执行时, 首先按照插入二叉搜索树的方法(自顶向下)将新节点插入到空指针位置, 从而形成一个新的叶子节点. 然后在回朔阶段, 自底向上地检查平衡性. 当高度差为2时, 通过旋转操作来调整平衡.

每次检查平衡性之前, 一个必要的步骤就是计算当前结点的高度. 否则就无法检查平衡性.旋转完成之后仍然要计算节点高度, 以保证下一层回朔的正确性

void AVLTree::insertAVL(DataType x){    insertAVL(x, root);}void AVLTree::insertAVL(DataType x, AVLNode*& node){    if (!node)    {        node = new AVLNode(x);        return;    }    if (x < node->data)    {        insertAVL(x, node->left);        node->height = max(getHeight(node->left), getHeight(node->right)) + 1;        // 如果x比当前结点小, 那么只可能在该节点导致LL或LR失衡        if (getHeight(node->left) - getHeight(node->right) == 2)        {            if (x < node->left->data) //x插入到左孩子的左侧, 导致LL失衡                rotateLL(node);             else if (x > node->left->data) //x插入到左孩子的右侧, 导致LR失衡                rotateLR(node);        }    }    else if (x > node->data)    {        insertAVL(x, node->right);        node->height = max(getHeight(node->left), getHeight(node->right)) + 1;        // 类比上面的分析        if (getHeight(node->left) - getHeight(node->right) == -2)        {            if (x > node->right->data)                rotateRR(node);            else if (x < node->right->data)                rotateRL(node);        }    }    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;}

AVL树


联系
我们