avl树 golang实现

前端之家收集整理的这篇文章主要介绍了avl树 golang实现前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

#Tree


术语:
- 树
- 根
- 节点
- 叶子
- 层次, 根节点
- 深度
- 树的高度, 空树的深度为`-1`, 根的深度为`0`, 一个节点的高度为`0`,所有的树叶的高度都为`0`。


---


##二叉树
每个节点最多有两个孩子,空树也是一棵二叉树,链表是一种特殊的二叉树。


## 二叉排序树(二叉搜索树,B树)


## 满二叉树


## 完全二叉树


## AVL树
AVL树本质上还是一棵二叉搜索树(因此读者可以看到我后面的代码是继承自二叉搜索树的),它的特点是:


1. 本身首先是一棵二叉搜索树。
2. 带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。


例如:
```
5 5
/ \ / \
2 6 2 6
/ \ \ / \
1 4 7 1 4
/ /
3 3
```
上图中,左边的是AVL树,而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1,而右边的树由于结点6没有子树,导致根结点5的平衡因子为2。


假设有一个结点的平衡因子为2(在AVL树中,最大就是2,因为结点是一个一个地插入到树中的,一旦出现不平衡的状态就会立即进行调整,因此平衡因子最大不可能超过2),那么就需要进行调整。由于任意一个结点最多只有两个儿子,所以当高度不平衡时,只可能是以下四种情况造成的:


- 对该结点的左儿子的左子树进行了一次插入(`LL`)。


- 对该结点的左儿子的右子树进行了一次插入(`LR`)。


- 对该结点的右儿子的左子树进行了一次插入(`RL`)。


- 对该结点的右儿子的右子树进行了一次插入(`RR`)。


情况1和4是关于该点的镜像对称,同样,情况2和3也是一对镜像对称。因此,理论上只有两种情况,当然了,从编程的角度来看还是四种情况。


第一种情况是插入发生在“外边”的情况(即左-左的情况或右-右的情况),该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况(即左-右的情况或右-左的情况),该情况要通过稍微复杂些的双旋转来处理。




`旋转:`


###单旋转
情况1(`LL`):对该结点的左儿子的左子树进行了一次插入。
![](http://blog.chinaunix.net/attachment/201108/14/25324849_1313308607C3xL.jpg)




左边为调整前得节点,我们可以看出k2的左右子树已不再满足AVL平衡条件,调整后的为右图。


由于K2的左孩子已经变大了,所以应该降低K1的高度,把K1往上提,而K2相应也得往下降。k2下降在k1的右子树(因为k1的左子树增加了,所以不可能再把k2降到k1的左子树上),Y变为K2的左子树(如果Y变成K2的有子树,那么k2的本身没有了左子树,还降为右子树,那么就一减一加,左右失调,平衡因子变成2)。


情况2(`LR`):对该节点的左孩子进行了一次插入
![](../../pic/2676FCA1-CF64-48B2-B4A7-73C41E8C16A7.png)


先从最先失去平衡的节点开始分析,B的left为h,right为h+2,失去平衡,c往上提,B往下提,以致降低整棵树的高度(可以理解为`B,Bl,C,Cl,Cr`这颗树,先把A ignore),C已经平衡,但是A失去平衡,C往上提,A往下降,以致降低整棵树(`C,A,Ar`),Cr连到A的left防止A的right变大而失去平衡,最终C,B,A都已经平衡。


其实他们之间的方法都是一致的,高的节点往上提已经降低其高度,高的往下提,增加高度。这里的***高度可以理解为树的高度***,他们采用的是一种策略,这是一种平衡左右子树的`趋势`


情况3(`RR`):


![](../../pic/7109344F-642A-4AC0-9F89-9B576FB59578.png)




情况4(`RL`)


![](../../pic/1CB097E6-D404-4CEC-8442-1DE3B3096A52.png)
实现代码


---
---


## B-树,B+树


---


---




package main

import (
	"fmt"
)

type DataType int
type Node AVLTreeNode
type AVLTree *AVLTreeNode

type AVLTreeNode struct {
	key   DataType
	high  int
	left  *AVLTreeNode
	right *AVLTreeNode
}

func main() {
	data := []DataType{3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9}
	fmt.Println(data)
	var root AVLTree = nil
	for _,value := range data {
		root = avl_insert(root,value)
		fmt.Println(" root -> key: ",root.key,"high :",root.high,"left",root.left,"right: ",root.right)
	  //  preorder(root)
	}
	preorder(root)
	fmt.Println()
	midorder(root)
	fmt.Println()
}


func highTree(p AVLTree) int {
	if p == nil {
		return -1
	} else {
		return p.high
	}
}

func max(a,b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

/*Please look LL*/
func left_left_rotation(k AVLTree) AVLTree {
	var kl AVLTree
	kl = k.left
	k.left = kl.right
	kl.right = k
	k.high = max(highTree(k.left),highTree(k.right)) + 1
	kl.high = max(highTree(kl.left),k.high) + 1
	return kl
}

/*Please look RR*/
func right_right_rotation(k AVLTree) AVLTree {
	var kr AVLTree
	kr = k.right
	k.right = kr.left
	kr.left = k
	k.high = max(highTree(k.left),highTree(k.right)) + 1
	kr.high = max(k.high,highTree(kr.right)) + 1
	return kr
}

/*so easy*/
func left_righ_rotation(k AVLTree) AVLTree {
	k.left = right_right_rotation(k.left)
	return left_left_rotation(k)
}

func right_left_rotation(k AVLTree) AVLTree {
	k.right = left_left_rotation(k.right)
	return right_right_rotation(k)
}

func avl_insert(avl AVLTree,key DataType) AVLTree {
	if avl == nil {
		avl = new(AVLTreeNode)
		if avl == nil {
			fmt.Println("avl tree create error!")
			return nil
		}else {
			avl.key = key
			avl.high = 0
			avl.left = nil
			avl.right = nil
		}
	} else if key < avl.key {
		avl.left = avl_insert(avl.left,key)
		if highTree(avl.left)-highTree(avl.right) == 2 {
			if key < avl.left.key { //LL
				avl = left_left_rotation(avl)
			} else { // LR
				avl = left_righ_rotation(avl)
			}
		}
	} else if key > avl.key {
		avl.right = avl_insert(avl.right,key)
		if (highTree(avl.right) - highTree(avl.left)) == 2 {
			if key < avl.right.key { // RL
				avl = right_left_rotation(avl)
			} else {
				fmt.Println("right right",key)
				avl = right_right_rotation(avl)
			}
		}
	} else if key == avl.key {
		fmt.Println("the key",key,"has existed!")
	}
	//notice: update high(may be this insert no rotation,so you should update high)
	avl.high = max(highTree(avl.left),highTree(avl.right)) + 1
	return avl
}

func preorder(avl AVLTree) {
	if avl != nil {
		fmt.Print(avl.key,"\t")
		preorder(avl.left)
		preorder(avl.right)
	}
}

func midorder(avl AVLTree) {
	if avl != nil {
		midorder(avl.left)
		fmt.Print(avl.key,"\t")
		midorder(avl.right)
	}
}

/*display avl tree*/
func display(avl AVLTree) {

}
原文链接:https://www.f2er.com/go/190799.html

猜你在找的Go相关文章