TREAPS

[Evelyn Cristina Pinto <ecp@linux.ime.usp.br>]

Eu li o programa do Knuth Wordtest e nao consegui entender exatamente o
que uma Treap faz.

O que entendi foi que ele usa Heap para espalhar os dados e depois ABB
para buscar as palavras no arquivo dado, mas parece que de alguma forma o
programa monta as duas arvores ao mesmo tempo. Eh isso mesmo?

Procurei, entao na Internet algum material sobre isso. Estou deixando o
que encontrei aqui para todos os alunos verem, mas ainda nao ficou claro
como uma Treap funciona. Gostaria que alguem pudesse explicar melhor isso.

Pelo pouco que entendi ela tem um otimo desempenho em busca.

Professor, em que livro podemos encontrar alguma coisa?


Valeu turma!

 Evelyn Cristina Pinto   <ecp@linux.ime.usp.br>

The first part of this page is in German - please ignore it if you do not
understand it!

Idea behind Treaps
Implementation of Treaps
Implementation of the test driver
Results of the measurements

Die Idee von Treaps stammt von Aragon und Seidel (1989).
Das Ziel ist, die Balancierung von binären Suchbäumen mit möglichst geringem
Aufwand zur Verhinderung von Degeneration.
Hauptidee: Beim Einfügen von Elementen eine zufällige Priorität vergeben und
im binären Suchbaum durch Rotationen die Heapbedingung wieder herstellen.
Suchbedingung:
  Linker Teilbaum enthält alle Elemente, deren Schlüssel kleiner sind.
  Rechter Teilbaum enthält alle Elemente, deren Schlüssel größer sind.
Heapbedingung:
  Söhne haben (numerisch) größere Priorität.
Suchen: wie in normalen binären Suchbäumen.
Einfügen:
  Platz im Suchbaum suchen.
  Blatt für neuen Knoten anlegen und zufällige Priorität vergeben.
  Durch Rotationen (lokale Transformation, die die Suchbedingung nicht
invalidiert) die Heapbedingung wiederherstellen, indem das Element nach oben
wandert.
Entfernen:
  Element suchen.
  Einfaches Löschen, wenn es keinen linken oder rechten Sohn gibt.
  Ansonsten Element solange durch Rotationen nach unten schieben, bis ein
Sohn NIL geworden ist. Man muß dabei aufpassen, mit welchem Sohn man
rotiert, da dieser Sohn dann nach dem Löschen der Wurzel über dem anderen
Sohn liegt. Man muß deshalb den Sohn mit der (numerisch) kleineren Priorität
nehmen, da dieser dann über dem anderen Sohn landet, womit die Heapbedingung
erfüllt ist.

MODULE Treaps; (* CS, 2 Jul 97 *)
(* Heuristically balanced search trees:
- C.R.Aragon, R.Seidel: Randomized Search Trees. Algorithmica,
16(4/5):464-497, 1996
- S. Nilsson: Treaps in Java. Dr.Dobbs Journal, July 1997, 40 - 44.
*)
IMPORT Out;

TYPE
  Node* = POINTER TO NodeDesc;
  NodeDesc* = RECORD
    prio: INTEGER;  (* node with smaller priority is higher up the tree *)
    val: INTEGER;
    left, right: Node
  END;

VAR
  seed: LONGINT;
costs: LONGINT;

PROCEDURE Random(): INTEGER;
BEGIN
  seed := (seed * 27181 + 13849) MOD 65536;
  RETURN SHORT(seed)
END Random;

PROCEDURE Search* (node: Node; val: INTEGER): Node;
BEGIN
  IF (node = NIL) OR (node.val = val) THEN RETURN node
  ELSIF val < node.val THEN RETURN Search(node.left, val)
  ELSE RETURN Search(node.right, val)
  END
END Search;

PROCEDURE Insert* (VAR root: Node; val: INTEGER);
  VAR p: Node;
BEGIN
  IF root = NIL THEN
    NEW(root); root.val := val; root.prio := Random()
  ELSIF val < root.val THEN
    Insert(root.left, val);
    IF root.prio > root.left.prio THEN p := root.left; root.left := p.right;
p.right := root; root := p END
  ELSE
    Insert(root.right, val);
    IF root.prio > root.right.prio THEN p := root.right; root.right :=
p.left; p.left := root; root := p END
  END
END Insert;

