左旋
示意图如下
left-rorate.jpg
func LeftRorate(tree *Tree, node *TreeNode) {
if tree.root == nil {
return
}
if node == nil {
return
}
// 左旋 先找到右支的节点
y := node.Right
// y 的左节点变为node的右节点
node.Right = y.Left
// y 的左的父节点变为node节点
if y.Left != nil {
y.Left.Parent = node
}
// y的父节点是 node节点的父节点
y.Parent = node.Parent
// 旋转的节点父节点是空节点-就是根节点
if node.Parent == nil {
tree.root = y
} else if node == node.Parent.Left {
// 是父节点的左节点
node.Parent.Left = y
} else {
// 是父节点的右节点
node.Parent.Right = y
}
//
y.Left = node
//
node.Parent = y
}
func RightRorate(tree *Tree, node *TreeNode) {
y := node.Left
node.Left = y.Right
if y.Right != nil {
y.Right.Parent = node
}
y.Parent = node.Parent
// 说明原来的node是root节点
if y.Parent == nil {
tree.root = y
} else if y.Parent.Left == node {
y.Parent.Left = y
} else {
y.Parent.Right = y
}
y.Right = node
node.Parent = y
}
