📌算法Go语言描述📌treestruct📌3-avl-rotate.txt
对失衡情形穷举细分,得出局部旋转parent和child结点平衡因子变化。
通过赋值代替频繁计算,从而获得更稳定的性能表现。

-------------------- 删除p.right导致左左失衡; R(-2,0)=>(-1,1)

        p(-2)                      c(1)
       /                           / \\
     c(0)            ==>          cl  p(-1)
     / \          rotateR(p)          //
    cl cr                            cr

-------------------- 删除p.right或插入c.left导致左左失衡; R(-2,-1)=>(0,0)

        p(-2)
       /                            c(0)
     c(-1)           ==>           / \\
     /            rotateR(p)      cl  p(0)
    cl

-------------------- 删除p.right或插入c.right导致左右失衡; L(1,0)=>(0,-1);

      p(-2)                            p(-2)
     /                                /
    c(1)             ==>            cr(-1)           ==>
     \            rotateL(c)        //            rotateR(p)
      cr(0)                       c(0)

-------------------- 删除pr.child或插入cr.right导致左右失衡; L(1,1)=>(-1,-1);

        p                                p(-2)
       / \                              / \
     c(1) pr         ==>             cr(-1)pr        ==>
     / \          rotateL(c)          // \        rotateR(p)
    cl cr(1)                       c(-1)  x
         \                         /
          x                       cl

-------------------- 删除pr.child或插入cr.left导致左右失衡; L(1,-1)=>(0,-2); R(-2,-2)=>(1,0)

        p                                p(-2)
       / \                              / \                           cr(0)
     c(1) pr         ==>             cr(-2)pr        ==>             / \\
     / \          rotateL(c)          //          rotateR(p)        c   p(1)
    cl cr(-1)                       c(0)                           / \   \
        /                          / \\                           cl  x   pr
       x                          cl  x


-------------------- 删除p.left导致右右失衡; L(2,0)=>(1,-1)

    p(2)                             c(-1)
     \                              // \
      c(0)           ==>          p(1) cr
      / \         rotateL(p)       \\
     cl  cr                         cl

-------------------- 删除p.left或插入c.right导致右右失衡; L(2,1)=>(0,0)

    p(2)
     \                               c(0)
      c(1)           ==>            // \
       \          rotateL(p)      P(0) cr
        cr

-------------------- 删除p.left或插入c.left导致右左失衡; R(-1,0)=>(0,1)

    p(2)                          p(2)
     \                             \
      c(-1)          ==>           cl(1)             ==>
      /           rotateR(c)         \\           rotateL(p)
     cl(0)                           c(0)

-------------------- 删除pl.child或插入cl.left导致右左失衡; R(-1,-1)=>(1,1);

       p                            p(2)
      / \                          / \
     pl  c(-1)       ==>          pl  cl(1)          ==>
         / \      rotateR(c)         / \\         rotateL(p)
     cl(-1) cr                      x   c(1)
      /                                   \
     x                                     cr

-------------------- 删除pl.child或插入l.right导致右左失衡; R(-1,1)=>(0,2); L(2,2)=>(-1,0)

       p                            p(2)
      / \                          / \                                cl(0)
     pl  c(-1)       ==>          pl  cl(2)          ==>             // \
        /  \      rotateR(c)           \\         rotateL(p)       p(-1) c
      cl(1) cr                         c(0)                        /    / \
        \                              // \                       pl   x   cr
         x                            x    cr