4
我寫了一個python代碼來實現。在編寫代碼時，我完全提到了我的僞代碼。爲了測試我創建的類，我寫了一個測試代碼「app.py」。它從用戶節點的數量和隨機如下生成AVL樹： -python AVL樹插入
from avl import *
import random
n = input("Enter number of nodes: ")
l = random.sample(range(-10000,10001),n)
root = node(l[0])
for x in l:
root = root.insert(x)
print root.key
print "Your tree is\n"
root.inorder()
k = input("Enter integer to insert: ")
root.insert(k)
root.inorder()
k = input("Enter integer to delete: ")
root.delete(k)
root.inorder()
下面是保存在應用程序的avl.py
class node:
def __init__(self,data):
self.left = None
self.right = None
self.key = data
self.height = 1
def calheight(self):
if not self.left:
if not self.right:
return 1
else:
return 1 + self.right.height
else:
if not self.right:
return 1 + self.left.height
else:
return max(self.left.height,self.right.height)+1
def rrotate(self):
p=self.left
self.left=p.right
p.right=self
self=p
self.right.calheight()
self.calheight()
return self
def lrotate(self):
p=self.right
self.right=p.left
p.left=self
self=p
self.left.calheight()
self.calheight()
return self
def dlrotate(self):
self.right = self.right.rrotate()
self = self.lrotate()
return self
def drrotate(self):
self.left = self.left.lrotate()
self = self.rrotate()
return self
def bal(self):
if not self.left:
if not self.right:
return 0
else:
return -(self.right.height)
else:
if not self.right:
return self.left.height
else:
return (self.left.height-self.right.height)
def insert(self,data):
if (data < self.key):
if not self.left:
self.left = node(data)
else:
self.left = self.left.insert(data)
if(self.bal() == 2):
print self.height,"\t",self.left.bal(),"\t",self.bal(),"\t",self.key
if(self.left.bal() == 1):
self = self.rrotate()
else:
self = self.drrotate()
elif (data > self.key):
if not self.right:
self.right = node(data)
else:
self.right = self.right.insert(data)
if(self.bal() == -2):
print self.height,"\t",self.right.bal(),"\t",self.bal(),"\t",self.key
if(self.right.bal() == -1):
self = self.lrotate()
else:
self = self.dlrotate()
else:
print "Key Already Exists"
self.height=self.calheight()
return self
def delete(self,data):
if (data < self.key):
self.left = self.left.delete(data)
elif (data > self.key):
self.right = self.right.delete(data)
else:
if not self.left:
if not self.right:
temp = self
self = None
else:
temp = self.right
self = temp
del temp
elif not self.right:
if not self.left:
temp = self
self = None
else:
temp = self.left
self = temp
del temp
else:
temp = self.right
while temp.left:
temp = temp.left
self.key = temp.key
self.right = self.right.delete(temp.key)
if self:
self.height=self.calheight()
if(self.bal() > 1):
if(self.left.bal() > 0):
self = self.rrotate()
else:
self = self.drrotate()
elif(self.bal() < -1):
if(self.right.bal() < 0):
self = self.lrotate()
else:
self = self.dlrotate()
return self
def inorder(self):
if self.left:
self.left.inorder()
print self.height,"\t",self.bal(),"\t",self.key
if self.right:
self.right.inorder()
輸出的AVL樹實現。 py在一開始似乎很好。但是爲了反覆運行app.py，使用更高的n值（超過50），我開始注意到，一些節點通常具有嚴格大於1或甚至2的絕對值的平衡因子。在一次運行期間，它甚至給出錯誤，因爲它嘗試過向左旋轉沒有正確孩子的節點。
問題最可能出在插入函數。我反覆檢查了我的平衡條件和旋轉算法。理論上他們都很好。 如果有人能夠找到錯誤，我會很高興。
我想這將是太難處理的代碼，並嘗試獲取的錯誤。我想你可以運行你的代碼，並獲得一個插入數字的列表（10-20個節點），使得這種平衡因素髮生。並修改您的代碼以逐個插入數字，並在每個數字後打印樹。與此同時，用一張紙做同樣的事情。找出代碼和樹的不同之處。並嘗試糾正代碼，使其相同。 –