Wir definieren uns einen Binären Suchbaum als Klasse BST. Die Klasse arbeitet intern mit einer Repräsentation Node, welche die Knoten vom Baum repräsentiert. Der leere Baum wird durch das Symbol None
definiert.
Die grundlegenden Operationen einer Symboltabelle, size
, isEmpty
, put
, get
, contains
, keys
sind einfach zu definieren.
Um die Grösse effizient zu berechnen, speichern wir uns einen Knotenzähler
count
, welcher die Anzahl Knoten im jeweiligen Unterbaum speichert.
class BST:
class Node:
def __init__(self, key, value, count = 1):
self.key = key
self.value = value
self.count = count
self.left = None
self.right = None
def __init__(self):
self._root = None
def size(self):
return self._size(self._root)
def _size(self, root):
if (root == None):
return 0
else:
return root.count
def isEmpty(self):
return self.size() == 0
def contains(self, key):
return self.get != None
def get(self, key):
return self._get(key, self._root)
def _get(self, key, node):
if node == None:
return None
elif key < node.key:
return self._get(key, node.left)
elif key > node.key:
return self._get(key, node.right)
elif key == node.key:
return node.value
else:
raise Exception("should never reach this line")
def put(self, key, value):
self._root = self._put(key, value, self._root)
def _put(self, key, value, node):
if (node == None):
return BST.Node(key, value, 1)
elif key < node.key:
node.left = self._put(key, value, node.left)
elif key > node.key:
node.right = self._put(key, value, node.right)
elif key == node.key:
node.value = value
node.count = 1 + self._size(node.left) + self._size(node.right)
return node
def keys(self):
return self._keys(self._root, [])
def _keys(self, node, keylist):
if node == None:
return keylist
else:
self._keys(node.left, keylist)
keylist.append(node.key)
self._keys(node.right, keylist)
return keylist
def height(self):
return self._height(self._root)
def _height(self, node):
if node == None:
return 0
else:
return 1 + max(self._height(node.left), self._height(node.right))
Der folgende Code ist dient dazu, einen binärbaum mittels der Plotting-library bokeh zu visualisieren. Details vom Code sind für das Verständnis im Kurs nicht relevant.
from bokeh.plotting import figure, output_notebook, show
def plotTree(bst):
output_notebook()
p = figure(plot_width=400, plot_height=400)
height = bst.height()
def _plotTree(root, level=1, horizontalPos = 0):
def leftOffset(level):
return horizontalPos - 2 ** (height - level)
def rightOffset(level):
return horizontalPos + 2 ** (height - level)
if root == None:
return
else:
if root.left != None:
p.line([horizontalPos ,leftOffset(level)], [height - level, height - (level + 1)])
_plotTree(root.left, level + 1, leftOffset(level))
p.text([horizontalPos], [height - level], [str(root.key)])
if root.right != None:
p.line([horizontalPos , rightOffset(level)], [height - level, height - (level + 1)])
_plotTree(root.right, level + 1, rightOffset(level))
_plotTree(bst._root)
show(p)
Als erstes testen wir unser einfaches Symboltabellenbeispiel.
string = "SEARCHEXAMPLE"
bst = BST()
for (pos, char) in enumerate(string):
bst.put(char, pos)
Nach dem Einfügen sollte der Baum nun so viele verschiedene Knoten haben, wie es unterschiedliche Buchstaben im Wort "SEARCHEXAMPLE" gibt.
print("Anzahl Knoten im Baum: ", bst.size())
print("Anzahl verschiedene Buchstaben: ", len(set(string)))
Anzahl Knoten im Baum: 10 Anzahl verschiedene Buchstaben: 10
Es ist auch interessant, den Baum zu visualisieren.
Wie wir sehen, ist der Baum nicht vollständig, sondern hat die Höhe 5:
bst.height()
6
Mit der Methode keys
können wir alle Schlüssel erhalten, und mit get
den dazugehörigen Wert ausgeben.
for key in bst.keys():
print("key: " +key, " value: ", bst.get(key))
key: A value: 8 key: C value: 4 key: E value: 12 key: H value: 5 key: L value: 11 key: M value: 9 key: P value: 10 key: R value: 3 key: S value: 0 key: X value: 7
Als erstes betrachten wir, wie die Reihenfolge der Inputdaten den Baum verändert.
def plotBSTForInput(string):
bst = BST()
for (pos, char) in enumerate(string):
bst.put(char, pos)
plotTree(bst)
testdata = list("NGDBACFEKIHJMLURPOQTSXWVZY")
import random
for i in range(0, 4):
random.shuffle(testdata)
plotBSTForInput(testdata)
Es ist intuitiv klar, dass die Form des Baums einen grossen Einfluss auf die Laufzeitkomplexität der get
Methode hat. Im schlechtesten Fall degeneriert der Baum zu einer verketteten Liste, und die Komplexität ist $O(N)$. Im besten Fall ist der Baum vollständig, und die Komplexität ist $O(\log_2(N))$.
In der Praxis werden wir nicht oft den besten Fall, aber auch nicht den schlechtesten Fall sehen. Es ist deshalb interessant zu sehen, was die Laufzeit auf zufälligen Inputs ist. Ein wichtiger Indikator ist dabei die Höhe. Die Höhe vom Baum bestimmt die maximale Anzahl von Vergleichen die für die Suche eines Schlüssels benötigt werden.
Wir schauen uns nun die Höhe für verschiedene, zufällig generierte Binäre Suchbäume an. Dafür schreiben wir uns als erstes eine Methode um einen zufälligen Baum zu erstellen.
def randomlyFilledBST(num):
bst = BST()
keys = list(range(0, num))
random.shuffle(keys)
for key in keys:
bst.put(key, "value")
return bst
Als nächstes erstellen wir verschieden grosse Bäume und berechnen deren Höhe und plotten diese.
import numpy
Ns = [100, 1000, 5000, 10000, 20000, 50000, 100000]
numRuns = 5
heights = []
for N in Ns:
avgHeight = 0
for i in range(0, numRuns):
bst = randomlyFilledBST(num=N)
avgHeight += bst.height()
heights.append(avgHeight / numRuns)
p = figure()
p.line(Ns, heights, line_color="green", legend="Experiment")
p.line(Ns, 4.3 * numpy.log(Ns) , line_color="red", legend="Erwartungswert (analytisch)")
show(p)
<Bokeh Notebook handle for In[16]>
Wir sehen, dass die Höhe des Baums bei zufälligen Schlüsseln nur logarithmisch zunimmt. Das bedeutet auch, dass wir in einem Binären Suchbaum den Schlüssel im Durchschnittsfall nach einer logarithmischen Anzahl Vergleichen finden.
Falls ein Set von Schlüsseln keine doppelten Schlüssel hat, können wir einen binären Suchbaum zum Sortieren verwenden. Dies geschieht wie folgt:
teststring = list("PSEUDOMYTHICAL")
bst = BST()
for c in teststring:
bst.put(c, None)
for key in bst.keys():
print(key)
A C D E H I L M O P S T U Y
Das liegt daran, dass die keys
Methode den Baum inorder traversiert.
Wir schreiben uns diese inorder traversierung nochmals explizit auf.
def traverseInorder(node):
if node == None:
return []
else:
keysLeft = traverseInorder(node.left)
keysRight = traverseInorder(node.right)
return keysLeft + [node.key] + keysRight
traverseInorder(bst._root)
['A', 'C', 'D', 'E', 'H', 'I', 'L', 'M', 'O', 'P', 'S', 'T', 'U', 'Y']
Wir vergleichen nun dieses Sortierverfahren mit Quicksort, den wir hier nochmals (in einer einfachen Version) zeigen. Beachten Sie, dass diese Implementation nicht in-place ist, und dadurch etwas einfacher ist, als die im Kurs vorgestellten Version.
def quicksort(a):
if a == []:
return []
else:
l = quicksort([x for x in a if x < a[0]])
r = quicksort([x for x in a if x > a[0]])
return l + [a[0]] + r
quicksort(teststring)
['A', 'C', 'D', 'E', 'H', 'I', 'L', 'M', 'O', 'P', 'S', 'T', 'U', 'Y']
Wenn wir Quicksort mit der Inorder traversierung vergleichen, sehen wir, dass die Zwei Methoden genau dieselbe Struktur haben.
In der Tat gibt es für den Fall, dass keine duplizierten Schlüssel vorhanden sind eine 1:1 Korrespondenz zwischen Binären Suchbäumen und Quicksort. Der Unterschied hier ist, dass bei den Binären Suchbäumen die Partitionierung beim Einfügen passiert, während dies beim Quicksort im Algorithmus gemacht wird.
Noch etwas klarer wird dies, wenn wir uns den Baum anzeigen, und uns beim Quicksort das Pivot als erstes ausgeben (also preorder). Das Pivot Element entspricht immer der Wurzel eines Unterbaums. Diese Wurzel muss beim Einfügen mit jedem Schlüssel im Unterbaum einmal verglichen werden.
plotTree(bst)
def quicksort(a):
if a == []:
return []
else:
print(a[0])
l = quicksort([x for x in a if x < a[0]])
r = quicksort([x for x in a if x > a[0]])
return l + [a[0]] + r
print("Pivot von Quicksort")
quicksort(teststring)
Die Vergleiche mit dem Pivot Element sind also genau die Vergleiche, die auch beim Einfügen einen Baum gemacht werden.
Die Korrespondenz zu Quicksort können wir zum Beispiel dazu nutzen, um die Komplexität von BST im Durchschnittsfall abzuschätzen. Für Quicksort ist nämlich bekannt, dass es im Durchschnittsfall $1.39 N\log_2(N)$ Vergleiche benötigt werden um ein Array zu sortieren. Durch die Äquivalenz zum Einfügen in Binäre Suchbäume, können wir schliessen, dass das Einfügen für jedes Element in einem Baum der Grösse $N$ im Schnitt $1.39 \log_2(N)$ Vergleiche benötigt.
Als nächsten zeigen wir einfache Implementation der Ordnungsbasierten Operationen, insbesondere min
, floor
, rank
, und select
.
class BSTWithOrderedOps(BST):
def min(self):
return self._min(self._root).key
def _min(self, node):
if node.left == None:
return node
else:
return self._min(node.left)
def floor(self, key):
return self._floor(self._root, key).key
def _floor(self, node, key):
if node == None:
print("key: ",key, "node = None", " => Return None")
return None;
if key == node.key:
print("key: ", key, "node = ", node.key, " => Found")
return node
elif key < node.key:
print("key: ", key, "node = ", node.key, " => Go left")
return self._floor(node.left, key)
else:
print("key: ", key, "node = ", node.key, " => Go right")
t = self._floor(node.right, key)
if t != None:
print("floor in right subtree ", t.key)
return t
else:
print("no smaller node in right subtree")
return node
def select(self, k):
return self._select(self._root, k).key
def _select(self, node, k):
if node == None:
return None
t = self._size(node.left);
if t > k:
return self._select(node.left, k)
elif t < k:
return self._select(node.right, k - t - 1)
else:
return node;
def rank(self, key):
return self._rank(self._root, key)
def _rank(self, node, key):
if node == None:
return 0
if key < node.key:
return self._rank(node.left, key)
elif key > node.key:
return 1 + self._size(node.left) + self._rank(node.right, key)
else:
return self._size(node.left)
bst = BSTWithOrderedOps()
for key in list("SEARCHEXAMPLE"):
bst.put(key, "value")
#bst.floor("G")
bst.floor("W")
key: W node = S => Go right key: W node = X => Go left key: W node = None => Return None no smaller node in right subtree
'S'
print("min: ", bst.min())
print("floor of W: ", bst.floor("W"))
print("select 0: ", bst.select(0))
print("rank Q: ", bst.rank("Q"))
min: A key: W node = S => Go right key: W node = X => Go left key: W node = None => Return None no smaller node in right subtree floor of W: S select 0: A rank Q: 7
Als letztes Zeigen wir noch eine Implementation der Löschoperationen nach Hibbard.
class BSTWithDelete(BSTWithOrderedOps):
def deleteMin(self):
self._deleteMin(self._root)
def _deleteMin(self, node):
if node.left == None:
return node.right;
node.left = self._deleteMin(node.left);
node.size = self._size(node.left) + self._size(node.right) + 1;
return node;
def delete(self, key):
self._root = self._delete(self._root, key)
def _delete(self, node, key):
if node == None:
return None;
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key);
else: # key == node.key (zu löschender Knoten)
if node.right == None:
return node.left
if node.left == None:
return node.right
t = node;
node = self._min(t.right)
node.right = self._deleteMin(t.right)
node.left = t.left
node.size = self._size(node.left) + self._size(node.right) + 1;
return node
Der folgende Code demonstriert, wie ein anfänglich perfekter Baum degeneriert, wenn beliebige Schlüssel gelöscht werden.
import random
bst = BSTWithDelete()
for key in list("NGDBACFEKIHJMLURPOQTSXWVZY"):
bst.put(key, "value")
plotTree(bst)
keys = list(bst.keys())
random.shuffle(keys)
for key in keys[0:(len(keys)//2)]:
bst.delete(key)
plotTree(bst)