BSTreeIndex

Balanced search trees are indexed by the same scheme as trees. Functions which process the indices only are imported and reexported from TreeIndex.

Signature of BSTreeIndex

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

SIGNATURE BSTreeIndex[data, <]

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

IMPORT BSTree[data, <] ONLY bstree[data, <]
       Nat ONLY nat
       Option[data] ONLY option
       Option[bstree] ONLY option

Parameter

SORT data
FUN < : data ** data -> bool

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: bstree ** nat -> bstree ** 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 ! : bstree ** nat -> data
FUN !? : bstree ** 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 ** bstree -> bstree
FUN upd: nat ** (data -> data) ** bstree -> bstree

Accessing balanced search trees by Indices

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

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

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 or the result violates the bs condition.

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

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

next node: BSTreeReduce,
prev node: BSTreeFilter,
up to node: Subsystem Balanced Search Trees