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)
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
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()
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()
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()
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()