eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'AVLTree':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: AVLTree


Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--AVLTree

Package:
stx:libbasic2
Category:
Collections-Ordered-Trees
Version:
rev: 1.6 date: 2017/01/20 12:36:09
user: cg
file: AVLTree.st directory: libbasic2
module: stx stc-classLibrary: libbasic2

Description:


AVLTree -- balanced trees.

This implements another kind of self-balancing tree, named after their inventors,
AVLTree is obsoleted by AATree, which has the same best/worst/average characteristics 
(it is also self-balancing), but is always faster (roughly by a factor of 1.5 to 2).

Consider using an AATree instead.
(unless a special situation arises, of which we don't know yet)


Examples:

|t|

t := AVLTree new.
self assert:(t depth == 0).
self assert:(t size == 0).
self assert:(t isEmpty).

t add:'hello'.
self assert:(t depth == 0).
self assert:(t size == 1).
self assert:(t notEmpty).

t add:'world'.
self assert:(t depth == 1).
self assert:(t size == 2).

t add:'aaa'.
self assert:(t depth == 1).
self assert:(t size == 3).

t add:'bbb'.
self assert:(t depth == 2).
self assert:(t size == 4).

self assert:(t printString = 'AVLTree(aaa bbb hello world)').

t remove:'aaa'.
self assert:(t printString = 'AVLTree(bbb hello world)').
self assert:(t depth == 1).
self assert:(t size == 3).

| words tree |
words := #( Peter Piper picked a peck of pickled peppers
            A peck of pickled peppers Peter Piper picked
            If Peter Piper picked a peck of pickled peppers
            Where is the peck of pickled peppers Peter Piper picked? ).
tree := AVLTree new.
tree addAll: words.
tree printOn:Transcript. Transcript cr; cr.
tree := AVLTree withSortBlock: [:a :b | b < a].
tree addAll: words.
tree printOn:Transcript. Transcript cr; cr.


Related information:

    AATree
    BTree
    SortedCollection
    [ttps]

Class protocol:

instance creation
o  new

o  withSortBlock: binaryBlock


Instance protocol:

accessing
o  orderBlock: aBlock

adding & removing
o  add: anObject

o  remove: anObject

enumeration
o  do: unaryBlock

o  reverseDo: unaryBlock

initialization
o  initialize

private
o  addNode: aNode

o  removeNode: aNode

queries
o  depth

o  isEmpty

o  size

searching
o  find: anObject

o  findNode: aNode


Private classes:

    AVLNil
    AVLTreeNode


ST/X 7.2.0.0; WebServer 1.670 at bd0aa1f87cdd.unknown:8081; Tue, 31 Jan 2023 20:46:54 GMT