本文将对平衡二叉树的旋转原理进行分析。
至于平衡二叉树是什么，大家可移步度娘，之后回到这里继续浏览。
本文还将使用golang实现二叉树的前中后序的打印，插入（平衡旋转）。
一、基础原理图解话不多说，上图：
1. 基本介绍，字符约定（T、L、R、h、BF）
2. 树高、平衡因子介绍
3. 节点插入的四种类型，以及相应的旋转大法
二、golang 代码实现
废话少说，上golang实现的代码：
1. 定义了一个二叉树的接口 文件目录 tree/tree.go
（请忽略默认int存储数据，大家根据喜好自行优化即可，对于删除和搜索本文并未提供实现，想学习的朋友可根据本文提供的思路自己实现一下，我想这样才能真的理解并记住它）
package tree
type Tree interface {
Insert(int)
PrefaceTraversal() //根左右
InorderTraversal() //左根右
PostTraversal() //左右根
//Delete(int)
//Search(int)
}
2. tree接口实现 文件目录 tree/avl.go
package tree
import (
"log"
"sync"
)
const (
LH = 1 //左高
EH = 0 //等高
RH = -1 //右高
)
//二叉树结构体
type AvlBinary struct {
state bool // 树 长（三声）高的标志
mutex *sync.RWMutex
node *node // node结构体
}
func NewAvlBinary() Tree {
return &AvlBinary{
state: false,
mutex: &sync.RWMutex{},
}
}
func (avl *AvlBinary) Insert(i int) {
avl.mutex.Lock()
defer avl.mutex.Unlock()
avl.node = avl.node.insert(i, &avl.state)
}
func (avl *AvlBinary) PrefaceTraversal() {
if avl != nil {
avl.node.prefaceTraversal()
}
}
func (avl *AvlBinary) InorderTraversal() {
if avl != nil {
avl.node.inorderTraversal()
}
}
func (avl *AvlBinary) PostTraversal() {
if avl != nil {
avl.node.postTraversal()
}
}
//节点结构体
type node struct {
data, bf int // bf 平衡因子
left, right *node
}
//创建节点
func createNode(i int) *node {
return &node{
data: i,
bf: EH,
left: nil,
right: nil,
}
}
//左旋
func (n *node) rotateToLeft() *node {
headNode := n.right
n.right = headNode.left
headNode.left = n
return headNode
}
//右旋
func (n *node) rotateToRight() *node {
headNode := n.left
n.left = headNode.right
headNode.right = n
return headNode
}
//右平衡旋转
func (n *node) rightBalance() *node {
r := n.right
switch r.bf {
case RH: //RR型 ，新入节点在p节点的右孩子的右子树，只做左旋。 旋转后 t与r的平衡因子 都为0
n.bf = EH
r.bf = EH
return n.rotateToLeft()
case LH: //RL型，新入节点在p节点的右孩子的左子树，需要双旋。//
rl := r.left
// 旋转后的平衡因子会根据新入节点的位置有不同的变化，【思考问题】的目的就在于此
//有三种情况:
switch rl.bf {
case LH: //情况一.插入节点后rl的平衡因子为1，即插入到rl的左子树
n.bf = EH
r.bf = RH
case RH: //情况二.插入节点后rl的平衡因子为-1，即插入到rl的右子树
n.bf = LH
r.bf = EH
case EH: //情况三.插入节点后rl的平衡因子为0，这种情况下 rl本就为空，即新入节点就是rl
n.bf = EH
r.bf = EH
}
rl.bf = EH
n.right = r.rotateToRight() //先对最小不平衡子树做右旋转处理
return n.rotateToLeft() //整体做左旋转处理
}
return n
}
//左平衡旋转
func (n *node) leftBalance() *node {
l := n.left
switch l.bf {
case LH: //新入节点在p节点的左孩子的左子树，只做右旋处理
n.bf = EH
l.bf = EH
return n.rotateToRight()
case RH: //新入节点在p节点的左孩子的右子树，要做双旋处理
lr := l.right
switch lr.bf {
case LH:
n.bf = RH
l.bf = EH
case EH:
n.bf = EH
l.bf = EH
case RH:
n.bf = EH
l.bf = LH
}
lr.bf = EH
n.left = l.rotateToLeft()
return n.rotateToRight()
}
return n
}
func (n *node) insert(i int, state *bool) *node {
if n == nil {
*state = true
return createNode(i)
} else {
if i == n.data {
return n
}
if i < n.data { //左子树寻找插入点
newNode := n.left.insert(i, state)
n.left = newNode
//判断平衡因子 是否需要不平衡处理
if *state {
switch n.bf {
case EH:
n.bf = LH
*state = true
case LH: //因本身左子树平衡因子=1，插入左子树则平衡因子+1，故此时需要平衡处理
*state = false
return n.leftBalance()
case RH:
n.bf = EH
*state = false
}
}
} else {
newNode := n.right.insert(i, state)
n.right = newNode
//判断平衡因子 是否需要不平衡处理
if *state {
switch n.bf {
case EH:
n.bf = RH
*state = true
case LH:
n.bf = EH
*state = false
case RH:
*state = false
return n.rightBalance()
}
}
}
}
return n
}
//前序打印
func (n *node) prefaceTraversal() {
if n != nil {
n.print()
n.left.prefaceTraversal()
n.right.prefaceTraversal()
}
}
func (n *node) inorderTraversal() {
if n != nil {
n.left.inorderTraversal()
n.print()
n.right.inorderTraversal()
}
}
func (n *node) postTraversal() {
if n != nil {
n.left.postTraversal()
n.right.postTraversal()
n.print()
}
}
func (n *node) print() {
log.Print(n.data, " 平衡因子:", n.bf)
}3. main文件 文件目录 main.go
package main
import "dataStructure/tree"
func main() {
avl := tree.NewAvlBinary()
avl.Insert(8)
avl.Insert(5)
avl.Insert(12)
avl.Insert(3)
avl.Insert(6)
avl.Insert(16)
avl.Insert(11)
//avl.Insert(14)
//avl.Insert(13)
avl.Insert(20)
avl.Insert(18)
avl.PrefaceTraversal()
}参考书：《大话数据结构》-- 程杰
学习整理：马丁之帜