樹(shù)結(jié)構(gòu)
-
樹(shù)
樹(shù)結(jié)構(gòu)是由一個(gè)父節(jié)點(diǎn)以及若干個(gè)子節(jié)點(diǎn)，然后子節(jié)點(diǎn)又是其他子節(jié)點(diǎn)的父節(jié)點(diǎn)埂陆，由此而形成的一種結(jié)構(gòu)即是樹(shù)刽沾。其中節(jié)點(diǎn)的子節(jié)點(diǎn)的子節(jié)點(diǎn)叫做該節(jié)點(diǎn)的孫節(jié)點(diǎn)。如下所示:
-
二叉樹(shù)(Binary Tree, BT)
二叉樹(shù)是樹(shù)結(jié)構(gòu)的應(yīng)用形式之一峭跳，二叉樹(shù)每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)膘婶，如上面第三個(gè)樹(shù)結(jié)構(gòu)所示，位于左邊的子節(jié)點(diǎn)叫做左孩子或者左子節(jié)點(diǎn)蛀醉，位于右邊的叫做右孩子或者右子節(jié)點(diǎn)悬襟。
-
二叉搜索(查找)樹(shù)(Binary Search Tree, BST)
二叉搜索樹(shù)是二叉樹(shù)的應(yīng)用之一，在一棵二叉搜索樹(shù)中拯刁，左子樹(shù)上所有節(jié)點(diǎn)的值都小于或者等于其根節(jié)點(diǎn)的值脊岳，而右子樹(shù)上所有節(jié)點(diǎn)的值總是大于或者等于根節(jié)點(diǎn)的值，由此便構(gòu)成了一棵有序的樹(shù)結(jié)構(gòu)。如下圖所示:
-
平衡二叉樹(shù)(AVL)
二叉搜索樹(shù)是一棵有序的樹(shù)割捅，但是大多數(shù)情況下奶躯，往二叉搜索樹(shù)中插入節(jié)點(diǎn)時(shí)，可能存在的情況是插入的節(jié)點(diǎn)始終位于一個(gè)分支上亿驾，如下圖所示:
這樣就出現(xiàn)了一種不盡如人意的情況嘹黔，就是在一棵二叉搜索樹(shù)中，某一個(gè)分支節(jié)點(diǎn)很少莫瞬，而另一個(gè)分支上節(jié)點(diǎn)卻很多儡蔓，導(dǎo)致在查找、插入疼邀、刪除等操作上效率很低喂江。
在一棵二叉搜索樹(shù)中，對(duì)于某一個(gè)節(jié)點(diǎn)旁振，如果該節(jié)點(diǎn)左子樹(shù)和右子樹(shù)的高度差的絕對(duì)值超過(guò)了abs(h) > 1获询，則稱該樹(shù)為非平衡二叉搜索樹(shù)。為了改善這種情況拐袜，便出現(xiàn)了平衡二叉樹(shù)吉嚣，顧名思義，平衡二叉樹(shù)任意一個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)高度差的絕對(duì)值都abs(h)<=1阻肿。平衡二叉樹(shù)是在二叉搜索樹(shù)的基礎(chǔ)上瓦戚，增加了平衡二叉樹(shù)的操作，使得二叉搜索樹(shù)是一棵平衡樹(shù)丛塌。如下圖為一棵平衡二叉樹(shù):
平衡查找樹(shù)的平衡
前面已經(jīng)提到什么是平衡二叉樹(shù)较解，那么怎么樣形成一棵平衡的二叉樹(shù)呢？
權(quán)威們給出的答案是旋轉(zhuǎn)赴邻，即通過(guò)對(duì)二叉樹(shù)進(jìn)行旋轉(zhuǎn)來(lái)改變樹(shù)的結(jié)構(gòu)并且不改變節(jié)點(diǎn)值的順序印衔，從而得到一棵平衡的二叉樹(shù)。下面介紹樹(shù)的旋轉(zhuǎn)姥敛，樹(shù)的旋轉(zhuǎn)分為左旋轉(zhuǎn)奸焙、右旋轉(zhuǎn)以及左右旋轉(zhuǎn)，右左旋轉(zhuǎn)彤敛。
因?yàn)闃?shù)的節(jié)點(diǎn)個(gè)數(shù)變化為1与帆、2、3...n墨榄，所以當(dāng)節(jié)點(diǎn)總數(shù)小于3時(shí)一棵二叉搜索樹(shù)一定是平衡的玄糟，如下圖:
此時(shí)左子樹(shù)的高度與右子樹(shù)的高度差的絕對(duì)值為1，所以是平衡的(在下文中提到的高度差都是左子樹(shù)高度減去右子樹(shù)高度)袄秩。但是隨著節(jié)點(diǎn)的插入阵翎，有可能變成不平衡的了逢并。以下為需要旋轉(zhuǎn)操作進(jìn)行平衡二叉樹(shù)的情況，均是針對(duì)最少節(jié)點(diǎn)數(shù)的情況郭卫，即需要旋轉(zhuǎn)操作的最小子樹(shù)砍聊。
注: 下文提到的高度差均為左子樹(shù)減去右子樹(shù)的高度差的絕對(duì)值，同時(shí)本文中的平衡二叉樹(shù)為左節(jié)點(diǎn)小于父節(jié)點(diǎn)贰军，父節(jié)點(diǎn)小于右節(jié)點(diǎn)
- 左旋轉(zhuǎn)
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡玻蝌。root只有右孩子的情況，以root的右孩子為中心谓形，向左(逆時(shí)針)旋轉(zhuǎn)root節(jié)點(diǎn)灶伊，旋轉(zhuǎn)結(jié)果為root節(jié)點(diǎn)變?yōu)閞oot右孩子的左孩子，如下圖, 在右子樹(shù)添加節(jié)點(diǎn)(圖中的16)寒跳，造成不平衡:
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡，其中root同時(shí)有左右子樹(shù)竹椒，左子樹(shù)只有一個(gè)節(jié)點(diǎn)童太，右孩子只有一個(gè)右子節(jié)點(diǎn)，添加一個(gè)節(jié)點(diǎn)(下圖中的17)后造成不平衡樹(shù)胸完，此時(shí)可以看到书释，root的右子樹(shù)不平衡，此時(shí)按照第一種旋轉(zhuǎn)方式可以將右子樹(shù)旋轉(zhuǎn)平衡赊窥，進(jìn)而使整棵樹(shù)平衡爆惧，如下圖:
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡，其中root只有一個(gè)左孩子锨能，root的右孩子同時(shí)存在左右孩子扯再，如下圖:
從上面可以看出，如果root右子樹(shù)比左子樹(shù)高2址遇，并且右子樹(shù)的右子樹(shù)比右子樹(shù)的左子樹(shù)高熄阻，則執(zhí)行左旋轉(zhuǎn)，以下是左旋轉(zhuǎn)的代碼(Golang):
type Element interface {
Value() interface{}
Compare(Element) int //相等返回0倔约，小于返回負(fù)數(shù)秃殉，大于返回正數(shù)
}
type AVLNode struct {
Data Element //存放的元素
Height int //存放節(jié)點(diǎn)的高度
Left *AVLNode //左子樹(shù)
Right *AVLNode //右子樹(shù)
}
func (avl *AVLNode) Max() *AVLNode {
node := avl
for node.Right != nil {
node = node.Right
}
return node
}
func getHeight(avl *AVLNode) int {
if avl != nil {
return avl.Height
}
return 0
}
func max(h1, h2 int) int {
if h1 > h2 {
return h1
}
return h2
}
func leftRotate(avl *AVLNode) *AVLNode {
if avl == nil {
return nil
}
node := avl.Right
avl.Right = node.Left
node.Left = avl
avl.Height = max(getHeight(avl.Left), getHeight(avl.Right)) + 1
node.Height = max(getHeight(node.Left), getHeight(node.Right)) + 1
return node
}
- 右旋轉(zhuǎn)
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡, root沒(méi)有右孩子，同時(shí)左孩子只有左孩子一個(gè)節(jié)點(diǎn), 此時(shí)以root的左孩子為中心浸剩，進(jìn)行右旋轉(zhuǎn)(順時(shí)針旋轉(zhuǎn)), 將root左孩子提升為root钾军，root降為左孩子的右孩子，如下圖:
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡, root同時(shí)包含左右孩子绢要，右孩子沒(méi)有子節(jié)點(diǎn)吏恭，左孩子只有一個(gè)左孩子節(jié)點(diǎn)，此時(shí)root的左子樹(shù)為不平衡樹(shù)袖扛，按照上面的方式對(duì)左子樹(shù)進(jìn)行右旋轉(zhuǎn)得到平衡樹(shù)砸泛，如下圖:
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡, root只有一個(gè)右孩子, 左孩子同時(shí)有左右孩子, 在左孩子的左孩子下添加一個(gè)節(jié)點(diǎn), 如下圖:
從上面可以看出, 如果root左子樹(shù)比右子樹(shù)高2十籍，并且左子樹(shù)的左子樹(shù)比左子樹(shù)的右子樹(shù)高，則執(zhí)行右旋轉(zhuǎn)唇礁，以下是右旋轉(zhuǎn)的代碼(Golang):
func rightRotate(avl *AVLNode) *AVLNode {
if avl == nil {
return nil
}
node := avl.Left //左子樹(shù)
avl.Left = node.Right //左子樹(shù)的右子樹(shù)變?yōu)樽笞訕?shù)
node.Right = avl //avl降為左子樹(shù)的右子樹(shù)
//更新節(jié)點(diǎn)高度
avl.Height = max(getHeight(avl.Left), getHeight(avl.Right)) + 1
node.Height = max(getHeight(node.Left), getHeight(node.Right)) + 1
return node
}
- 左右旋轉(zhuǎn)
左右旋轉(zhuǎn)是指先執(zhí)行左旋轉(zhuǎn)再執(zhí)行右旋轉(zhuǎn)勾栗。
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡，root只有左子樹(shù)盏筐，且左子樹(shù)只有一個(gè)節(jié)點(diǎn)围俘，如下圖:
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡，root同時(shí)有左右孩子琢融，root的左孩子同時(shí)有左右孩子界牡，在root的左孩子的右孩子上添加左節(jié)點(diǎn)造成不平衡，如下圖:
- 在左子樹(shù)添加節(jié)點(diǎn)造成不平衡漾抬，root同時(shí)有左右孩子宿亡，root的左孩子同時(shí)有左右孩子，在root的左孩子的左孩子上添加右節(jié)點(diǎn)造成不平衡纳令，如下圖:
從上面可以看出, 如果root左子樹(shù)比右子樹(shù)高2挽荠，并且左子樹(shù)的右子樹(shù)比左子樹(shù)的左子樹(shù)高2，則先執(zhí)行左旋轉(zhuǎn)平绩，再執(zhí)行右旋轉(zhuǎn)圈匆，以下是左右旋轉(zhuǎn)的代碼(Golang):
//先將左孩子左旋轉(zhuǎn)，自己再右旋轉(zhuǎn)
func (avl *AVLNode) leftRightRotate() *AVLNode {
avl.Left = avl.Left.leftRotate()
return avl.rightRotate()
}
- 右左旋轉(zhuǎn)
右左旋轉(zhuǎn)是指先執(zhí)行右旋轉(zhuǎn)再執(zhí)行左旋轉(zhuǎn)捏雌。
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡, root只有右子樹(shù)跃赚，且右子樹(shù)只有一個(gè)節(jié)點(diǎn)，如下圖:
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡, root同時(shí)有左右孩子性湿，root的右孩子同時(shí)有左右孩子纬傲，在root的右孩子的左孩子上添加右節(jié)點(diǎn)，如下圖:
- 在右子樹(shù)添加節(jié)點(diǎn)造成不平衡, root同時(shí)有左右孩子窘奏，root的右孩子同時(shí)有左右孩子嘹锁，在root的右孩子的左孩子上添加左節(jié)點(diǎn)，如下圖:
從上面可以看出, 如果root右子樹(shù)比左子樹(shù)高2, 并且右子樹(shù)的右子樹(shù)比右子樹(shù)的左子樹(shù)矮, 則執(zhí)行右旋轉(zhuǎn)后再執(zhí)行左旋轉(zhuǎn)着裹，以下是左右旋轉(zhuǎn)的代碼(Golang):
//先將右孩子右旋轉(zhuǎn)领猾，然后自己右旋轉(zhuǎn)
func (avl *AVLNode) rightLeftRotate() *AVLNode {
avl.Right = avl.Right.rightRotate()
return avl.leftRotate()
}
綜上可以得出平衡二叉查找樹(shù)的函數(shù)為:
//調(diào)整樹(shù)為二叉平衡樹(shù)
func balance(avl *AVLNode) *AVLNode {
if avl == nil {
return nil
}
if getHeight(avl.Right)-getHeight(avl.Left) == 2 {
if getHeight(avl.Right.Right) > getHeight(avl.Right.Left) {
avl = avl.leftRotate()
} else {
avl = avl.rightLeftRotate()
}
} else if getHeight(avl.Left)-getHeight(avl.Right) == 2 {
if getHeight(avl.Left.Left) > getHeight(avl.Left.Right) {
avl = avl.rightRotate()
} else {
avl = avl.leftRightRotate()
}
}
return avl
}
插入、刪除節(jié)點(diǎn)
以上為樹(shù)的旋轉(zhuǎn)操作骇扇，用于平衡二叉查找摔竿，對(duì)于二叉查找樹(shù)，每添加或者插入一個(gè)節(jié)點(diǎn)后均需要執(zhí)行一次平衡操作少孝。代碼如下:
//添加節(jié)點(diǎn)
func (avl *AVLNode) AddNode(data Element) (root *AVLNode, ok bool) {
defer func() {
if ok {
root = balance(avl)
root.Height = max(getHeight(root.Left), getHeight(root.Right)) + 1
}
}()
var target = &AVLNode{
Data: data,
Height: 1,
Left: nil,
Right: nil,
}
cmpResult := avl.Data.Compare(data)
switch {
case cmpResult > 0:
if avl.Left == nil {
avl.Left = target
ok = true
return
}
avl.Left, ok = avl.Left.AddNode(data)
return
case cmpResult < 0:
if avl.Right == nil {
avl.Right = target
ok = true
return
}
avl.Right, ok = avl.Right.AddNode(data)
return
default:
ok = true
return
}
}
func (avl *AVLNode) RemoveNode(data Element) (root *AVLNode, ok bool) {
defer func() {
if ok && root != nil {
root = balance(root)
root.Height = max(getHeight(root.Left), getHeight(root.Right)) + 1
}
}()
var temp *AVLNode
cmpResult := avl.Data.Compare(data)
switch {
case cmpResult > 0:
if avl.Left == nil {
return nil, false
}
temp, ok = avl.Left.RemoveNode(data)
if ok {
avl.Left = temp
}
root = avl
return
case cmpResult < 0:
if avl.Right == nil {
return nil, false
}
temp, ok = avl.Right.RemoveNode(data)
if ok {
avl.Right = temp
}
root = avl
return
default:
if avl.Left == nil && avl.Right == nil {
return nil, true
}
if avl.Left == nil {
root, ok = avl.Right, true
return
}
if avl.Right == nil {
root, ok = avl.Left, true
return
}
//將左子樹(shù)最大節(jié)點(diǎn)提升到頭節(jié)點(diǎn)继低，并將該最大節(jié)點(diǎn)從左子樹(shù)中刪除
avl.Data = avl.Left.Max().Data
avl.Left, ok = avl.Left.RemoveNode(avl.Data)
root = avl
return
}
}
最后
謝謝！
