Class: BinaryTree

• Inheritance
• Description
• Class protocol
  • initialization
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • enumerating
  • queries
• Examples

Inheritance:

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

Package:

stx:libbasic2

Category:

Collections-Ordered-Trees

Version:

rev: 1.20 date: 2021/01/20 13:13:27

user: cg

file: BinaryTree.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

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

copyright
COPYRIGHT (c) 2003 by eXept Software AG
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

 initialize

setup the default sortBlock.
Use #<, since this is the base method in Magnitude.

Usage example(s):

BinaryTree initialize

 new

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

 new: n

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

 sortBlock: aTwoArgBlock

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

Usage example(s):

|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

Instance protocol:

 rootNode

return the rootNode of the tree

 sortBlock: something

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

 add: anObject

add anObject to the collection. The object is inserted as defined by the sortBlock.
Returns anObject

 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

 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

 remove: oldObject ifAbsent: exceptionValue

sigh - collection protocol

 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

 do: aBlock

enumerate the tree in order

Usage example(s):

|coll| coll:= OrderedCollection new. (BinaryTree withAll:#(5 4 3 2 1 6 7 8 9 0)) do:[:each| coll add:each]. coll

 postOrderDo: aBlock

enumerate in postOrder - Left, Right, Root

 preOrderDo: aBlock

enumerate in preOrder - Root, Left, Right

 isFixedSize

return true if the receiver cannot grow

 rootTreeNodeClass

 size

return the number of tree elements

 treeNodeClass

Examples:

  |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     

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