Start | bst
 

BST



BST står för Binary Search Tree eller kanske Binärt Sök Träd på svenska. Binärt, därför att trädet enbart har en förgrening på 2 noder i varje nod, en left och en right.

Binärt sökträd

Så, om du tagit dig igenom den allmänna genomgången av träd så är kanske binärt sökträd inledningsvis en liten nerförsbacke. I varje nod har vi enbart (max) 2 stycken child och de brukar traditionellt kallas left och right. Det blir glasklart framöver att detta är geniala namn.
class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right
Eftersom du redan har koll på hur träd fungerar så går vi fram lite snabbare nu. Vi skapar en utility -class som håller alla metoder för det binära sökträdet. Vi kan kalla det BSTree och vår första metod kan vara insert() samt print().

insert

En egenskap i ett binärt träd är att vi alltid ska kunna hitta ett värde genom att följa några enkla regler.

1. Om värdet vi letar efter är större än nodens data, då går vi åt höger i trädet - annars vänster.
2. Vi upprepar (1) tills vi hittat värdet.

För att denna egenskap skall upprätthållas kräver det att vi stoppar in värde i det binära trädet med samma regler.

1. Om värdet vi vill stoppa in är större än nodens data, då går vi åt höger i trädet - annars vänster.
2. Vi upprepar (1) tills vi hittat en nod där vi kan göra insert().



Det binära trädet är på så vis alltid sorterat. Om vi skriver ut trädet in-order så blir utskriften alltid sorterad. Vi utnyttjar denna egenskap när vi balanserar trädet genom att konvertera det obalanserade trädet till en array och sedan tillbaka till en balanserad binärt träd. Mer om det längre ner.
class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class BSTree: 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, node , data): if node is None: return Node(data) if data < node.data: node.left = self.insertNode(node.left, data) elif data > node.data: node.right = self.insertNode(node.right, data) return node def insert(self, data): self.root = self.insertNode(self.root , data) tree = BSTree() tree.insert(20) tree.insert(25) tree.insert(15) tree.insert(10) tree.insert(50) tree.insert(24) tree.print() print("\n\nVi sätter in 17\n") tree.insert(17) tree.print()

delete

För att radera en nod följer vi några regler. Exakt vad vi behöver göra beror lite på.

Funktionen börjar med att leta upp noden som skall raderas genom att jämföra värdet data med nodens värde (node.data).

- Om data är mindre än nodens värde, fortsätter funktionen att söka i vänstra subträdet.
- Om data är större än nodens värde, fortsätter funktionen att söka i högra subträdet.
- Om data är lika med nodens värde, har vi hittat noden som ska raderas.

Vad vi nu gör beror lite på. Det finns 3 situationer. De 2 första är enkla. Om vi har att göra med ett löv, då sätter vi helt enkelt pekaren, som pekar mot lövet, till None. Dvs, lövet försvinner.



En annan situation kan vara att noden som skall raderas har 1 barn. Vad vi då gör är att när vi letat upp noden som skall raderas, så kopplar vi helt enkelt förbi den. Dvs, vi flyttar pekaren som pekar mot noden som skall raderas, till noden efter. Vi kopplar förbi den som skall bort.



Sista situationen är mer komplicerad. När vi letat reda på noden som skall raderas, så anropar vi gerSuccessor() ("efterträdaren", den som skall ersätta) som hjälper oss hitta noden till vänster. Vi kopierar sedan värdet i ersättaren till den som skall raderas. Därmed är den som ska raderas i praktiken utplånad och vi har 2 kopior med ersättarens data. Vi raderar ersättaren. Kvar är en kopia av ersättaren i det ställe där den som ska raderas var.



