📌算法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