Mich interessieren insbesondere Algorithmen, die adaptiv reagieren, d. h. sich den Anforderungen anpassen können. Hierzu zählen nicht nur Neuronale Netze sondern auch die Verarbeitung von Datenmengen, zu denen auch der Splay Tree gehört.
Ich freue mich z. B., wenn ich bei meinem Navigationssystem bei meiner Suche nach einer Stadt nach der Eingabe eines „D“ bereits die letzten von mir getätigten Eingaben wieder vorgelegt bekomme, da die Wahrscheinlichkeit, dass ich noch mal in diese Stadt fahren möchte, relativ hoch ist.
Bei einem Suchalgorithmus ist es natürlich schön, wenn ein Suchbegriff in einer definierten Zeit gefunden wird, noch schöner ist es aber, wenn Suchbegriffe, die häufig gesucht werden, schneller gefunden werden. Auf dieser Idee basiert der Splay Tree. Jede Suche und jedes Einfügen von Werten führen dazu, dass diese Werte an die Spitze eines Binären Baumes „gespült“ werden.
Dabei ist die Grundidee, dass ein gefundener Knoten mit Hilfe von Rotationen an die Spitze bewegt wird. Eine einfache Rotation sieht z. B. so aus:
Rotation
Damit das Ganze noch performanter erfolgen kann, gibt es auch Doppelrotationen. Sehr leicht lassen sich diese mit Hilfe von Zeigern auf den Elternknoten im Binären Baum realisieren. Dadurch würde aber der Speicherverbrauch je Knoten um 50% steigen (neben den Zeigern für das linke und rechte Kind dann auch noch den auf den Elternknoten). Um das zu vermeiden wurde der Algorithmus zum sogenannten Splay Tree Top-Down erweitert, den ich hier in einer Scala-Implementierung zeigen möchte.
Zuerst habe ich einen Binären Baum realisiert. Obwohl das in Java eine leichte Übung ist, ging es mir hier darum, nicht mit null-Pointern als Darstellung der Blätter zu arbeiten sondern mit einem eigenen Objekt. Das ist typsicher und vermeidet NullPointerExceptions.
sealed abstract class Tree[+A] {
def rotateRight(): Tree[A]
def rotateLeft(): Tree[A]
def size: Int
def height: Int
}
case object Empty extends Tree[Nothing] {
override def rotateRight() = Empty
override def rotateLeft() = Empty
override def size = 0
override def height = 0
}
case class Node[A]( val key: A, var left: Tree[A] = Empty, var right: Tree[A] = Empty )
extends Tree[A] {
override def rotateRight(): Node[A] = left match {
case oldLeft: Node[A] =>
left = oldLeft.right
oldLeft.right = this
oldLeft
case Empty => this
}
override def rotateLeft(): Node[A] = right match {
case oldRight: Node[A] =>
right = oldRight.left
oldRight.left = this
oldRight
case Empty => this
}
override def size = left.size + right.size + 1
override def height = Math.max(left.height, right.height) + 1
}
Einige der für den Splay Tree benötigten Operationen wie die einfache Rotation sind bereits implementiert. Eine solche Operation kann jedoch nur ausgeführt werden, wenn die entsprechenden Knoten auch vorhanden (also keine Blätter / Empty-Knoten) sind. Diese Abfragen wurden hier bereits mit Hilfe von match-Anweisungen eingebaut.
Der Code für den eigentlichen Splay Tree ist deutlich komplexer. Es ging mir auch darum, die Datenstruktur als Set aufzubauen, so dass sie wie andere Scala-Datenstrukturen zu verwenden ist und auch von den zugehörigen Traits profitiert.
Interessant finde ich die Möglichkeit durch Verwendung von Funktionen in Funktionen die eigentlich notwendigen Kommentare durch aussagekräftige Methodennamen zu ersetzen bzw. auf das Notwendige zu reduzieren.
class SplayTree[A <% Ordered[A]] extends Set[A] {
private[this] var root: Tree[A] = Empty
override def contains( key: A ): Boolean = {
root = splay( key, root )
root match {
case Empty => false
case node: Node[A] => key == node.key
}
}
override def iterator: Iterator[A] = new SplayTreeIterator[A]( root )
override def +( key: A ): this.type = add( key )
override def +=( key: A ): this.type = add( key )
override def -( key: A ): this.type = { delete( key ); this }
override def -=( key: A ): this.type = { delete( key ); this }
override def empty: SplayTree[A] = new SplayTree[A]
override def foreach[U]( f: ( A ) => U ): Unit = {
def foreach( topNode: Tree[A] ): Unit = {
topNode match {
case Empty => // do nothing
case Node( key, left, right ) =>
foreach( left )
f( key )
foreach( right )
}
}
foreach( root )
}
override def size: Int = root.size
private[this] def add( aKey: A ): this.type = {
def addLeftAboveRoot( rootNode: Node[A] ) = {
val node = Node( aKey, rootNode.left, rootNode )
rootNode.left = Empty
node
}
def addRightAboveRoot( rootNode: Node[A] ) = {
val node = Node( aKey, rootNode, rootNode.right )
rootNode.right = Empty
node
}
root = root match {
case Empty => Node( aKey, Empty, Empty )
case _ =>
splay( aKey, root ) match {
case Empty => Empty
case rootNode: Node[A] =>
aKey.compareTo( rootNode.key ) match {
case cmp if cmp < 0 => addLeftAboveRoot( rootNode )
case cmp if cmp > 0 => addRightAboveRoot( rootNode )
case _ => rootNode
}
}
}
this
}
private[this] def delete( key: A ) {
// If key is in the tree it will be at the root
root = splay( key, root )
root match {
case Empty => // empty tree
case topNode: Node[A] =>
// key is in the tree
if ( key == topNode.key ) {
root = topNode.left match {
case Empty => topNode.right
case topNodeLeft: Node[A] =>
// Finde das Maximum im linken Teilbaum mit dem rekursiven
// Aufruf von splay. Daran wird das rechte Kind gehängt.
val rightNode = topNode.right
splay( key, topNodeLeft ) match {
case Empty => topNodeLeft
case newRoot: Node[A] =>
newRoot.right = rightNode
newRoot
}
}
}
}
}
private[this] def splay( key: A, tree: Tree[A] ): Tree[A] = {
tree match {
case Empty => Empty
case node: Node[A] =>
key.compareTo( node.key ) match {
case cmp if cmp < 0 => splayLeftTree( key, node )
case cmp if cmp > 0 => splayRightTree( key, node )
case _ => node
}
}
}
private[this] def splayLeftTree( key: A, node: Node[A] ): Node[A] = {
def handleLeftNode( leftNode: Node[A] ): Node[A] = key.compareTo( leftNode.key ) match {
case cmp if cmp < 0 =>
leftNode.left = splay( key, leftNode.left )
node.rotateRight()
case cmp if cmp > 0 =>
leftNode.right = splay( key, leftNode.right )
node.left = leftNode.rotateLeft()
node
case _ => node
}
node.left match {
case Empty => node
case leftNode: Node[A] =>
val newNode = handleLeftNode( leftNode )
newNode.rotateRight()
}
}
private[this] def splayRightTree( key: A, node: Node[A] ): Node[A] = {
def handleRightNode( rightNode: Node[A] ): Node[A] = key.compareTo( rightNode.key ) match {
case cmp if cmp > 0 =>
rightNode.right = splay( key, rightNode.right )
node.rotateLeft()
case cmp if cmp < 0 =>
rightNode.left = splay( key, rightNode.left )
node.right = rightNode.rotateRight
node
case _ => node
}
node.right match {
case Empty => node // key not in tree: done!
case rightNode: Node[A] =>
val newNode = handleRightNode( rightNode )
newNode.rotateLeft()
}
}
private class SplayTreeIterator[A]( root: Tree[A] )
extends Iterator[A] {
private val iterationStack = new Stack[A]
override def hasNext: Boolean = !iterationStack.isEmpty
override def next(): A = iterationStack.pop
def add( node: Tree[A] ): Unit = node match {
case innerNode: Node[A] =>
add( innerNode.left )
iterationStack.push( innerNode.key )
add( innerNode.right )
case _ => // do nothing
}
add( root )
}
}