class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class BSTree: root = None def getSuccessor(self, curr): curr = curr.right while curr is not None and curr.left is not None: curr = curr.left return curr def deleteNode(self, node, data): if(node==None): return node if (node.data > data): node.left = self.deleteNode(node.left, data) elif (node.data < data): node.right = self.deleteNode(node.right, data) else: # 0 barn eller enbart right child # ta bort noden eller ersätt med right child # om right child är None samma som inga barn if node.left is None: return node.right # Om python kommit hit finns left child # om right child är None så är left child # enda barnet och vi ersätter noden med # enda barnet if node.right is None: return node.left # båda barn är närvarande = komplicerat !!! succ = self.getSuccessor(node) node.data = succ.data node.right = self.deleteNode(node.right, succ.data) return node def delete(self, data): self.deleteNode(self.root, data) 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, node , data): if node is None: return Node(data) if data < node.data: node.left = self.insertNode(node.left, data) elif data > node.data: node.right = self.insertNode(node.right, data) return node def insert(self, data): self.root = self.insertNode(self.root , data) tree = BSTree() tree.insert(20) tree.insert(25) tree.insert(15) tree.insert(10) tree.insert(50) tree.insert(24) tree.print() print("\n\nVi tar bort 50\n") tree.delete(50) tree.print() print()

balansera binärt träd

Ett problem med ett binärt träd, det är att om vi plockar ut och sätter in element så blir det med tiden obalanserat.



Dvs, det blir väldigt ojämt och icke-optimalt. Så, vissa data kommer gå snabbt hitta i trädet - andra långsammare. Vi kan åtgärda detta obalanserade träd genom att balansera det.

1. Vi travererar BST inorder och lagrar data i en lista. Detta tar O(n) tid. Observera att inorder tillsammans med binära trädets egenskaper medför att listan kommer vara sorterad.
2. Bygger om trädet. Plockar fram mitten av listan och betraktar det som en root. Vi gör detta rekursivt för vänster och höger delträd, där vi delar repektive halva av listan och plockar fram respektive mitt (root).
class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class BSTree: root = None def getSuccessor(self, curr): curr = curr.right while curr is not None and curr.left is not None: curr = curr.left return curr def deleteNode(self, node, data): if(node==None): return node if (node.data > data): node.left = self.deleteNode(node.left, data) elif (node.data < data): node.right = self.deleteNode(node.right, data) else: if node.left is None: return node.right if node.right is None: return node.left succ = self.getSuccessor(node) node.data = succ.data node.right = self.deleteNode(node.right, succ.data) return node def delete(self, data): self.deleteNode(self.root, data) 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, node , data): if node is None: return Node(data) if data < node.data: node.left = self.insertNode(node.left, data) elif data > node.data: node.right = self.insertNode(node.right, data) return node def insert(self, data): self.root = self.insertNode(self.root , data) def inorderTraversal(self, node, result): if node: self.inorderTraversal(node.left, result) result.append(node.data) self.inorderTraversal(node.right, result) def balanceBST(self): # Steg 1: Gör om trädet till en lista sorted_nodes = [] self.inorderTraversal(self.root, sorted_nodes) # Steg 2: Bygg om ett balanserat BST från den sorterade listan self.root = self.buildBalancedBST(sorted_nodes, 0, len(sorted_nodes) - 1) def buildBalancedBST(self, nodes, start, end): if start > end: return None mid = (start + end) // 2 node = Node(nodes[mid]) node.left = self.buildBalancedBST(nodes, start, mid - 1) node.right = self.buildBalancedBST(nodes, mid + 1, end) return node tree = BSTree() print("\n\nVi bygger ett optimalt o-balanserat träd\n") for x in range(1,15): tree.insert(x*10) tree.print() print("\n\nVi balanserar ...\n") tree.balanceBST() tree.print() print("\n\nVi tar bort ett gäng noder\n") for x in [150,50,100,30,40,60,130,90]: tree.delete(x) tree.delete(40) tree.print() print("\n\nVi balanserar ...\n") tree.balanceBST() tree.print() print()
Ibland kan det vara önskvärt med ett självbalanserande binärt träd (AVL -träd), som håller sig själv balanserat s.a.s.
14.858961105347 ms