Skip to content
This repository was archived by the owner on Feb 24, 2025. It is now read-only.

TAvlTree

Jump to bottom
Ivan Semenkov edited this page Oct 9, 2021 · 4 revisions

Table of contents

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;
Clone this wiki locally