集成学习集成学习09-25 10:48

二叉树总结(四)平衡二叉树

平衡二叉树概念

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。它是最先发明的自平衡二叉查找树,也被称为高度平衡树。相比于"二叉查找树",它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。如果在AVL树中插入或删除节点后,使得高度之差大于1。此时,AVL树的平衡状态就被破坏,它就不再是一棵二叉树;为了让它重新维持在一个平衡状态,就需要对其进行旋转处理。

平衡二叉树结构:

typedef int Type;

typedef struct AVLTreeNode{
    Type key;
    int height;                     //当前节点的高度
    struct AVLTreeNode *left;    // 左孩子
    struct AVLTreeNode *right;    // 右孩子
}Node, *AVLTree;

 

平衡二叉树修复方法

 当插入一个元素使平衡二叉树不平衡时,可能出现以下的四种情况:

  1. LL:称为"左左"。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。

例如,在上面LL情况中,由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

  1. LR:称为"左右"。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。

 例如,在上面LR情况中,由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

  1. RL:称为"右左"。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。

例如,在上面RL情况中,由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

  1. RR:称为"右右"。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。

例如,在上面RR情况中,由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

下面根据上面的四种情况来具体看修复的办法。

LL旋转

当平衡二叉树失去平衡,显示出上面LL的情况时,可以用下面的一次调整使其恢复平衡。

从上图看出,只需要将高度较大的左子树的根节点作为其父节点,然后,将其父节点作为右子树的根节点;这时,原来左子树的右子树需要移动到现在的右子树下,作为其左子树。

/*
 *p 为需要调整的子树树根,即图中的k1
 *root 为调整后的树根,即p的左孩子
**/
Node *leftLeftRotation(AVLTree p)
{
    AVLTree root = p->left;//调整子树
    p->left = root->right;
    root->right = p;

    p->height = 0;//重新计算高度
    if (p->left)p->height = p->left->height + 1;
    if (p->right)p->height = max(p->height, p->right->height + 1);
    root->height = 0;
    if (root->left)root->height = root->left->height + 1;
    if (root->right)root->height = max(root->height, root->right->height + 1);

    return root;
}

RR旋转

当平衡二叉树失去平衡,显示出上面RR的情况时,可以用下面的一次调整使其恢复平衡。

从上图看出,只需要将高度较大的右子树的根节点作为其父节点,然后,将其父节点作为左子树的根节点;这时,原来右子树的左子树需要移动到现在的左子树下,作为其右子树。

/*
*p 为需要调整的子树树根,即图中的k1
*root 为调整后的树根,即p的右孩子
**/
Node *rightRightRotation(AVLTree p)
{
    AVLTree root = p->right;//调整子树
    p->right = root->left;
    root->left = p;

    p->height = 0;//重新计算高度
    if (p->left)p->height = p->left->height + 1;
    if (p->right)p->height = max(p->height, p->right->height + 1);
    root->height = 0;
    if (root->left)root->height = root->left->height + 1;
    if (root->right)root->height = max(root->height, root->right->height + 1);

    return root;
}

LR旋转

当平衡二叉树失去平衡,显示出上面LR的情况时,可以用下面的两次调整使其恢复平衡。

如上图,先将k1为树根的子树向左旋转,即和前面的RR调整的方向类似,然后在将以k3为树根的子树向右旋转。

/*
 *先按照RR的方式调整p->left;然后按照LL的方式调整p
**/
Node *leftRightRotation(AVLTree p){
    p->left = rightRightRotation(p->left);
    return leftLeftRotation(p);
}

RL旋转

当平衡二叉树失去平衡,显示出上面RL的情况时,可以用下面的两次调整使其恢复平衡。

如上图,先将k3为树根的子树向右旋转,即和前面的LL调整的方向类似,然后在将以k1为树根的子树向左旋转。

/*
*先按照LL的方式调整p->right;然后按照RR的方式调整p
**/
Node *rightLeftRotation(AVLTree p){
    p->right = leftLeftRotation(p->right);
    return rightRightRotation(p);
}

 

程序之家二维码

小额赞赏

000
评论