Class: AVLTree

• Inheritance
• Description
• Related information
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • enumeration
  • initialization
  • private
  • queries
  • searching
• Private classes

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:

 new

 withSortBlock: binaryBlock

Instance protocol:

 orderBlock: aBlock

 add: anObject

 remove: anObject

 do: unaryBlock

 reverseDo: unaryBlock

 initialize

 addNode: aNode

 removeNode: aNode

 depth

 isEmpty

 size

 find: anObject

 findNode: aNode

Private classes:

    AVLNil
    AVLTreeNode