Golang实现平衡二叉树
GO语言AVL树1.AVL泛型类型`
type AVLType interface {//所有符合排序树的基类型
~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string | ~uintptr
}
//平衡因子常数
const (
LH = +1 //左高
EH = 0 //等高
RH = -1 // 右高
)
2.AVL结点和AVL树结构
//平衡二叉树（AVL树）结点
type AVLNode[T AVLType] struct {
Data T
bf int //结点平衡因子
LChild, RChild *AVLNode[T] //左右孩子
}
//AVL树
type AVLBiTree[T AVLType] struct {
lock *sync.RWMutex //加入读写锁确保线程安全，效率降低
node *AVLNode[T]
taller, shorter bool
}
3.左右旋和左右平衡
(1). 左旋
//对待平衡二叉树结点左旋处理
func (tree *AVLNode[T]) lRotate() *AVLNode[T] {
var R *AVLNode[T]
R = tree.RChild //R指向tree的右子树
tree.RChild = R.LChild //R的左子树接为tree的右子树
R.LChild = tree
tree = R //tree指向新的根结点
return tree
}
(2).右旋
//对待平衡二叉树结点右旋处理
func (tree *AVLNode[T]) rRotate() *AVLNode[T] {
var L *AVLNode[T]
L = tree.LChild //L指向tree的左子树根节点
tree.LChild = L.RChild //L的右子树接为tree的左子树
L.RChild = tree
tree = L //tree指向新的根结点
return tree
}
(3).左平衡
//左平衡处理
func (tree *AVLNode[T]) leftBalance() *AVLNode[T] {
var L, Lr *AVLNode[T]
L = tree.LChild //L指向tree的左子树根结点
switch L.bf { //检查tree的左子树的平衡度，并做相应处理
case LH:
tree.bf = EH
L.bf = EH
return tree.rRotate()
case RH:
Lr = L.RChild
switch Lr.bf {
case LH:
tree.bf = RH
L.bf = EH
case EH:
tree.bf = EH
L.bf = EH
case RH:
tree.bf = EH
L.bf = LH
}
Lr.bf = EH
tree.LChild = L.lRotate() //对tree的左子树作左旋平衡处理
return tree.rRotate() //对tree做右旋平衡处理
}
return tree
}
(4).右平衡
//右平衡处理
func (tree *AVLNode[T]) rightBalance() *AVLNode[T] {
var R, Rl *AVLNode[T]
R = tree.RChild //L指向tree的左子树根结点
switch R.bf { //检查tree的右子树的平衡度，并做相应处理
case RH:
tree.bf = EH
R.bf = EH
return tree.lRotate()
case LH:
Rl = R.LChild
switch Rl.bf {
case LH:
tree.bf = EH
R.bf = RH
case EH:
tree.bf = EH
R.bf = EH
case RH:
R.bf = EH
tree.bf = LH
}
Rl.bf = EH
tree.RChild = R.rRotate()
return tree.lRotate()
}
return tree
}
4. AVL树的插入
//AVL树树结构插入
func (tree *AVLBiTree[T]) InsertAVL(e T) {
tree.lock.Lock()
defer tree.lock.Unlock()
tree.taller = false // 每次插入要初始化“长高”状态
tree.node = tree.node.insertAVLNode(e, &tree.taller)
}
//平衡二叉树插入结点
func (tree *AVLNode[T]) insertAVLNode(e T, taller *bool) *AVLNode[T] {
if tree == nil {
//插入新结点，树长高
tree = createAVLNode(e)
*taller = true
} else {
if e == tree.Data {
//树中已存在和e有相同关键字的结点则不再插入
*taller = false
return tree
}
if e < tree.Data {
//如果小于tree的值，则应该在tree的左子树中查找
newNode := tree.LChild.insertAVLNode(e, taller)
tree.LChild = newNode
if *taller {
//已插入tree的左子树且左子树长高
switch tree.bf { //检查tree的平衡度
case LH: //原本左子树比右子树高，需要做左平衡处理
*taller = false
return tree.leftBalance()
case RH: //原本右子树高，现在等高
tree.bf = EH
*taller = false
case EH: //原本等高，现在长高
tree.bf = LH
*taller = true
}
}
} else {
//否则在tree的右子树中查找
newNode := tree.RChild.insertAVLNode(e, taller)
tree.RChild = newNode
if *taller {
//已插入tree的右子树且右子树长高
switch tree.bf { //检查tree的平衡度
case RH: //原本右子树比右子树高，需要做有平衡处理
*taller = false
return tree.rightBalance()
case LH: //原本左子树高，现在等高
tree.bf = EH
*taller = false
case EH: //原本等高，现在长高
tree.bf = RH
*taller = true
}
}
}
}
return tree
}
5.AVL树的删除
//删除结点是慢慢摸索调试出来的，没怎么优化，所以比较长
//平衡二叉树删除
func (tree *AVLBiTree[T]) DeleteAVL(e T) {
tree.lock.Lock()
defer tree.lock.Unlock()
tree.shorter = false
tree.node = tree.node.deleteNode(e, &tree.shorter)
}
//平衡二叉树结点删除
func (tree *AVLNode[T]) deleteNode(e T, shorter *bool) *AVLNode[T] {
if tree == nil {
//未找到要删除的值。退出
*shorter = false
return tree
} else {
if e == tree.Data {
//找到要删除的值，开始分情况讨论
//如果是叶子结点，直接删除后返回
if tree.LChild == nil && tree.RChild == nil {
*shorter = false
return tree
} else if tree.RChild == nil { //仅有左叶子结点
*shorter = true
tree.Data = tree.LChild.Data
tree.LChild = nil
return tree
} else if tree.LChild == nil { //仅有右叶子结点
*shorter = true
tree.Data = tree.RChild.Data
tree.RChild = nil
return tree
} else {
//左右子树均存在
switch {
case tree.bf == LH || tree.bf == EH:
Lr := tree.LChild
L := tree
for Lr.RChild != nil {
L = Lr
Lr = Lr.RChild
}
tree.Data = Lr.Data
*shorter = false
if L == tree {
tree.LChild = Lr.LChild
tree.bf = RH
return tree
} else {
L.RChild = Lr.LChild
switch L.bf {
case LH:
return L.leftBalance()
case EH:
L.bf = LH
case RH:
L.bf = EH
}
}
return tree //找到待删除结点的父节点开始删除
case tree.bf == RH:
Rl := tree.RChild
R := tree
for Rl.LChild != nil {
R = Rl
Rl = Rl.LChild
}
tree.Data = Rl.Data
*shorter = false
if R == tree {
tree.RChild = Rl.RChild
tree.bf = LH
return tree
} else {
R.LChild = Rl.RChild
switch R.bf {
case RH:
return R.rightBalance()
case EH:
R.bf = RH
case LH:
R.bf = EH
}
}
return tree //找到待删除结点的父节点开始删除
}
}
} else if e < tree.Data {
newNode := tree.LChild.deleteNode(e, shorter)
if newNode != nil && newNode.LChild == nil && newNode.RChild == nil && e == newNode.Data {
//要删除左子树的叶子结点
tree.LChild = nil //删除左叶子
switch tree.bf {
case RH:
*shorter = true
return tree.rightBalance()
case LH:
*shorter = true
tree.bf = EH
case EH:
*shorter = false
tree.bf = RH
}
} else {
if *shorter {
switch tree.bf {
case LH:
*shorter = false
tree.bf = EH
case EH:
*shorter = true
tree.bf = RH
case RH:
*shorter = false
return tree.rightBalance()
}
}
}
} else {
newNode := tree.RChild.deleteNode(e, shorter)
if newNode != nil && newNode.LChild == nil && newNode.RChild == nil && e == newNode.Data {
//要删除右子树的叶子结点
tree.RChild = nil //删除右叶子
switch tree.bf {
case LH:
*shorter = true
return tree.leftBalance()
case RH:
*shorter = true
tree.bf = EH
case EH:
*shorter = false
tree.bf = LH
}
} else {
if *shorter {
switch tree.bf {
case RH:
*shorter = false
tree.bf = EH
case EH:
*shorter = true
tree.bf = LH
case LH:
*shorter = false
return tree.leftBalance()
}
}
}
}
}
return tree
}
6.总结
因为刚接触go泛型不久，也刚好想实现一下AVL树，所以就简单总结了解了一下平衡二叉树的插入和删除，写的比较粗糙，欢迎各位大佬指正！