TreeIndex

Trees can be indexed by the following scheme: The root has index 0, and if i is the index of some subtree, the left child of the subtree has index 2i+1, the right child has index 2i+2.

Signature of TreeIndex

List of Import References :
See BOOL
See DENOTATION
See Nat
See Option
See Seq
See Tree

SIGNATURE TreeIndex[data]

$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)

IMPORT Tree[data] ONLY tree
       Nat ONLY nat
       Option[data] ONLY option
       Option[tree] ONLY option

Parameter

SORT data

Handling Indices

Functions for handling indices are located in the structure IndexingOfTrees.

If the index points to root, nothing happens. Otherwise, returns the left or right subtree according to index, and adjusts the index by unleft or unright.

FUN step: tree ** nat -> tree ** nat

Accessing Values by Indices

! returns the value of the subtree with the given index, which must exist. !? returns nil, if the index does not exist.

FUN ! : tree ** nat -> data
FUN !? : tree ** nat -> option[data]

upd replace the value at the given index (which must exist) either by the given data or by result of applying the function to the old value.

FUN upd: nat ** data ** tree -> tree
FUN upd: nat ** (data -> data) ** tree -> tree

Accessing Trees by Indices

These functions return the subtrees instead of the values of the subtrees

FUN ! : tree ** nat -> tree
FUN !? : tree ** nat -> option[tree]

repl(t,idx,new) replaces the subtree at index idx with the new tree. insert does the same, but aborts if the index does not point to an empty tree. delete replaces the subtree by an empty tree. All functions abort, if the index does not exist.

repl(t, idx, fct) replaces the subtree at position idx with f(idx).

FUN repl: tree ** nat ** tree -> tree
FUN repl: tree ** nat ** (tree -> tree) -> tree
FUN insert: tree ** nat ** tree -> tree
FUN delete: tree ** nat -> tree

next node: TreeMap,
prev node: TreeFilter,
up to node: Subsystem Binary Trees