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.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:

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

o  withSortBlock: binaryBlock


Instance protocol:

accessing
o  orderBlock: aBlock

adding & removing
o  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).

o  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.

enumeration
o  do: unaryBlock
(comment from inherited method)
evaluate the argument, aBlock for every element in the collection in
sequence order.

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

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

private
o  addNode: aNode

o  removeNode: aNode

queries
o  depth

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

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

searching
o  find: anObject

o  findNode: aNode


Private classes:

    AVLNil
    AVLTreeNode


ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Sat, 15 Jun 2024 06:36:37 GMT