golang 手?jǐn)] 平衡二叉樹
樹是一種計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)中非常常用的一種結(jié)構(gòu)，其中就包含了：平衡二叉樹，這種樹是一種特殊的二叉查找樹(二叉查找樹也就是，右孩子大于其父結(jié)點(diǎn)遗菠，左孩子小于其父結(jié)點(diǎn)的樹)，但是簡(jiǎn)單的二叉查找樹存在的問(wèn)題就是不平衡华蜒，最差的查找效率為O(n)辙纬，故就有人發(fā)明了一種平衡的額二叉查找樹。
特點(diǎn)
- 平衡二叉樹是一種二叉查找樹
- 每個(gè)結(jié)點(diǎn)的左子樹的高度減去右子樹的高度的絕對(duì)值不超過(guò)1
- 空樹和左右子樹都是平衡二叉樹
- 相比紅黑樹叭喜，平衡二叉樹比較適用于沒(méi)有刪除的情況
平衡因子
平衡二叉樹是在二叉查查找樹的基礎(chǔ)上進(jìn)行構(gòu)建了贺拣，為了維持平衡二叉樹的平衡，那么就需要一種機(jī)制來(lái)判斷平衡二叉樹是否是平衡的域滥。這種機(jī)制就叫做平衡因子纵柿。
平衡二叉樹的每個(gè)結(jié)點(diǎn)都會(huì)維持一個(gè)值，這個(gè)值就是平衡因子启绰，這個(gè)平衡因子就是這個(gè)結(jié)點(diǎn)的左子樹的高度減去右子樹的高度得到的值昂儒。如果這個(gè)平衡因子的值的絕對(duì)值大于1了，說(shuō)明這個(gè)樹就不平衡了委可，那么就需要調(diào)整樹的結(jié)構(gòu)了渊跋。
我們可以從如上這個(gè)這個(gè)圖中看的到：每個(gè)結(jié)點(diǎn)都維持了一個(gè)值腊嗡，比如左邊的AVL 樹根結(jié)點(diǎn)的值為-1，這個(gè)-1是怎么來(lái)的呢拾酝，就是結(jié)點(diǎn)3的左子樹的高度為 2, 右子樹的高度為 3, 左子樹的高度減去右子樹的高度就得到這個(gè)結(jié)點(diǎn)的平衡因子燕少。
如果某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于了 1 ，那么就說(shuō)明這個(gè)平衡二叉樹不平衡了蒿囤，就需要調(diào)整平衡二叉樹的結(jié)構(gòu)客们。
旋轉(zhuǎn)
由于AVL樹需要做到平衡，所以每次插入葉子節(jié)點(diǎn)材诽，如果發(fā)現(xiàn)不平衡底挫，都需要進(jìn)行旋轉(zhuǎn)以保持平衡。
找到了要給別人做的一個(gè)旋轉(zhuǎn)圖例脸侥，可以參考的看下：
我們來(lái)總結(jié)下以上圖片中出現(xiàn)的這幾種情況：
-
三個(gè)結(jié)點(diǎn)的單旋轉(zhuǎn)
- 我們可以看到上途中結(jié)點(diǎn)3的平衡因子為2了建邓，這樣就不平衡橫了，那么就需要進(jìn)行一個(gè)對(duì)結(jié)點(diǎn)3的順時(shí)針旋轉(zhuǎn)睁枕，旋轉(zhuǎn)完的結(jié)果就是上圖中的右圖官边。
-
三個(gè)結(jié)點(diǎn)的雙旋轉(zhuǎn)
- 針對(duì)這種情況其實(shí)就是上面一種情況的特殊版本：我們要先把這種情況先轉(zhuǎn)化為:
三個(gè)結(jié)點(diǎn)的單旋轉(zhuǎn)這種情況。 - 首先對(duì)結(jié)點(diǎn)11進(jìn)行一個(gè)逆時(shí)針的旋轉(zhuǎn)外遇，然后就變?yōu)榱耍?code>三個(gè)結(jié)點(diǎn)的單旋轉(zhuǎn)注簿。
- 然后再像；
三個(gè)結(jié)點(diǎn)的單旋轉(zhuǎn)一樣的對(duì)結(jié)點(diǎn)3進(jìn)行右旋轉(zhuǎn)臀规。
什么時(shí)候怎樣旋轉(zhuǎn)呢?
-
我們插入一個(gè)結(jié)點(diǎn)后滩援，某個(gè)結(jié)點(diǎn)p的平衡因子由原來(lái)的1變成了2栅隐。
- 那就可能是這兩種情況：
-
新插入的結(jié)點(diǎn)插入到了結(jié)點(diǎn)p的左子樹的左孩子下
-
golang 代碼實(shí)現(xiàn)
// 順時(shí)針旋轉(zhuǎn)塔嬉，右旋 func (avlNode *AVLNode) RightRotate() *AVLNode { headNode := avlNode.Left avlNode.Left = headNode.Right headNode.Right = avlNode // 更新旋轉(zhuǎn)后結(jié)點(diǎn)的高度 avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight())+1 headNode.height = Max(headNode.Left.GetHeight(), headNode.Right.GetHeight())+1 return headNode }
-
新插入的結(jié)點(diǎn)插入到了結(jié)點(diǎn)p的左子樹的右孩子下
從以上例子中我們就可以發(fā)現(xiàn)，順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn)的規(guī)律所在
-
golang 代碼實(shí)現(xiàn)
// 先逆時(shí)針旋轉(zhuǎn)再順時(shí)針旋轉(zhuǎn)租悄，先左旋谨究，在右旋 func (avlNode *AVLNode) LeftThenRightRotate() *AVLNode { // 先把左孩子結(jié)點(diǎn)進(jìn)行左旋 avlNode.Left = avlNode.Left.LeftRotate() // 然后把自己右旋 return avlNode.RightRotate() }
- 從以上的三張圖中我們就可以發(fā)現(xiàn)這樣的一個(gè)容易忽略的問(wèn)題
- 假設(shè)有一個(gè)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)是P泣棋，我們?cè)谀鏁r(shí)針旋轉(zhuǎn)一個(gè)結(jié)點(diǎn)的時(shí)候需要把結(jié)點(diǎn)P的右孩子的左子樹移動(dòng)為結(jié)點(diǎn)P的右子樹
- 假設(shè)有一個(gè)結(jié)點(diǎn)胶哲，這個(gè)結(jié)點(diǎn)是P，我們?cè)陧槙r(shí)針旋轉(zhuǎn)時(shí)潭辈，需要把P結(jié)點(diǎn)的左孩子的右子樹移動(dòng)為P結(jié)點(diǎn)的左子樹
-
我們插入一個(gè)結(jié)點(diǎn)后鸯屿，某個(gè)結(jié)點(diǎn)p的平衡因子由原來(lái)的-1變成了-2。
- 那就可能是這兩種情況：
-
新插入的結(jié)點(diǎn)插入到了結(jié)點(diǎn)p的右子樹的右孩子下
- 那就應(yīng)該進(jìn)行對(duì)結(jié)點(diǎn)p的逆時(shí)針旋轉(zhuǎn)
- 旋轉(zhuǎn)過(guò)程可以參考上圖
- golang 實(shí)現(xiàn)
// 逆時(shí)針旋轉(zhuǎn)把敢，左旋 func (avlNode *AVLNode) LeftRotate() *AVLNode { headNode := avlNode.Right avlNode.Right = headNode.Left headNode.Left = avlNode // 更新結(jié)點(diǎn)的高度 // 這里應(yīng)該注意的俄式應(yīng)該先更新avlNode 的高度寄摆，因?yàn)閔eadNode結(jié)點(diǎn)在avlNode結(jié)點(diǎn)的上面 // headNode計(jì)算高度的時(shí)候要根據(jù)avlNode的高度來(lái)計(jì)算 avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight())+1 headNode.height = Max(headNode.Left.GetHeight(), headNode.Right.GetHeight())+1 return headNode }
-
新插入的結(jié)點(diǎn)插入到了結(jié)點(diǎn)p的右子樹的左孩子下
- 那就因該先對(duì)結(jié)點(diǎn)p的右孩子進(jìn)行順時(shí)針旋轉(zhuǎn)
- 然后在對(duì)結(jié)點(diǎn)p進(jìn)行逆時(shí)針旋轉(zhuǎn)
- 旋轉(zhuǎn)過(guò)程可以參考上圖
- golang 實(shí)現(xiàn)
// 先順時(shí)針旋轉(zhuǎn)再逆時(shí)針旋轉(zhuǎn)，先右旋修赞，再左旋 func (avlNode *AVLNode) RightThenLeftRotate() *AVLNode { // 先把右孩子進(jìn)行右旋 avlNode.Right = avlNode.Right.RightRotate() // 然后把自己右旋 return avlNode.LeftRotate() }
上面我們展示了針對(duì)具體的四種情況婶恼，是怎么怎么旋轉(zhuǎn)的，但是我們要寫一個(gè)函數(shù)用來(lái)判斷這四種情況：
// 調(diào)整AVL樹的平衡
func (avlNode *AVLNode) adjust() *AVLNode {
// 如果右子樹的高度比左子樹的高度大于2
if avlNode.Right.GetHeight() - avlNode.Left.GetHeight() == 2 {
// 如果 avlNode.Right 的右子樹的高度比avlNode.Right的左子樹高度大
// 直接對(duì)avlNode進(jìn)行左旋轉(zhuǎn)
// 否則先對(duì) avlNode.Right進(jìn)行右旋轉(zhuǎn)然后再對(duì)avlNode進(jìn)行左旋轉(zhuǎn)
if avlNode.Right.Right.GetHeight() > avlNode.Right.Left.GetHeight() {
avlNode = avlNode.LeftRotate()
}else{
avlNode = avlNode.RightThenLeftRotate()
}
// 如果左子樹的高度比右子樹的高度大2
}else if avlNode.Right.GetHeight() - avlNode.Left.GetHeight() == -2 {
// 如果avlNode.Left的左子樹高度大于avlNode.Left的右子樹高度
// 那么就直接對(duì)avlNode進(jìn)行右旋
// 否則先對(duì)avlNode.Left進(jìn)行左旋，然后對(duì)avlNode進(jìn)行右旋
if avlNode.Left.Left.GetHeight() > avlNode.Left.Right.GetHeight() {
avlNode = avlNode.RightRotate()
}else {
avlNode = avlNode.LeftThenRightRotate()
}
}
return avlNode
}
golang 實(shí)現(xiàn)
AVLNode
type AVLNode struct {
Left, Right *AVLNode // 表示指向左孩子和右孩子
Data interface{} // 結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)
height int // 記錄這個(gè)結(jié)點(diǎn)此時(shí)的高度
}
AVL樹還需要一些簡(jiǎn)單的獲取和設(shè)置結(jié)點(diǎn)性質(zhì)的方法
注意：每次NewAVLNode的時(shí)候height一定是1勾邦，因?yàn)橐粋€(gè)簡(jiǎn)單的高度最低就是1
// 定義comparer 指針類型
// 用來(lái)比較兩個(gè)結(jié)點(diǎn)中Data的大小
type comparator func(a, b interface{}) int
// compare 指針
var compare comparator
// 新建一個(gè)結(jié)點(diǎn)
func NewAVLNode(data interface{}) *AVLNode {
return &AVLNode{
Left: nil,
Right: nil,
Data: data,
height: 1,
}
}
// 新建AVL 樹
func NewAVLTree(data interface{}, myfunc comparator) (*AVLNode, error) {
if data == nil && myfunc == nil {
return nil, errors.New("不能為空")
}
compare = myfunc
return NewAVLNode(data), nil
}
// 獲取結(jié)點(diǎn)數(shù)據(jù)
func (avlNode *AVLNode) GetData() interface{} {
return avlNode.Data
}
// 設(shè)置結(jié)點(diǎn)數(shù)據(jù)
func (avlNode *AVLNode) SetData(data interface{}) {
if avlNode == nil {
return
}
avlNode.Data = data
}
// 獲取結(jié)點(diǎn)的右孩子結(jié)點(diǎn)
func (avlNode *AVLNode) GetRight() *AVLNode {
if avlNode == nil {
return nil
}
return avlNode.Right
}
// 獲取結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
func (avlNode *AVLNode) GetLeft() *AVLNode {
if avlNode == nil {
return nil
}
return avlNode.Left
}
// 獲取結(jié)點(diǎn)的高度
func (avlNode *AVLNode) GetHeight() int {
if avlNode == nil {
return 0
}
return avlNode.height
}
//比較兩個(gè)子樹高度的大小
func Max(a, b int) int {
if a >= b {
return a
} else {
return b
}
}
查找結(jié)點(diǎn)
查找指定結(jié)點(diǎn)
// 查找指定值
func (avlNode *AVLNode) Find(data interface{}) *AVLNode {
var finded *AVLNode
// 調(diào)用比較函數(shù)比較兩個(gè)結(jié)點(diǎn)的指的大小
switch compare(data, avlNode.Data) {
case -1:
finded = avlNode.Left.Find(data)
case 1:
finded = avlNode.Right.Find(data)
case 0:
return avlNode
}
return finded
}
查找最大結(jié)點(diǎn)
// 查找最大值
func (avlNode *AVLNode) FindMax() *AVLNode {
var finded *AVLNode
if avlNode.Right != nil {
finded = avlNode.Right.FindMin()
} else {
finded = avlNode
}
return finded
}
查找最小結(jié)點(diǎn)
// 查找最小值
func (avlNode *AVLNode) FindMin() *AVLNode { // 遞歸寫法
var finded *AVLNode
if avlNode.Left != nil {
finded = avlNode.Left.FindMin()
} else {
finded = avlNode
}
return finded
}
插入和刪除
插入
// 插入數(shù)據(jù)
// 因?yàn)闆](méi)有定義 結(jié)點(diǎn)的parent指針蚣录，所以你插入數(shù)據(jù)就只能遞歸的插入，因?yàn)槲乙{(diào)整樹的平衡和高度
func (avlNode *AVLNode) Insert(value interface{}) *AVLNode {
if avlNode == nil {
return NewAVLNode(value)
}
switch compare(value, avlNode.Data) {
case -1:
// 如果value 小于 avlNode.Data 那么就在avlNode的左子樹上去插入value
avlNode.Left = avlNode.Left.Insert(value)
avlNode = avlNode.adjust() // 自動(dòng)調(diào)整平衡
case 1:
avlNode.Right = avlNode.Right.Insert(value)
avlNode = avlNode.adjust()
case 0:
fmt.Print("數(shù)據(jù)已經(jīng)存在")
}
// 修改結(jié)點(diǎn)的高度
avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight()) + 1
return avlNode
}
插入數(shù)據(jù)的時(shí)候我們應(yīng)該注意的是眷篇，我們要針對(duì)插入點(diǎn)相關(guān)的父結(jié)點(diǎn)萎河，都要判斷是否平衡，然后就行平衡的調(diào)整蕉饼。
刪除
// 刪除數(shù)據(jù)
func (avlNode *AVLNode) Delete(value interface{}) *AVLNode {
// 沒(méi)有找到匹配的數(shù)據(jù)
if avlNode == nil {
//fmt.Println("不存在", value)
return nil
}
switch compare(value, avlNode.Data) {
case 1:
avlNode.Right = avlNode.Right.Delete(value)
case -1:
avlNode.Left = avlNode.Left.Delete(value)
case 0:
// 找到數(shù)據(jù)公壤，刪除結(jié)點(diǎn)
if avlNode.Left != nil && avlNode.Right != nil { // 結(jié)點(diǎn)有左孩子和右孩子
avlNode.Data = avlNode.Right.FindMin().Data
avlNode.Right = avlNode.Right.Delete(avlNode.Data)
} else if avlNode.Left != nil { // 結(jié)點(diǎn)只有左孩子，無(wú)右孩子
avlNode = avlNode.Left
} else { // 結(jié)點(diǎn)只有右孩子或者無(wú)孩子
avlNode = avlNode.Right
}
}
// 自動(dòng)調(diào)整平衡, 如果avlNode!=nil說(shuō)明執(zhí)行了對(duì)avlNode 的某個(gè)子樹執(zhí)行了刪除結(jié)點(diǎn)椎椰，那么就需要重新調(diào)整樹的平衡
if avlNode != nil {
avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight()) + 1
avlNode = avlNode.adjust() // 自動(dòng)平衡
}
return avlNode
}
