保持二叉搜索性质的左/右旋转： LEFT-ROTATE(T,x) 01111111111111i11 RIGHT-ROTATE(T,y) 主意子树的父节点的变化 旋转对提高平衡度有帮助，但对红黑性质保持有影响
保持二叉搜索性质的左/右旋转： 旋转对提高平衡度有帮助，但对红黑性质保持有影响 主意子树的父节点的变化
在树T中以x节点为中心左转： LEFT-ROTATE(T.x) 1 y =x.right 6 if x.p==T.nil 2 x.right =y.left 7 T.root =y 3ify.ler≠T.nil 8 elseif x ==x.p.left 4 y.left.p=x 9 x.p.left =y 5 y.p=x.p 10 else x.p.right =y 11 y.left =x 12 2 x.p=y
在树T中以x节点为中心左转：
Improving the Balancing by Rotation The node group 50 to be rotated 50 Root of the group is changed. The middle subtree changes parent
Improving the Balancing by Rotation 50 15 10 25 20 30 40 25 40 15 10 20 30 50 The node group to be rotated Root of the group is changed. The middle subtree changes parent
7 4 11 3 6 9 18 2 14 19 12 17 22 LEFT-ROTATE(T,x) 20 7 4 18 3 6 11 19 2 9 14 22 12 17 20
间题 在红黑树中插入元素与在一 般BST中插入有什么不同？ 你会怎么设想这样的插入过 程？ 关键是颜色的处理
关键是颜色的处理