Detta skapar en PDF som du sedan kan skriva ut. Du kan även spara ner PDFn och skriva ut senare.
Titel på utskriften?
Tack för ditt bidrag
Om vi kan använda det så lägger vi upp det på sidan. Nedan en länk till ditt bidrag om du vill spara det.
Spara som ...
Du sparar ditt skript under detta namn och kan sedan hämta tillbaka det med samma namn.
Läs in
Läs in ett tidigare sparat skript. Obs att du enbart kan läsa in skript i den webbläsare där du sparade skriptet. Vill du kunna läsa in och spara skript oberoende av webbläsare, så behöver du skaffa ett login (enkelt och gratis).
Skicka in bidrag
Föreslå rubrik
Beskriv vad din kod gör
Skapa kort länk
Använd en kort URL för att skicka länk till koden via SMS eller epost. När mottagaren klickar på länken, så öppnas denna webbsida, med din kod och din text. Länken rensas bort automatiskt om den inte används.
Rubrik (frivilligt)
Beskrivning (frivilligt)
Länk (kopiera hela)
AVL
motiv
Om vi upprepade gånger, i ett binärt träd, plockar ut och sätter in nya data så kommer trädet med tiden bli mer eller mindre obalanserat.
Vi kan, i ett binärt träd, åtgärda detta genom att då och då balansera det binära trädet. Men en bättre lösning vore om trädet alltid håller sig balanserat. Det är vad AVL handlar om. Det självbalanserade binära trädet!
Balansera hela tiden
Så efter att vi gjort insert eller efter vi gjort delete på någon data, så kontrollerar vi om höjdskillnaden i trädet är mer än 1. Om så är fallet, då balanserar vi trädet. Eftersom vi ständigt (vid insert och delete) håller trädet balanserat, så när en obalans uppstår så är det oftast mycket enkelt att fixa. Lite som att ständigt plocka iordning saker där hemma - då blir det aldrig stökigt och behövs aldrig städas.
Om obalans uppstår efter insert eller delete, så fixar vi det alltså direkt. Medans det fortfarande är enkelt.
left och right rotate
Vi har 2 verktyg som vi använder för att hålla trädet balanserat. Det är left rotate och right rotate. Tänk kuben! Se det som 2 stycken rörelser vi gör för att fixa en lokal obalans.
left rotate
Vi flyttar X's pekare till Y, till att istället peka på c och Y's pekare på c flyttar vi att peka på X.
right rotate
Vi flyttar X's pekare på Y, till att istället peka på c och Y's pekare på c flyttar vi att peka på X.
mäta obalansen i trädet
För att mäta obalansen i trädet behöver vi 2 funktioner. Först måste vi kunna mäta höjden. Vi krattar manegen för oss genom att införa en variabel i vår Node -klass som berättar vad en specifik Node ligger på för höjd och sedan håller vi denna variabel uppdaterad. Då blir det enkelt att fråga efter höjden i en viss situation. Vi behöver bara returnera höjden för noden ifråga, detta gör getHeight().
Med en funktion getBalance() så frågar vi helt enkelt efter skillnaden i höjd mellan vänster och höger delträd. En balans större än 1 betyder alltså att trädet är tungt på vänster sida. En balans mindre än 1 betyder att trädet är tungt på höger sida. Samtidigt, när vi sätter in ett nytt värde (eller tar bort), så vet vi om det nya värdet ska sättas in eller tas bort i höger eller vänster delträd. Om trädet är tungt på vänster sida och vi också skall sätta in något på vänster sida (vilket gör det ännu tyngre till vänster), då måste vi alltså fixa denna obalans.
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
Så, beroende på vad vi får för balansvärden, när vi mäter dessa, och beroende på om det vi skall sätta in eller ta bort finns på höger eller vänster sida, så korrigerar vi en eventuell obalans med någon av 4 metoder.
Är balance över 0 så är det tungt åt vänster är balance negativt så det tungt åt höger.
left left
Om balance > 1 och data < root.left.data, dvs det är tungt åt vänster, då korrigerar vi obalansen på följande sätt, genom att anropa rotateRight.
right right
Om balance är mindre än -1, dvs trädet är tungt till höger och data > root.right.data, då korrigerar vi med rotateLeft
left right
Om balance > 1 och data > root.left.data, dvs tungt åt vänster, då kör vi på vänster sida rotateLeft och därefter rotateRight
right left
Om balance < -1 och data < root.right.data, dvs tungt åt höger, då gör vi på höger sida rotateRight och därefter rotateLeft.
insert
class Node:
def __init__(self, data=None, left=None, right=None, height=1):
self.data = data
self.left = left
self.right = right
self.height = height
class AVLTree:
def __init__(self):
self.root = None
def printNodes(self,node, d=0, lr=''):
if(node==None):
return
if(node.right):
self.printNodes(node.right,d+1,'┌')
self.c[d] += (1 if lr =="┌" else -1)
vbrack = ''.join([' ',' │'][self.c[i]] for i in range(1,len(self.c)) if i < d)
print(vbrack+ ('' if d==0 else ' ') + lr +'───┤' +'(' +str(node.data)+')')
if(node.left):
self.printNodes(node.left,d+1,"└")
def print(self):
self.c = [0 for x in range(20)]
self.printNodes(self.root)
def insertNode(self, root, data):
if not root:
return Node(data)
elif data < root.data:
root.left = self.insertNode(root.left, data)
else:
root.right = self.insertNode(root.right, data)
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
# Situation Left Left
if balance > 1 and data < root.left.data:
return self.rotateRight(root)
# Situation Right Right
if balance < -1 and data > root.right.data:
return self.rotateLeft(root)
# Situation Left Right
if balance > 1 and data > root.left.data:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
# Situation Right Left
if balance < -1 and data < root.right.data:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def rotateLeft(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rotateRight(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def insert(self, data):
self.root = self.insertNode(self.root, data)
# Exempel på användning
tree = AVLTree()
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(40)
tree.insert(50)
tree.insert(85)
tree.insert(33)
tree.insert(88)
tree.insert(99)
tree.insert(4)
tree.insert(45)
tree.insert(35)
tree.print()
class Node:
def __init__(self, data=None, left=None, right=None, height=1):
self.data = data
self.left = left
self.right = right
self.height = height
class AVLTree:
def __init__(self):
self.root = None
def printNodes(self,node, d=0, lr=''):
if(node==None):
return
if(node.right):
self.printNodes(node.right,d+1,'┌')
self.c[d] += (1 if lr =="┌" else -1)
vbrack = ''.join([' ',' │'][self.c[i]] for i in range(1,len(self.c)) if i < d)
print(vbrack+ ('' if d==0 else ' ') + lr +'───┤' +'(' +str(node.data)+')')
if(node.left):
self.printNodes(node.left,d+1,"└")
def print(self):
self.c = [0 for x in range(20)]
self.printNodes(self.root)
def insertNode(self, root, data):
if not root:
return Node(data)
elif data < root.data:
root.left = self.insertNode(root.left, data)
else:
root.right = self.insertNode(root.right, data)
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
# Situation Left Left
if balance > 1 and data < root.left.data:
return self.rotateRight(root)
# Situation Right Right
if balance < -1 and data > root.right.data:
return self.rotateLeft(root)
# Situation Left Right
if balance > 1 and data > root.left.data:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
# Situation Right Left
if balance < -1 and data < root.right.data:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def rotateLeft(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rotateRight(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def insert(self, data):
self.root = self.insertNode(self.root, data)
# Exempel på användning
tree = AVLTree()
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(40)
tree.insert(50)
tree.insert(85)
tree.insert(33)
tree.insert(88)
tree.insert(99)
tree.insert(4)
tree.insert(45)
tree.insert(35)
tree.print()
Som du ser när du kör ovan kod, trots att vi stoppar in mängder med data, så är trädet fint och balanserat eftersom trädet håller sig själv balanserat.
delete
class Node:
def __init__(self, data=None, left=None, right=None, height=1):
self.data = data
self.left = left
self.right = right
self.height = height
class AVLTree:
def __init__(self):
self.root = None
def printNodes(self,node, d=0, lr=''):
if(node==None):
return
if(node.right):
self.printNodes(node.right,d+1,'┌')
self.c[d] += (1 if lr =="┌" else -1)
vbrack = ''.join([' ',' │'][self.c[i]] for i in range(1,len(self.c)) if i < d)
print(vbrack+ ('' if d==0 else ' ') + lr +'───┤' +'(' +str(node.data)+')')
if(node.left):
self.printNodes(node.left,d+1,"└")
def print(self):
self.c = [0 for x in range(20)]
self.printNodes(self.root)
def insertNode(self, root, data):
if not root:
return Node(data)
elif data < root.data:
root.left = self.insertNode(root.left, data)
else:
root.right = self.insertNode(root.right, data)
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
# Situation Left Left
if balance > 1 and data < root.left.data:
return self.rotateRight(root)
# Situation Right Right
if balance < -1 and data > root.right.data:
return self.rotateLeft(root)
# Situation Left Right
if balance > 1 and data > root.left.data:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
# Situation Right Left
if balance < -1 and data < root.right.data:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def rotateLeft(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rotateRight(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def insert(self, data):
self.root = self.insertNode(self.root, data)
def delete(self, data):
self.root = self.deleteNode(self.root, data)
def deleteNode(self, root, data):
if not root:
return root
if data < root.data:
root.left = self.deleteNode(root.left, data)
elif data > root.data:
root.right = self.deleteNode(root.right, data)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = self.getMinValueNode(root.right)
root.data = temp.data
root.right = self.deleteNode(root.right, temp.data)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rotateRight(root)
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
if balance < -1 and self.getBalance(root.right) <= 0:
return self.rotateLeft(root)
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def getMinValueNode(self, node):
if node is None or node.left is None:
return node
return self.getMinValueNode(node.left)
avl = AVLTree()
# Insert nodes
nodes = [10, 20, 30, 40, 50, 25]
for node in nodes:
root = avl.insert(node)
avl.print()
avl.delete(30)
avl.delete(20)
print("\n\nRaderar 30 och 20\n\n")
avl.print()
class Node:
def __init__(self, data=None, left=None, right=None, height=1):
self.data = data
self.left = left
self.right = right
self.height = height
class AVLTree:
def __init__(self):
self.root = None
def printNodes(self,node, d=0, lr=''):
if(node==None):
return
if(node.right):
self.printNodes(node.right,d+1,'┌')
self.c[d] += (1 if lr =="┌" else -1)
vbrack = ''.join([' ',' │'][self.c[i]] for i in range(1,len(self.c)) if i < d)
print(vbrack+ ('' if d==0 else ' ') + lr +'───┤' +'(' +str(node.data)+')')
if(node.left):
self.printNodes(node.left,d+1,"└")
def print(self):
self.c = [0 for x in range(20)]
self.printNodes(self.root)
def insertNode(self, root, data):
if not root:
return Node(data)
elif data < root.data:
root.left = self.insertNode(root.left, data)
else:
root.right = self.insertNode(root.right, data)
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
# Situation Left Left
if balance > 1 and data < root.left.data:
return self.rotateRight(root)
# Situation Right Right
if balance < -1 and data > root.right.data:
return self.rotateLeft(root)
# Situation Left Right
if balance > 1 and data > root.left.data:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
# Situation Right Left
if balance < -1 and data < root.right.data:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def rotateLeft(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rotateRight(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def insert(self, data):
self.root = self.insertNode(self.root, data)
def delete(self, data):
self.root = self.deleteNode(self.root, data)
def deleteNode(self, root, data):
if not root:
return root
if data < root.data:
root.left = self.deleteNode(root.left, data)
elif data > root.data:
root.right = self.deleteNode(root.right, data)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = self.getMinValueNode(root.right)
root.data = temp.data
root.right = self.deleteNode(root.right, temp.data)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rotateRight(root)
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
if balance < -1 and self.getBalance(root.right) <= 0:
return self.rotateLeft(root)
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def getMinValueNode(self, node):
if node is None or node.left is None:
return node
return self.getMinValueNode(node.left)
avl = AVLTree()
# Insert nodes
nodes = [10, 20, 30, 40, 50, 25]
for node in nodes:
root = avl.insert(node)
avl.print()
avl.delete(30)
avl.delete(20)
print("\n\nRaderar 30 och 20\n\n")
avl.print()
Som du ser när du klickar kör här ovan, vi kan både lägga till helt random och radera. Trädet håller sig fint och balanserat eftersom trädet balanserar vid behov både vid insert och delete. Det behövs aldrig storstäda eftersom en liten städning görs direkt vid behov.
Vi kan förstås inte göra något åt att det alltid kan bli en obalans i höjdskillnaden på 1 (det är omöjligt, eller hur?). Men en obalans på 2 behöver aldrig uppstå.