ein Suchbaum mit einer Optimalitätseigenschaft.

Um in einer gegebenen Menge von Objekten ein bestimmtes Objekt zu finden, verwendet man oft einen Suchbaum, also einen Baum, in dem die Menge der zu durchsuchenden Objekte entsprechend einer inhaltlich bedingten Gliederung auf die einzelnen Zweige des Baums aufgeteilt ist, sodaß man von der Wurzel her nach logischen Kriterien den Baum durchsuchen kann, bis das gewünschte Objekt gefunden ist.

In Fällen, in denen die Wahrscheinlichkeit des Zugriffs zu verschiedenen Objektschlüsseln bekannt ist, kann man angeben, welche Baumstruktur im Hinblick auf die Suche optimal ist. Hat der Suchbaum n Knoten mit den Nummern 1 bis n, so bezeichne p(i) die Wahrscheinlichkeit des Zugriffs auf den Knoten mit der Nummer i. Dann ist p(1) + p(2) + … + p(n) = 1. Ziel der Organisation des Suchbaums ist es, die Gesamtzahl der Suchschritte, gezählt über hinreichend viele Versuche, zu minimieren. Ist nun h(i) die um 1 erhöhte Distanz des Knotens mit der Nummer i von der Wurzel des Baums, so definiert man eine gewichtete Weglänge durch \begin{eqnarray}L=p(1)\cdot h(1)+p(2)\cdot h(2)+\cdots +p(n)\cdot h(n).\end{eqnarray}

Ein Suchbaum, der die gegebenen Objekte als Knoten enthält, heißt dann optimal, wenn seine gewichtete Weglänge unter allen möglichen Suchbäumen mit den gleichen Knoten minimal ist.