平衡树基础

树

说明

旋转可调整局部高度而保持中序顺序；AVL、红黑树在此基础上维护平衡约束。

分析

右旋把左孩子提升为局部根，原根变成它的右孩子；左旋操作对称。旋转保持所有节点的中序顺序，因而不会破坏搜索树性质。

右旋把3的左孩子2提为局部根，原根3成为2的右孩子，中序仍为1、2、3。若2原有右子树，必须转接给3的左边；旋转之后AVL还需更新高度，红黑树还需维护颜色。

查看图表代码

适用前提与边界

仅有旋转函数还不是完整平衡树，插入或删除后还需维护高度或颜色约束。 右旋要求当前根与左孩子非空，左旋要求根与右孩子非空；返回的新局部根必须接回父节点或全树根。

示例输入与调用

root := &Node{Value: 3, Left: &Node{Value: 2, Left: &Node{Value: 1}}}
	fmt.Println(RotateRight(root).Value)

运行输出

2

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func RotateRight(y *Node) *Node {
	x := y.Left
	y.Left = x.Right
	x.Right = y
	return x
}
func RotateLeft(x *Node) *Node {
	y := x.Right
	x.Right = y.Left
	y.Left = x
	return y
}

func main() {
	root := &Node{Value: 3, Left: &Node{Value: 2, Left: &Node{Value: 1}}}
	fmt.Println(RotateRight(root).Value)
}