PROCEDURE Delete* (VAR root: Node; val: INTEGER);
  VAR p: Node;
BEGIN
  IF root # NIL THEN
    IF val = root.val THEN
      IF root.left = NIL THEN root := root.right; RETURN
      ELSIF root.right = NIL THEN root := root.left; RETURN
      ELSIF root.left.prio < root.right.prio THEN p := root.left; root.left
:= p.right; p.right := root; root := p
        (* left subtree has (numerically) smaller priority, i.e. it must be
above the right subtree in
          the resulting tree. Rotating the left subtree results in moving
the left node up, the right
          node will be located under the left one, priority is maintained
correctly. Otherwise rotate
          the right subtree so that the right node will be located above the
left node. *)
      ELSE p := root.right; root.right := p.left; p.left := root; root := p
      END
    END;
    IF val < root.val THEN Delete(root.left, val) ELSE Delete(root.right,
val) END
  END
END Delete;

PROCEDURE Dump* (root: Node; indent: INTEGER);
  VAR i: INTEGER;
BEGIN
  FOR i := 1 TO indent DO Out.String(" ") END;
  IF root = NIL THEN Out.Char("-"); Out.Ln
  ELSE
    Out.Int(root.val, 0); Out.Ln;
    Dump(root.left, indent + 1);
    Dump(root.right, indent + 1)
  END
END Dump;

PROCEDURE Costs* (root: Node);
  VAR nofNodes: INTEGER;

  PROCEDURE Search (node: Node; val: INTEGER; VAR height: INTEGER): Node;
  BEGIN
    IF (node = NIL) OR (node.val = val) THEN RETURN node
    ELSIF val < node.val THEN INC(height); RETURN Search(node.left, val,
height)
    ELSE INC(height); RETURN Search(node.right, val, height)
    END
  END Search;

  PROCEDURE Traverse (node: Node);
    VAR height: INTEGER;
  BEGIN
    IF node # NIL THEN
      Traverse(node.left);
      Traverse(node.right);
      INC(nofNodes);
      height := 0;
      IF Search(root, node.val, height) # NIL THEN INC(costs, LONG(height))
      ELSE HALT(66)
      END
    END
  END Traverse;

BEGIN
  costs := 0; nofNodes := 0;
  Traverse(root);
  Out.Ln; Out.String("Costs for searching "); Out.Int(nofNodes, 0);
Out.String(": "); Out.Int(costs, 0)
END Costs;

BEGIN
  seed := 20015
END Treaps.

MODULE test;  (** CS, 2 Jul 97 **)
IMPORT Treaps, In, Out;

VAR
  tree: Treaps.Node;

PROCEDURE Insert*;
  VAR val: INTEGER;
BEGIN
  In.Open;
  REPEAT
    In.Int(val);
    Treaps.Insert(tree, val)
  UNTIL ~In.Done;
  Treaps.Dump(tree, 0)
END Insert;

PROCEDURE InsertMany*;
  VAR no: INTEGER;
BEGIN
  In.Open; In.Int(no);
  IF In.Done THEN
    WHILE no > 0 DO
      Treaps.Insert(tree, no);
      DEC(no)
    END
  END
END InsertMany;

PROCEDURE DeleteMany*;
  VAR from, to: INTEGER;
BEGIN
  In.Open; In.Int(from); In.Int(to);
  IF In.Done THEN
    FOR from := from TO to DO Treaps.Delete(tree, from) END
  END
END DeleteMany;

PROCEDURE Delete*;
  VAR val: INTEGER;
BEGIN
  In.Open; In.Int(val);
  Treaps.Delete(tree, val);
  Treaps.Dump(tree, 0)
END Delete;

PROCEDURE Costs*;
BEGIN Treaps.Costs(tree)
END Costs;

BEGIN
  tree := NIL
END test.

The results of the measurements:

test.Insert ^  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
test.InsertMany ^  100  400
test.DeleteMany ^  10 50  250 350
test.Delete ^
test.Costs

Batch.Start
test.InsertMany 100
test.Costs
test.DeleteMany 10 50
test.Costs
~
Costs for searching 100: 568  N * log N = 664
Costs for searching 59: 290  N * log N = 346

Batch.Start
test.InsertMany 400
test.Costs
test.DeleteMany 250 350
test.Costs
~
Costs for searching 400: 3648  N * log N = 3455
Costs for searching 299: 2638  N * log N = 2457