TAvlTree

Table of contents

• About
• TOptionalValue
• Create
• Insert
• Remove
• Search
  • Search
  • SearchDefault
• NumEntries
• IsEmpty
• Iterate
  • FirstEntry
  • TIterator
    • HasValue
    • Prev
    • Next
    • Key
    • Value

About

The TAvlTree structure is a balanced binary tree which stores a collection of nodes. Each node has a key and a value associated with it. The nodes are sorted within the tree based on the order of their keys. Modifications to the tree are constructed such that the tree remains balanced at all times (there are always roughly equal numbers of nodes on either side of the tree). Balanced binary trees have several uses. They can be used as a mapping (searching for a value based on its key), or as a set of keys which is always ordered.

uses
  container.avltree, utils.functor;
  
type
  generic TAvlTree<K, V, KeyBinaryCompareFunctor> = class

KeyBinaryCompareFunctor is based on utils.functor.TBinaryFunctor interface and used to compare two keys.

TOptionalValue

If macro {$USE_OPTIONAL} is defined, then all methods return a TOptionalValue wrapper, otherwise V.

uses
  utils.optional;

type
  TOptionalValue = {$IFDEF FPC}specialize{$ENDIF} TOptional<V>;

For non-existent values, returns a empty TOptionalValue if defined or an EKeyNotExistsException is thrown.

type
  {$IFNDEF USE_OPTIONAL}
  EKeyNotExistsException = class(Exception);
  {$ENDIF}

Create

A new AVL tree can be created by call its constructor.

constructor Create;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  
  FreeAndNil(tree);
end;

Insert

Insert a new key-value pair into an AVL tree.

procedure Insert (Key : K; Value : V);

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  tree.Insert(1, 'one');
  
  FreeAndNil(tree);
end;

Remove

Remove an entry from a tree, specifying the key of the node to remove. Return false if no node with the specified key was found in the tree, true if a node with the specified key was removed.

function Remove (Key : K) : Boolean;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  tree.Remove(1);
  
  FreeAndNil(tree);
end;

Search

Search

Search an AVL tree for a value corresponding to a particular key. This uses the tree as a mapping.

function Search (Key : K) : {$IFNDEF USE_OPTIONAL}V{$ELSE}TOptionalValue{$ENDIF};

If value not exists returns empty TOptionalValue or raise EKeyNotExistsException.

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  tree.Search(1);
  
  FreeAndNil(tree);
end;

SearchDefault

Search an AVL tree for a value corresponding to a particular key. Return default value if key not exists.

function SearchDefault (Key : K; ADefault : V) : V;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  writeln(tree.SearchDefault(1, 'none'));
  
  FreeAndNil(tree);
end;

NumEntries

Retrieve the number of entries in the tree.

function NumEntries : Cardinal;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  writeln(tree.NumEnries);
  
  FreeAndNil(tree);
end;

IsEmpty

Return true if container is empty.

function IsEmpty : Boolean;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  
begin
  tree := TIntStrAvlTree.Create;
  if tree.IsEmpty then
    ;
  
  FreeAndNil(tree);
end;

Iterate

It is possible to iterate for TAvlTree values using in operator. Each value would present as TAvlTree.TIterator object.

uses
  container.avltree, utils.functor;
  
type
  generic TAvlTree<K, V, KeyBinaryCompareFunctor> = class
  type
  	TIterator = class({$IFDEF FPC}specialize{$ENDIF}
        TBidirectionalIterator<TAvlKeyValuePair, TIterator>)
  end;

TBidirectionalIterator is a abstract class which provide interface for iterable object that can moves to both sides.

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  pair : TIntStrAvlTree.TAvlKeyValuePair;
  
begin
  tree := TIntStrAvlTree.Create;
  for pair in tree do
    ;
  
  FreeAndNil(tree);
end;

FirstEntry

Retrive the iterator for first entry in a AVL tree.

function FirstEntry : TIterator

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  iterator := tree.FirstEntry;
  
  FreeAndNil(tree);
end;

TIterator

HasValue

Return true if iterator has correct value.

function HasValue : Boolean;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  
  iterator := tree.FirstEntry;
  while iterator.HasValue do
  begin
  
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(tree);
end;

Prev

Retrieve the iterator for previous entry in an array list.

function Prev : TIterator;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  
  iterator := tree.FirstEntry;
  while iterator.HasValue do
  begin
  
  	iterator := iterator.Next;
  end;
  iterator := iterator.Prev;
  
  FreeAndNil(tree);
end;

Next

Retrieve the iterator for next entry in an array list.

function Next : TIterator;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  
  iterator := tree.FirstEntry;
  while iterator.HasValue do
  begin
  
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(tree);
end;

Key

Return key value.

property Key : K;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  
  iterator := tree.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Key);
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(tree);
end;

Value

Return value.

property Value : V;

Example

uses
  container.avltree, utils.functor;
  
type
  TIntStrAvlTree = {$IFDEF FPC}type specialize{$ENDIF} TAVlTree<Integer, String, TCompareFunctorInteger>;

var
  tree : TIntStrAvlTree;
  iterator : TIntStrAvlTree.TIterator;
  
begin
  tree := TIntStrAvlTree.Create;
  
  iterator := tree.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Value);
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(tree);
end;