eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'BinaryTree':

Home

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

Class: BinaryTree


Inheritance:

   Object
   |
   +--Collection
      |
      +--BinaryTree
         |
         +--AATree

Package:
stx:libbasic2
Category:
Collections-Ordered-Trees
Version:
rev: 1.19 date: 2016/10/13 10:28:26
user: cg
file: BinaryTree.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
Steve Chepurny (original BinaryTreeNode implementation)
Claus Gittinger (cg@alan)

Description:


Loosely based on the Public Domain BinaryTreeNode class from Steve Chepurny.

WARNING:
    This tree does not reorganize itself. 
    Thus, its performance might degenerate to that of a linked list (see performance) when elements
    are added in 'already sorted' or reverse order.
    The performance is OK, if elements are added in random order and the tree is therefore more or less
    balanced.
    The worst case is to add elements in order, reverseOrder or zig-zag order.
    Use instances of my subclasses, which balance the tree if in doubt.

EXTRA WARNING:
    the inherited storeString will generate the elements in sorted order,
    which generates exactly the generated worst case when read-back.
    If you use this class and need textual persistency, you should consider rewriting
    the storeOn: method, to enumerate elements in a binary segmentation fashion.
    Otherwise, please use one of the self-balancing trees instead,
    for example AATree or BTree.
    
Changes:
    Changed to be Collection-protocol compatible.
    Slight speedup in insert-code.


[instance variables:]

[class variables:]


Related information:



Class protocol:

initialization
o  initialize
setup the default sortBlock.
Use #<, since this is the base method in Magnitude.
usage example(s):
     BinaryTree initialize

instance creation
o  new
return a new instance using the default sortOrder (which is a < b)

o  new: n
return a new instance using the default sortOrder (which is a < b)

o  sortBlock: aTwoArgBlock
return a new instance using the given sortBlock (which returns true if a < b)


Instance protocol:

accessing
o  rootNode
return the rootNode of the tree

o  sortBlock: something
set the sort block.
This is allowed only before any elements are stored in the tree

adding & removing
o  add: anObject
add anObject to the collection. The object is inserted as defined by the sortBlock.
Returns anObject

o  includes: anElement
return true, if the argument, anObject is contained in the collection.
Uses #= when comparing; i.e. the search is for an equal object.
usage example(s):
     BinaryTree new 
        addAll:#( 2 1 4.0 3 6 5 7); 
        includes:4           
usage example(s):
     BinaryTree new 
        addAll:#( 2 1 4.0 3 6 5 7); 
        includes:4.0           

o  includesIdentical: anElement
return true, if the argument, anObject is contained in the collection.
Uses #== (instead of #=) when comparing;
i.e. the search is for the object itself, not some object being just equal.
usage example(s):
     BinaryTree new 
        addAll:#(4 2 1 4.0 3 6 5 7); 
        includesIdentical:4           
usage example(s):
     BinaryTree new 
        addAll:#( 2 1 4.0 3 6 5 7); 
        includesIdentical:4           
usage example(s):
     BinaryTree new 
        addAll:#(4 2 1 3 6 5 7); 
        includesIdentical:8

o  remove: oldObject ifAbsent: exceptionValue
sigh - collection protocol

o  removeIdentical: oldObject ifAbsent: exceptionValue
sigh - collection protocol
usage example(s):
     BinaryTree new 
        addAll:#(4 2 1 3 6 5 7); 
        removeIdentical:4;
        yourself   
usage example(s):
     BinaryTree new 
        addAll:#(4 2 1 3 6 5 7); 
        removeIdentical:7;
        yourself      

enumerating
o  do: aBlock
enumerate the tree in order

o  postOrderDo: aBlock
enumerate in postOrder - Left, Right, Root

o  preOrderDo: aBlock
enumerate in preOrder - Root, Left, Right

queries
o  isFixedSize
return true if the receiver cannot grow

o  rootTreeNodeClass

o  size
return the number of tree elements

o  treeNodeClass


Examples:


a degenerated tree:
  |coll|

  coll := BinaryTree new.
  (1 to:10) do:[:i | coll add:i].
  coll addAll:(20 to:30).
  coll inspect   
  |tree|

  tree := self new.
  tree add:'hello'.
  tree add:'aaaa'.
  tree add:'AAAb'.
  tree add:'aaaC'.
  tree add:'world'.
  tree asOrderedCollection     
  |tree|

  tree := self sortBlock:[:a :b | a asLowercase < b asLowercase].
  tree add:'hello'.
  tree add:'aaaa'.
  tree add:'AAAb'.
  tree add:'aaaC'.
  tree add:'world'.
  tree asOrderedCollection     
timing examples and benchmarks: see examples in AATree: A functional example of a UCB-CS61A lecture's example. The task is to extract all values within a given range (min..max) from a binary tree. The range 'function' below does this; given a binary tree, a min and max value, range(bst, min, max) returns an array of all values which are within that range. Only the relevant branches of the binary tree are to be visited, of course.
  |t rangeNode range|

  t := BinaryTree new.
  t add:54; add:37; add:19; add:45; add:80; add:65; add:91; add:57.

  rangeNode := [:node :min :max |
              |nodeValue leftTree rightTree left right middle|

              leftTree := node leftSubtree.
              rightTree := node rightSubtree.
              nodeValue := node data.

              left := (leftTree notNil and:[nodeValue > min]) 
                          ifTrue:[ rangeNode value:leftTree value:min value:max ]
                          ifFalse:[ #() ].

              right := (rightTree notNil and:[nodeValue < max]) 
                          ifTrue:[ rangeNode value:rightTree value:min value:max ]
                          ifFalse:[ #() ].

              middle := (nodeValue between:min and:max)
                          ifTrue:[ (Array with:nodeValue) ]    
                          ifFalse:[ #() ].

              left, middle, right
      ].
  range := [:tree :min :max |
              rangeNode value:tree rootNode value:min value:max
      ].
  range value:t value:30 value:60.                


ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Wed, 19 Sep 2018 03:40:50 GMT