算法Go语言描述📌treestruct📌3-avl-rotate.txt
失衡情形旋转前后bf变化
========== LL失衡: R(-2,-1)=>(0,0); R(-2,0)=>(-1,1)
p(-2) | p(-2) c(1)
/ c(0) | / / \\
c(-1) ===> / \\ | c(0) ===> cl p(-1)
/ R(p) cl p(0) | / \ R(p) //
cl | cl cr cr
========== RR失衡: L(2,1)=>(0,0); L(2,0)=>(1,-1)
p(2) | p(2) c(-1)
\ c(0) | \ // \
c(1) ===> // \ | c(0) ===> p(1) cr
\ L(p) p(0) cr | / \ L(p) \\
cr | cl cr cl
========== LR失衡: R(1,0)=>(0,-1)
p(-2) p(-2)
/ //
c(1) ===> cr(-1) ===>
\ L(c) // R(p)
cr(0) c(0)
========== RL失衡: L(-1,0)=>(0,1)
p(2) p(2)
\ \\
c(-1) ===> cl(1) ===>
/ R(c) \\ L(p)
cl(0) c(0)
========== LR失衡: L(1,1)=>(-1,-1)
p(-2) p(-2)
/ \ // \
c(1) pr ===> cr(-1)pr ===>
/ \ L(c) // \ R(p)
cl cr(1) c(-1) x
\ /
x cl
========== LR失衡: L(1,-1)=>(0,-2); R(-2,-2)=>(1,0)
p(-2) p(-2)
/ \ // \ cr(0)
c(1) pr ===> cr(-2)pr ===> /\\
/ \ L(c) // R(p) c p(1)
cl cr(-1) c(0) / \ \
/ / \\ cl x pr
x cl x
========== RL失衡: R(-1,-1)=>(1,1)
p(2) p(2)
/ \ / \\
pl c(-1) ===> pl cl(1) ===>
/ \ R(c) / \\ L(p)
cl(-1)cr x c(1)
/ \
x cr
========== RL失衡: R(-1,1)=>(0,2); L(2,2)=>(-1,0)
p(2) p(2)
/ \ / \\ cl(0)
pl c(-1) ===> pl cl(2) ===> // \
/ \ R(c) \\ L(p) p(-1) c
cl(1)cr c(0) / / \
\ // \ pl x cr
x x cr