Class: AVLTree

• Inheritance
• Description
• 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.11 date: 2023/05/29 15:54:29

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,
Adelson-Velsky and Landis.
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.

copyright
Copyright (c) 2005 Ian Piumarta
All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the 'Software'),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, provided that the above copyright notice(s) and this
permission notice appear in all copies of the Software and that both the
above copyright notice(s) and this permission notice appear in supporting
documentation.

THE SOFTWARE IS PROVIDED 'AS IS'.  USE ENTIRELY AT YOUR OWN RISK.

Last edited: 2007-01-25 03:17:27 by piumarta on emilia.local

performance
Time to insert random 1000000 into SortedCollection: 840ms
Time to insert random 1000000 into BinaryTree: 2040ms
Time to insert random 1000000 into AATree: 3060ms
Time to insert random 1000000 into AVLTree: 3780ms

Time to insert ordered 1000000 into SortedCollection: 30ms
Time to insert ordered 1000000 into BinaryTree: 72200ms
Time to insert ordered 1000000 into AATree: 110ms
Time to insert ordered 1000000 into AVLTree: 180ms

Time to insert reverse ordered 1000000 into SortedCollection: 30ms
Time to insert reverse ordered 1000000 into BinaryTree: 73880ms
Time to insert reverse ordered 1000000 into AATree: 80ms
Time to insert reverse ordered 1000000 into AVLTree: 160ms

Class protocol:

 new

(comment from inherited method)
return an instance of myself without indexed variables

 withSortBlock: binaryBlock

Instance protocol:

 orderBlock: aBlock

 add: anObject

(comment from inherited method)
append the argument, anObject to the collection.
Return the argument, anObject.

Notice that this modifies the receiver, NOT a copy.
Also note that it may be a slow operation for some collections,
due to the grow:-message, which is inefficient for fixed size
collections (i.e. for Strings and Arrays it is not recommended).

 remove: anObject

(comment from inherited method)
search for the first element, which is equal to anObject;
if found, remove and return it.
If not found, report a 'value not found'-error.
Uses equality compare (=) to search for the occurrence.

 do: unaryBlock

(comment from inherited method)
evaluate the argument, aBlock for every element in the collection in
sequence order.

 reverseDo: unaryBlock

(comment from inherited method)
evaluate the argument, aBlock for every element in the collection
in reverse order

 initialize

(comment from inherited method)
just to ignore initialize to objects which do not need it

 addNode: aNode

 removeNode: aNode

 depth

 isEmpty

(comment from inherited method)
return true, if the receiver is empty

 size

(comment from inherited method)
return the number of elements in the collection.
concrete implementations must define this

 find: anObject

 findNode: aNode

Private classes:

    AVLNil
    AVLTreeNode