网站建设资讯

NEWS

网站建设资讯

AVL树之旋转-创新互联

1、AVL树

成都创新互联主要从事成都网站制作、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务汉南,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

 AVL树首先是一颗二叉搜索树,满足其所有性质,AVL树又叫做高度平衡的二叉搜索树;

 AVL: 动态搜索树;

 平衡因子bf: 右树高度 — 左树高度; bf的取值只能是1, 0, -1;

 左右子树都得符合平衡因子, 若不符, 的通过旋转来调整平衡因子;

2、四种旋转

 (1)、单旋转---->直线型

AVL树之旋转

 (2)、双旋转----->折线型

 要进行两次旋转的调整,判断折线,看哪边突出(就是三个结点中有一个突出的方向),就先向哪边旋转;

AVL树之旋转

 四种旋转,每次就只针对两个结点(要进行旋转的2个结点);然后将上面的分支挂到旋转后的L/R上即可。

3、画平衡树

 根据一组数字,画出其AVL树:16 3 7 11 9 26 18 14 15

 画AVL树,首先其实是一颗搜索二叉树; 按照其比左孩子大,比右孩子小画就行; 有了平衡因子,不满足时在旋转调整即可。

 画法如下:

AVL树之旋转

AVL树之旋转

AVL树之旋转

4、四种旋转的实现

 永远只考虑三层以内结点的旋转;

 C++实现其所有代码:

 (1)、右单旋

AVL树之旋转

 代码如下(代码中ptr代表的是要bf不为平衡处,指向要进行旋转的结点):

void RotateR(AVLNode *&ptr){
        AVLNode *subR = ptr;
        ptr = ptr->leftChild;  //通过引用直接修改指向1的指针(可能是上一个的左孩子/右孩子)
        subR->leftChild = ptr->rightChild;
        ptr->rightChild = subR;
        ptr->bf = subR->bf = 0;
    }

 (2)、左单旋

 左单旋与右单旋的代码是镜像的,并且想法是一致的; 所以代码如下:

void RotateL(AVLNode *&ptr){
    AVLNode *subL = ptr;
    ptr = subL->rightChild;  //同样是经过引用修改
    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    subL->bf = ptr->bf = 0;
}

 在进行单旋转时,因为是在插入,其自身的bf不用调整,初始化为0;修改的是根和另一个结点的bf;

 (3)、先左后右单旋

 在进行双旋转时,首先明确左/右孩子,根结点的最终情况, 在进行调整;并且在双旋转时每个结点的bf都得改变;

AVL树之旋转

 平衡因子在这不好考虑,有点复杂,具体分析如下:

 平衡因子的考虑关键在:ptr有左树/右树,对应上去则subL/sunR原先必有一个分支结点; ptr没有孩子结点,对应subR/subL原先也没有分支结点;

AVL树之旋转

AVL树之旋转

 代码如下:

void RotateLR(AVLNode *&ptr){
    AVLNode *subR = ptr;    //最终右孩子
    AVLNode *subL = ptr->leftChild; //最终左孩子
    ptr = subL->rightChild;  //最终根节点,因为引用,最终这个修改了指向根结点,完成了连接;

    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    if(ptr->bf <= 0){
        subL->bf = 0;  //此时的情况就是,自己ptr原先没有挂结点或者是左树挂上结点,而满足这种情况下,sunL原先必有左树,此时在挂上右树,所以为0;
    }else{
        subL->bf = -1;  //此时的情况是ptr有右孩子,而sunL有左孩子,满足这种情况,所以bf只能是-1;
    }

    subR->leftChild = ptr->rightChild;
    ptr->rightChild = subR;
    if(ptr->bf == -1){  //当结点ptr其只有左孩子时,
        subR->bf = 1;  //sunR必定有右孩子,所以此时为1
    }else{
        subR->bf = 0; //当ptr没有孩子结点或有一个右孩子时(此时subR必有右树),所以此时为0;
    }

    ptr->bf = 0;   //调整后根的bf永远是0;
}

 (4)、先右后左单旋

 与上一个双旋的代码是镜像的, 并且想法是一致的; 平衡因子的修改有点不一样,注意一下就行, 所以代码如下:

void RotateRL(AVLNode *&ptr){
    AVLNode *subL = ptr;
    AVLNode *subR = ptr->rightChild;
    ptr = subR->leftChild;

    subR->leftChild = ptr->rightChild;
    ptr->rightChild = subR;
    if(ptr->bf >=0){
        subR->bf = 0;
    }else{
        subR->bf = 1;
    }

    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    if(ptr->bf == 1){
        subL->bf = -1;
    }else{
        subL->bf = 0;
    }

    ptr->bf = 0;
}

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


新闻标题:AVL树之旋转-创新互联
网页URL:http://cdweb.net/article/posgp.html