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:

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