balanced binary trees

See also balanced binary trees in Delphi

Balanced binary trees are extremely efficient datastructures for searching data.
Finding an element in 65536 requires at most 16 compares.

//
//  Taken from Nicklaus Wirth :
//    Algorithmen und Datenstrukturen ( in Pascal )
//    Balanced Binary Trees p 250 ++
//
//   for Turbo Pascal
//   not usable as it is in Delphi !!
//
//
//
//
unit BTree;


interface

type
 ref=^node;
 node=record
  key:integer;  // the data associated with the node
  left,right:ref;
  bal:-1..1;
  count:byte;
 end;

implementation


procedure search(x:integer;var p:ref;var h:boolean);   // insert
 var p1,p2: