1.二叉排序樹的介紹
二叉排序樹為一顆二叉樹惭等，或者為空，或者滿足如下條件：
如果它的左子樹不為空办铡，那么左子樹上的所有結(jié)點的值均小于它的根結(jié)點的值
如果它的右子樹不為空辞做，那么右子樹上的左右結(jié)點的值均大于它的根結(jié)點的值
根結(jié)點的左子樹和右子樹又是二叉排序樹。
二叉排序樹通常采用二叉鏈表作為存儲結(jié)構(gòu)寡具。中序遍歷二叉排序樹便可得到一個有序序列秤茅，一個無序序列可以通過構(gòu)造一棵二叉排序樹變成一個有序序列，構(gòu)造樹的過程即是對無序序列進行排序的過程童叠。
2.二叉排序樹的操作
我們對二叉排序的操作有三種：
查找
插入
刪除
其中二叉排序樹是一個動態(tài)樹表框喳，其特點就是樹的結(jié)構(gòu)不是一次生成的，而是在查找過程中，如果關(guān)鍵字不在樹表中五垮，在把關(guān)鍵字插入到樹表中乍惊。而對于刪除操作，它分為三種情況：
- 刪除結(jié)點為葉子結(jié)點（左右子樹均為NULL）放仗，所以我們可以直接刪除該結(jié)點
- 刪除結(jié)點只有左子樹或者右子樹润绎，此時只需要讓其左子樹或者右子樹直接替代刪除結(jié)點的位置，稱為刪除結(jié)點的雙親的孩子匙监，就可以了
- 當(dāng)要刪除的那個結(jié)點凡橱，其左右子樹都存在的情況下，則要從從左子樹中找出一個最大的值那個結(jié)點來替換我們需要刪除的結(jié)點
3.二叉排序樹代碼實現(xiàn)：
class BinarySortTree():
def __init__(self):
self.root = None
def add(self,node):
if self.root == None:
self.root = node
else:
self.root.add(node)
def infixOrder(self):
if self.root == None:
print("None")
else:
self.root.infixOrder()
def delete(self,value):
if self.root == None:
print("None")
else:
self.root.delete(value)
class Node():
def __init__(self,value=None):
self.value = value
self.left = None
self.right = None
self.root = None
def add(self,insertnode):
if insertnode.value < self.value:
if self.left != None:
self.left.add(insertnode)
else:
self.left = insertnode
if insertnode.value > self.value:
if self.right != None:
self.right.add(insertnode)
else:
self.right = insertnode
def infixOrder(self):
if self.left != None:
self.left.infixOrder()
print(self.value)
if self.right != None:
self.right.infixOrder()
def delete(self,value):
#判斷是否為根結(jié)點：
if self.value == value:
self.covervalue,self.covervaluefather = self.left.findmaxvalue()
self.value = self.covervalue
self.covervaluefather.right = None
return
#找到刪除結(jié)點父結(jié)點
# print(self.value)
self.fathernode= self.findcurfathernode(value)
#找到刪除結(jié)點
if self.fathernode.left != None and self.fathernode.left.value == value:
self.delnode = self.fathernode.left
elif self.fathernode.right != None and self.fathernode.right.value == value:
self.delnode = self.fathernode.right
#判斷刪除結(jié)點的三種形態(tài)
#1.刪除結(jié)點左右子結(jié)點均為空
if self.delnode.left == None and self.delnode.right == None:
if self.fathernode.left.value == value:
self.fathernode.left = None
else:
self.fathernode.right = None
#2.刪除結(jié)點左右子結(jié)點均不為空
elif self.delnode.left != None and self.delnode.right != None:
#找當(dāng)前結(jié)點左子樹的最大值亭姥，刪除該結(jié)點并把該結(jié)點的值給當(dāng)前結(jié)點
if self.delnode.left.right == None:
self.delnode.value = self.delnode.left.value
self.delnode.left = None
else:
self.covervalue,self.covervaluefather = self.delnode.left.findmaxvalue()
self.delnode.value = self.covervalue
self.covervaluefather.right = None
#3.刪除結(jié)點左子結(jié)點或右子結(jié)點其中一個為空
else:
if self.fathernode.left != None and self.fathernode.left.value == value:
if self.delnode.left != None:
self.fathernode.left = self.delnode.left
else:
self.fathernode.left = self.delnode.right
else:
if self.delnode.left != None:
self.fathernode.right = self.delnode.left
else:
self.fathernode.right = self.delnode.right
#找到當(dāng)前結(jié)點下子樹的最大值稼钩，即一直往該結(jié)點的右子結(jié)點找就行
def findmaxvalue(self):
if self.right.right != None:
self.right.findmaxvalue()
else:
covervalue = self.right.value
return covervalue,self
#找到待刪除結(jié)點的父結(jié)點
def findcurfathernode(self,value):
if self.right != None and self.right.value == value:
# print("111",self.value)
return self
elif self.left != None and self.left.value == value:
# print("222",self.value)
return self
else:
if self.value > value:
self = self.left.findcurfathernode(value)
else:
self = self.right.findcurfathernode(value)
# print("113331",self.value)
return self
bst = BinarySortTree()
node1 = Node(1)
node3 = Node(3)
node5 = Node(5)
node7 = Node(7)
node9 = Node(9)
node10 = Node(10)
node12 = Node(12)
node2 = Node(2)
bst.add(node7)
bst.add(node3)
bst.add(node10)
bst.add(node12)
bst.add(node5)
bst.add(node1)
bst.add(node9)
bst.add(node2)
bst.infixOrder()
bst.delete(12)
bst.infixOrder()
4.AVL樹的介紹：
AVL 樹是一種平衡二叉樹，得名于其發(fā)明者的名字（ Adelson-Velskii 以及 Landis）达罗。（可見名字長的好處坝撑，命名都能多占一個字母出來）。平衡二叉樹遞歸定義如下：
左右子樹的高度差小于等于 1粮揉。
其每一個子樹均為平衡二叉樹巡李。
平衡因子： 某個結(jié)點的左子樹的高度減去右子樹的高度得到的差值。
基于平衡因子扶认，我們就可以這樣定義 AVL 樹侨拦。
AVL 樹： 所有結(jié)點的平衡因子的絕對值都不超過 1 的二叉樹。
為了計算平衡因子辐宾，我們自然需要在節(jié)點中引入高度這一屬性狱从。在這里，我們把節(jié)點的高度定義為其左右子樹的高度的最大值叠纹。代碼如下：
def height(self,node):
if node == None:
return 0
else:
return max(self.height(node.left),self.height(node.right))+1
當(dāng)平衡因子的絕對值大于 1 時季研，就會觸發(fā)樹的平衡化操作。
樹的平衡化操作
二叉樹的平衡化有兩大基礎(chǔ)操作： 左旋和右旋誉察。左旋与涡，即是逆時針旋轉(zhuǎn)；右旋持偏，即是順時針旋轉(zhuǎn)驼卖。這種旋轉(zhuǎn)在整個平衡化過程中可能進行一次或多次，這兩種操作都是從失去平衡的最小子樹根結(jié)點開始的(即離插入結(jié)點最近且平衡因子超過1的祖結(jié)點)鸿秆。
需要平衡的四種情況
LL 型
RR 型
LR 型
RL 型
AVL 樹的插入和刪除操作
基于上文的再平衡操作款慨，現(xiàn)在我們可以寫出完整的 AVL 樹的插入/刪除操作。
代碼是基于BST樹進行開發(fā)的谬莹，但是AVL樹的刪除還沒有寫檩奠，（太懶了～）
代碼實現(xiàn)
class AVLTree():
def __init__(self):
self.root = None
def add(self,node):
if self.root == None:
self.root = node
else:
self.root.add(node)
def infixOrder(self):
if self.root == None:
print("None")
else:
self.root.infixOrder()
def delete(self,value):
if self.root == None:
print("None")
else:
self.root.delete(value)
def height(self):
if self.root == None:
return 0
else:
print("height",self.root.height(self.root))
class Node():
def __init__(self,value=None):
self.value = value
self.left = None
self.right = None
self.root = None
self.leftheight = 0
self.rightheight = 0
#獲得當(dāng)前結(jié)點的深度
def height(self,node):
if node == None:
return 0
else:
return max(self.height(node.left),self.height(node.right))+1
def add(self,insertnode):
# print("111",self.value)
if insertnode.value < self.value:
if self.left != None:
self.left.add(insertnode)
else:
self.left = insertnode
elif insertnode.value > self.value:
if self.right != None:
self.right.add(insertnode)
else:
self.right = insertnode
#1.首先我知道如果添加一個結(jié)點桩了，只會影響它所在的樹的深度，因此只需要找到它的爺爺及以上埠戳，再去判斷深度井誉，就可以平衡了
#2.問題是怎么從爺爺往根結(jié)點找，這會兒又忘了這是個遞歸的過程整胃，我遞歸的從根結(jié)點一直往待插入結(jié)點的父結(jié)點找插入位置颗圣，完事之后回一直返回，這樣就能從爺爺找到根結(jié)點了
# print("222",self.value)
if self.height(self.left) - self.height(self.right) >1:
if insertnode.value < self.left.value:
self.ll()
else:
self.lr()
elif self.height(self.right) - self.height(self.left) >1:
if insertnode.value < self.right.value:
self.rl()
else:
self.rr()
def infixOrder(self):
if self.left != None:
self.left.infixOrder()
print(self.value)
if self.right != None:
self.right.infixOrder()
def delete(self,value):
#判斷是否為根結(jié)點：
if self.value == value:
self.covervalue,self.covervaluefather = self.left.findmaxvalue()
self.value = self.covervalue
self.covervaluefather.right = None
return
#找到刪除結(jié)點父結(jié)點
# print(self.value)
self.fathernode= self.findcurfathernode(value)
#找到刪除結(jié)點
if self.fathernode.left != None and self.fathernode.left.value == value:
self.delnode = self.fathernode.left
elif self.fathernode.right != None and self.fathernode.right.value == value:
self.delnode = self.fathernode.right
#判斷刪除結(jié)點的三種形態(tài)
#1.刪除結(jié)點左右子結(jié)點均為空
if self.delnode.left == None and self.delnode.right == None:
if self.fathernode.left != None and self.fathernode.left.value == value:
self.fathernode.left = None
else:
self.fathernode.right = None
#2.刪除結(jié)點左右子結(jié)點均不為空
elif self.delnode.left != None and self.delnode.right != None:
#找當(dāng)前結(jié)點左子樹的最大值屁使，刪除該結(jié)點并把該結(jié)點的值給當(dāng)前結(jié)點
if self.delnode.left.right == None:
self.delnode.value = self.delnode.left.value
self.delnode.left = None
else:
self.covervalue,self.covervaluefather = self.delnode.left.findmaxvalue()
self.delnode.value = self.covervalue
self.covervaluefather.right = None
#3.刪除結(jié)點左子結(jié)點或右子結(jié)點其中一個為空
else:
if self.fathernode.left != None and self.fathernode.left.value == value:
if self.delnode.left != None:
self.fathernode.left = self.delnode.left
else:
self.fathernode.left = self.delnode.right
else:
if self.delnode.left != None:
self.fathernode.right = self.delnode.left
else:
self.fathernode.right = self.delnode.right
#找到當(dāng)前結(jié)點下子樹的最大值在岂，即一直往該結(jié)點的右子結(jié)點找就行
def findmaxvalue(self):
if self.right.right != None:
self.right.findmaxvalue()
else:
covervalue = self.right.value
return covervalue,self
#找到待刪除結(jié)點的父結(jié)點
def findcurfathernode(self,value):
if self.right != None and self.right.value == value:
# print("111",self.value)
return self
elif self.left != None and self.left.value == value:
# print("222",self.value)
return self
else:
if self.value > value:
self = self.left.findcurfathernode(value)
else:
self = self.right.findcurfathernode(value)
# print("113331",self.value)
return self
def rr(self):
#右右-> 左旋
print("rr")
head = Node()
head.value = self.value
head.left = self.left
head.right = self.right.left
self.value = self.right.value
self.left = head
self.right = self.right.right
def ll(self):
#左左 -> 右旋
print("ll")
head = Node()
head.value = self.value
head.right = self.right
head.left = self.left.right
self.value = self.left.value
self.right = head
self.left = self.left.left
def lr(self):
#左右先左旋再右旋
print("lr")
self.left.rr()
self.ll()
def rl(self):
#右左先右旋再左旋
print("rl")
self.right.ll()
self.rr()
bst = AVLTree()
node1 = Node(1)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
node10 = Node(10)
node11 = Node(11)
node12 = Node(12)
node13 = Node(13)
node14 = Node(14)
node15 = Node(15)
bst.add(node13)
bst.add(node11)
bst.add(node14)
bst.add(node10)
bst.add(node12)
bst.add(node15)
bst.add(node9)
# bst.add(node15)
# bst.add(node9)
# bst.add(node2)
# bst.add(node3)
# bst.infixOrder()
bst.delete(9)
# bst.infixOrder()
# bst.height()
print(bst.root.value)
print(bst.root.left.value)
print(bst.root.right.value)
print(bst.root.left.left.value)
print(bst.root.left.right.value)
# print(bst.root.right.left.value)
print(bst.root.right.right.value)
# print(bst.root.left.left.left.value)
