Start | avl
 

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)
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()
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()
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å.
18.245935440063 ms