pine.BinTree: Functions Types Modinfo Source  

Data structures/Binary search trees

A binary tree has the advantages of being organized on-the-fly, efficient removal and insertion of objects, and, under ideal conditions, an extremely efficient retrieval of objects. Every object is associated with some string key, and the tree is sorted and objects are found using them.

To create a binary tree, use the CreateTree command. Its optional argument, which defaults to true, decides whether the tree is a regular old binary tree, or a splayed tree. Splayed trees require more overhead for insert and find operations, but are much more efficient for many applications.

Add objects to a binary tree using TreeInsert, and remove them using TreeRemove. You can efficiently find an object in a tree using TreeFind and TreeFindAll.

To visit all the objects in a binary tree in alphabetical order of their keys, you can use an EachIn loop.

Functions Summary

BinNodeContents Gets node contents as a TList.
BinNodeKey Gets node key.
BinNodeString Gets node contents as a list of comma separated values.
BinNodeValue Gets node value.
ClearTree Clear all contents of a tree.
CopyTree Copy a tree.
CountTree Count the number of values in a tree.
CountTreeNodes Count the number of nodes in a tree.
CreateTree Create a new tree.
OptimizeTree Optimize the tree so that it is as close to balanced as possible.
TreeContains Determine whether some key is present in the tree.
TreeFind Get the object associated with some key.
TreeFindAll Get a list of all the objects associated with some key.
TreeFindNode Get the node associated with some key.
TreeGetSplay Get whether a tree will automatically splay when not otherwise specified.
TreeHeight A tree with no nodes is considered to have a height of 0, and a tree with only a root to have a height of 1.
TreeInsert Insert a new key and value pair into the tree.
TreeIsEmpty Determine whether the tree is empty.
TreeKeys Returns an iterator object to that can be used with EachIn.
TreeNodes Returns an iterator object to that can be used with EachIn.
TreeObjects Returns an iterator object to that can be used with EachIn.
TreeRemove Remove the all values associated with the desired key.
TreeRemoveFirst Remove the first value with the desired key.
TreeRemoveNode Remove a specific node.
TreeRoot Get the root node of a tree.
TreeSetSplay Set whether a tree will automatically splay when not otherwise specified.
TreeSplayNode Splay a node so that it becomes the new root of a tree.
TreeToArray Get an array for the contents of a tree.

Types Summary

BinNode A single node for a binary tree.
BinTree A binary tree object.

Functions

Function BinNodeContents:TList(node:BinNode)
ReturnsA TList containing all the objects associated with this node's key.
DescriptionGets node contents as a TList.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert into the tree a bunch of stuff
TreeInsert tree,"key 1","kitty"
TreeInsert tree,"key 1","ewe"
TreeInsert tree,"key 1","jellyfish"
TreeInsert tree,"key 2","cougar"
TreeInsert tree,"key 2","crab"
TreeInsert tree,"key 2","jackal"

'print the contents of the key 'key 1'
Print "key 1:"
For Local str$=EachIn BinNodeContents(TreeFindNode(tree,"key 1"))
	Print str
Next

'and now print the contents of the key 'key 2'
Print "key 2:"
For Local str$=EachIn BinNodeContents(TreeFindNode(tree,"key 2"))
	Print str
Next

Function BinNodeKey:String(node:BinNode)
ReturnsThe node's key.
DescriptionGets node key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert a node into the tree
Local node:BinNode=TreeInsert(tree,"I like big butts","and I cannot lie")

'print the node's key (you other brothers can't deny)
Print BinNodeKey(node)

Function BinNodeString:String(node:BinNode)
ReturnsA string containing objects cast as strings separated by commas.
DescriptionGets node contents as a list of comma separated values.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert a new node into it
Local node:BinNode=TreeInsert(tree,"key","value 1")
TreeInsert(tree,"key","value 2")
TreeInsert(tree,"key","value 3")
TreeInsert(tree,"key","value 4")

'now print that pizazz
Print BinNodeString(node)

Function BinNodeValue:Object(node:BinNode)
ReturnsThe node's value.
DescriptionGets node value.
InformationOnly the first value is returned, not any others with duplicate keys.

Function ClearTree(tree:BinTree)
DescriptionClear all contents of a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:bintree=CreateTree()

'fill the tree with some elements
For Local i%=1 To 5
	TreeInsert tree,i,String(i)
Next

'check if the tree is empty
Print "Is the tree empty? "+TreeIsEmpty(tree)

'clear the tree
Print "Clearing the tree..."
ClearTree tree

'check again if the tree is empty
Print "*Now* is the tree empty? "+TreeIsEmpty(tree)

Function CopyTree:BinTree(tree:BinTree)
ReturnsA tree with identical key and value pairs but different node objects.
DescriptionCopy a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with some elements
For Local i%=1 To 5
	TreeInsert tree,i,String(i)
Next

'copy it
Print "Copying tree..."
Local copy:BinTree=CopyTree(tree)

'screw around with the original tree
Print "Clearing the original tree..."
ClearTree tree

'print out the contents of the copied tree
Print "Contents of copied tree:"
For Local str$=EachIn copy
	Print str
Next

Function CountTree:Int(tree:BinTree)
ReturnsThe number of values in the tree.
DescriptionCount the number of values in a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import brl.random
Import pine.BinTree

'create a new tree object
Local tree:bintree=CreateTree()

'fill the tree with a random amount of elements
SeedRnd MilliSecs()
For Local i%=1 To Rand(20,50)
	TreeInsert tree,i,String(i)
Next

'print out the contents of the tree
'note that keys are compared as strings, not numbers, so that the list is not ordered numerically.
Print "Tree contents:"
For Local str$=EachIn tree
	Print str
Next

'print the number of elements in the tree
Print "Number of elements: "+CountTree(tree)

Function CountTreeNodes:Int(tree:BinTree)
ReturnsThe number of nodes in the tree.
DescriptionCount the number of nodes in a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'put some elements in the tree, include some duplicate keys
TreeInsert tree,"flower","daisy"
TreeInsert tree,"flower","rose"
TreeInsert tree,"flower","violet"
TreeInsert tree,"animal","yeti"
TreeInsert tree,"animal","raccoon"
TreeInsert tree,"animal","yeti"
TreeInsert tree,"stone","agate"
TreeInsert tree,"stone","amythest"

'print the number of elements in the tree
Print "Number of elements: "+CountTree(tree)

'print the number of nodes in the tree
Print "Number of nodes: "+CountTreeNodes(tree)

Function CreateTree:BinTree(splay:Int=True)
ReturnsA new tree.
DescriptionCreate a new tree.
Example
SuperStrict

'import required modules
Framework pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

Function OptimizeTree(tree:BinTree)
DescriptionOptimize the tree so that it is as close to balanced as possible.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-z
'note: this kind of sequential insertion is bad for keeping blanced trees
'	(i.e. it fucks shit up)
For Local i%=Asc("a") To Asc("z")
	TreeInsert tree,Chr(i),String(i)
Next

'print the tree's height
Print "Height of tree: "+TreeHeight(tree)

'balance the tree
Print "Optimizing tree..."
OptimizeTree tree

'print the tree's new height
Print "New height of tree: "+TreeHeight(tree)

Function TreeContains:Int(tree:BinTree,key:String)
Returns1 if there is any node in the tree with the specified key, 0 if there is not.
DescriptionDetermine whether some key is present in the tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-g
For Local i%=Asc("a") To Asc("g")
	TreeInsert tree,Chr(i),String(i)
Next

'see what stuff is or isn't in the tree
Print "Tree contains key 'a'? "+TreeContains(tree,"a")
Print "Tree contains key 'f'? "+TreeContains(tree,"f")
Print "Tree contains key 'o'? "+TreeContains(tree,"o")
Print "Tree contains key 'z'? "+TreeContains(tree,"z")

Function TreeFind:Object(tree:BinTree,key:String)
ReturnsThe first value in the tree associated with the desired key, null if one does not exist.
DescriptionGet the object associated with some key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import brl.retro
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'put some values into it
TreeInsert tree,"apple","fruit"
TreeInsert tree,"orange","fruit"
TreeInsert tree,"pear","fruit"
TreeInsert tree,"onion","vegetable"
TreeInsert tree,"carrot","vegetable"
TreeInsert tree,"broccoli","vegetable"

'find the value associated with a key
Print "A carrot is a: "+String(TreeFind(tree,"carrot"))+"!"

Function TreeFindAll:TList(tree:BinTree,key:String)
ReturnsA list containing all the values in the tree associated with the desired key.
DescriptionGet a list of all the objects associated with some key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'shove some animals up into it
TreeInsert tree,"dog","Lassie"
TreeInsert tree,"dog","Siloh"
TreeInsert tree,"monkey","Curious George"
TreeInsert tree,"dog","Arfy"
TreeInsert tree,"dog","Air Bud"
TreeInsert tree,"fish","Nemo"
TreeInsert tree,"fish","Goldeen"

'get a list of all the values associated with the key 'dog'
Local contents:TList=TreeFindAll(tree,"dog")
'iterate through and print them
For Local obj$=EachIn contents
	Print obj+" is a dog!"
Next

Function TreeFindNode:BinNode(tree:BinTree,key:String)
ReturnsThe node in the tree with the specified key, null if none exists.
DescriptionGet the node associated with some key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert into the tree three different values
TreeInsert tree,"first","1st"
TreeInsert tree,"second","2nd"
TreeInsert tree,"third","3rd"

'print the value of a node in the tree
Print BinNodeString(TreeFindNode(tree,"first"))

Function TreeGetSplay:Int(tree:BinTree)
Returns1 if the tree is set to splay automatically, 0 if not.
DescriptionGet whether a tree will automatically splay when not otherwise specified.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'print out that splay settings info
Print TreeGetSplay(tree)

'set the splay to false
Print "Setting splay to false..."
TreeSetSplay tree,False

'now print it out again
Print TreeGetSplay(tree)

'make a new tree, and initialize it with splay set to false
Print "Making a brand-new tree..."
Local tree_2:BinTree=CreateTree(False)

'and print that stuff out one last time
Print TreeGetSplay(tree_2)

Function TreeHeight:Int(tree:BinTree)
ReturnsThe height of the tree.
DescriptionA tree with no nodes is considered to have a height of 0, and a tree with only a root to have a height of 1.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import brl.random
Import pine.BinTree

'create a new tree object
Local tree:bintree=CreateTree()

'fill the tree with a random amount of elements
SeedRnd MilliSecs()
For Local i%=1 To Rand(20,50)
	TreeInsert tree,i,String(i)
Next

'print out the contents of the tree
'note that keys are compared as strings, not numbers, so that the list is not ordered numerically.
Print "Tree contents:"
For Local str$=EachIn tree
	Print str
Next

'print the number of elements in the tree
Print "Height of the tree: "+TreeHeight(tree)

Function TreeInsert:BinNode(tree:BinTree,key:String,value:Object)
ReturnsThe newly inserted node.
DescriptionInsert a new key and value pair into the tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'put something in the tree
TreeInsert tree,"key","value"

Function TreeIsEmpty:Int(tree:BinTree)
Returns1 if the tree is empty, 0 if it contains at least a root.
DescriptionDetermine whether the tree is empty.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create two new tree objects
Local treeA:bintree=CreateTree()
Local treeB:bintree=CreateTree()

'fill tree A with some elements
For Local i%=1 To 5
	TreeInsert treeA,i,String(i)
Next

'check if each tree is empty
Print "Is tree A empty? "+TreeIsEmpty(treeA)
Print "Is tree B empty? "+TreeIsEmpty(treeB)

Function TreeKeys:BinEnum(tree:BinTree)
ReturnsAn iterator object.
DescriptionReturns an iterator object to that can be used with EachIn.
InformationIterates through the keys in the tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-g
For Local i%=Asc("a") To Asc("g")
	TreeInsert tree,Chr(i),String(i)
Next

'balance the tree
OptimizeTree tree

'print out all the keys in the tree
Print "Keys:"
For Local str$=EachIn TreeKeys(tree)
	Print str
Next
'print out all the objects in the tree
Print "Values:"
For Local str$=EachIn TreeObjects(tree)
	Print str
Next
'print out all the keys and value pairs in the tree
Print "Keys:"
For Local n:BinNode=EachIn TreeNodes(tree)
	Print n.key+","+String(n.data)
Next

Function TreeNodes:BinEnum(tree:BinTree)
ReturnsAn iterator object.
DescriptionReturns an iterator object to that can be used with EachIn.
InformationIterates through the nodes in the tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-g
For Local i%=Asc("a") To Asc("g")
	TreeInsert tree,Chr(i),String(i)
Next

'balance the tree
OptimizeTree tree

'print out all the keys in the tree
Print "Keys:"
For Local str$=EachIn TreeKeys(tree)
	Print str
Next
'print out all the objects in the tree
Print "Values:"
For Local str$=EachIn TreeObjects(tree)
	Print str
Next
'print out all the keys and value pairs in the tree
Print "Keys:"
For Local n:BinNode=EachIn TreeNodes(tree)
	Print n.key+","+String(n.data)
Next

Function TreeObjects:BinEnum(tree:BinTree)
ReturnsAn iterator object.
DescriptionReturns an iterator object to that can be used with EachIn.
InformationIterates through the objects in the tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-g
For Local i%=Asc("a") To Asc("g")
	TreeInsert tree,Chr(i),String(i)
Next

'balance the tree
OptimizeTree tree

'print out all the keys in the tree
Print "Keys:"
For Local str$=EachIn TreeKeys(tree)
	Print str
Next
'print out all the objects in the tree
Print "Values:"
For Local str$=EachIn TreeObjects(tree)
	Print str
Next
'print out all the keys and value pairs in the tree
Print "Keys:"
For Local n:BinNode=EachIn TreeNodes(tree)
	Print n.key+","+String(n.data)
Next

Function TreeRemove:Int(tree:BinTree,key:String)
ReturnsThe number of values removed.
DescriptionRemove the all values associated with the desired key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree(1)

'put some stuff in the tree
TreeInsert tree,"group 1","up"
TreeInsert tree,"group 1","down"
TreeInsert tree,"group 2","left"
TreeInsert tree,"group 2","forward"
TreeInsert tree,"group 2","right"
TreeInsert tree,"group 3","in"
TreeInsert tree,"group 3","out"

'output the contents of the tree
Print "Contents:"
For Local str$=EachIn tree
	Print str
Next

'now take out group 2
Print "Taking some stuff out..."
TreeRemove tree,"group 2"

'output the new contents of the tree
Print "New contents:"
For Local str$=EachIn tree
	Print str
Next

Function TreeRemoveFirst:BinNode(tree:BinTree,key:String)
ReturnsThe node the value was removed from, or null if nothing was found to be removed.
DescriptionRemove the first value with the desired key.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert into the tree three values with the same key
TreeInsert tree,"key","A"
TreeInsert tree,"key","B"
TreeInsert tree,"key","C"

'remove the first value associated with the key 'key'
TreeRemoveFirst tree,"key"

'print out all the objects in the tree
Print "Values:"
For Local str$=EachIn tree
	Print str
Next

Function TreeRemoveNode(tree:BinTree,node:BinNode)
DescriptionRemove a specific node.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree(1)

'put some stuff in the tree
Local node:BinNode=TreeInsert(tree,"group 1","down")
TreeInsert tree,"group 1","up"
TreeInsert tree,"group 2","left"
TreeInsert tree,"group 2","right"

'output the contents of the tree
Print "Contents:"
For Local str$=EachIn tree
	Print str
Next

'now take out group 2
Print "Taking one node out..."
TreeRemoveNode tree,node

'output the new contents of the tree
Print "New contents:"
For Local str$=EachIn tree
	Print str
Next

Function TreeRoot:BinNode(tree:BinTree)
ReturnsThe root node of the tree.
DescriptionGet the root node of a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert into the tree three values with the same key
TreeInsert tree,"first","1st"
TreeInsert tree,"second","2nd"
TreeInsert tree,"third","3rd"

'print the key of the tree's root node
Print BinNodeKey(TreeRoot(tree))

Function TreeSetSplay(tree:BinTree,splay:Int)
DescriptionSet whether a tree will automatically splay when not otherwise specified.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'print out that splay settings info
Print TreeGetSplay(tree)

'set the splay to false
Print "Setting splay to false..."
TreeSetSplay tree,False

'now print it out again
Print TreeGetSplay(tree)

Function TreeSplayNode(tree:BinTree,node:BinNode)
DescriptionSplay a node so that it becomes the new root of a tree.
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'insert into the tree three values with the same key
TreeInsert tree,"first","1st"
TreeInsert tree,"second","2nd"
TreeInsert tree,"third","3rd"

'print the key of the tree's root node
Print BinNodeKey(TreeRoot(tree))

'set a different node as the root
Print "Splaying a different node..."
TreeSplayNode tree,TreeFindNode(tree,"first")

'print the key of the tree's new root node
Print BinNodeKey(TreeRoot(tree))

Function TreeToArray:Object[](tree:BinTree,sort:Int=0)
ReturnsAn array containing the objects in the tree.
DescriptionGet an array for the contents of a tree.
Informationsort can be one of:
ValueResult

0Elements in the array are ordered via an in-order traversal

1Elements in the array are ordered via a reversed in-order traversal

2Elements in the array are ordered via a pre-order traversal

3Elements in the array are ordered via a post-order traversal
Example
SuperStrict

'import required modules
Framework brl.standardio
Import pine.BinTree

'create a new tree object
Local tree:BinTree=CreateTree()

'fill the tree with the letters a-g
For Local i%=Asc("a") To Asc("g")
	TreeInsert tree,Chr(i),Chr(i)
Next

'balance the tree
OptimizeTree tree

'print out the contents of the tree, iterating left-to-right
Print "EachIn:"
For Local str$=EachIn tree
	Print str
Next

'print out the contents of the tree in-order
Print "In-order:"
For Local str$=EachIn TreeToArray(tree,0)
	Print str
Next

'print out the contents of the tree reversed in-order
Print "Reverse-order:"
For Local str$=EachIn TreeToArray(tree,1)
	Print str
Next

'print out the contents of the tree pre-order
Print "Pre-order:"
For Local str$=EachIn TreeToArray(tree,2)
	Print str
Next

'print out the contents of the tree post-order
Print "Post-order:"
For Local str$=EachIn TreeToArray(tree,3)
	Print str
Next

Types

Type BinNode
DescriptionA single node for a binary tree.
Methods Summary
addvalue Add value(s) to this node, for handling duplicate keys.
clearlinks Recursive algorithm which discards all links between nodes in this node's subtree.
copy Copy the subtree which this node is the root of.
count Recursive counting algorithm.
countvalues Recursive counting algorithm.
csv Gets node contents as a list of comma separated values.
findclosest Recursive search algorithm.
height Recursive counting algorithm.
inorder Perform an in-order traversal of the tree.
insert Insertion algorithm.
leftmostchild Iterates through the left children starting at this node until a node is found which does not have a left child, and returns that node.
movetoleft Move this node so that it becomes the leftmost child of the specified node.
movetoright Move this node so that it becomes the rightmost child of the specified node.
nodesinorder Perform an in-order traversal of the tree.
nodespostorder Perform a post-order traversal of the tree.
nodespreorder Perform a pre-order traversal of the tree.
nodesreverseorder Perform a reversed in-order traversal of the tree.
optimize Optimize this node's subtree so that it is as close to balanced as possible and return the new root.
orphan Sever links to and from the node's parent.
postorder Perform a post-order traversal of the tree.
predecessor If the node has a left child then return that node's rightmost child, otherwise return the first node possessing a left child found while travelling up its ancestry.
preorder Perform a pre-order traversal of the tree.
remove Remove a node and return the node which replaces it, null if none does.
removeallvalues Remove all the values from a node, And the node only If flag is True.
removevalue Remove a single value from a node, and the node only if no values remain and flag is true.
reverseorder Perform a reversed in-order traversal of the tree.
rightmostchild Iterates through the right children starting at this node until a node is found which does not have a right child, and returns that node.
successor If the node has a right child then return that node's leftmost child, otherwise return the first node possessing a right child found while travelling up its ancestry.
value Get the first value the node contains.
valuecount Get the number of values belonging to the node.
values Get all the values the node contains as a list.
Functions Summary
Create Create a new node.
Method addvalue(n:BinNodeData)
DescriptionAdd value(s) to this node, for handling duplicate keys.
InformationTakes a BinNodeData for an argument, and appends all members of it onto the beginning of the node's existing list of values.
Method copy:BinNode()
ReturnsA subtree with identical key and value pairs but different node objects.
DescriptionCopy the subtree which this node is the root of.
Method count%()
ReturnsThe number of nodes in this node's subtree.
DescriptionRecursive counting algorithm.
Method countvalues%()
ReturnsThe number of values in this node's subtree.
DescriptionRecursive counting algorithm.
Method csv$()
ReturnsA string containing objects cast as strings separated by commas.
DescriptionGets node contents as a list of comma separated values.
Method findclosest:BinNode(k$)
ReturnsThe first node in this node's subtree with the desired key, or the closest to the desired key.
DescriptionRecursive search algorithm.
Method height%()
ReturnsThe height of this node's subtree.
DescriptionRecursive counting algorithm.
InformationA tree containing only its root is considered to have a height of 1.
Method inorder:Object[]() 'return array of BinNodes resulting from an in-order traversal
ReturnsAn array of objects organized such that this node's subtree was traversed in-order.
DescriptionPerform an in-order traversal of the tree.
Method insert:BinNode(n:BinNode)
DescriptionInsertion algorithm.
Method leftmostchild:BinNode()
ReturnsThe leftmost child of the node.
DescriptionIterates through the left children starting at this node until a node is found which does not have a left child, and returns that node.
Method movetoleft(t:BinNode)
DescriptionMove this node so that it becomes the leftmost child of the specified node.
Method movetoright(t:BinNode)
DescriptionMove this node so that it becomes the rightmost child of the specified node.
Method nodesinorder:BinNode[]() 'return array of BinNodes resulting from an in-order traversal
ReturnsAn array of nodes organized such that this node's subtree was traversed in-order.
DescriptionPerform an in-order traversal of the tree.
Method nodespostorder:BinNode[]()
ReturnsAn array of nodes organized such that this node's subtree was traversed post-order.
DescriptionPerform a post-order traversal of the tree.
Method nodespreorder:BinNode[]()
ReturnsAn array of nodes organized such that this node's subtree was traversed pre-order.
DescriptionPerform a pre-order traversal of the tree.
Method nodesreverseorder:BinNode[]()
ReturnsAn array of nodes organized such that this node's subtree was traversed reverse in-order.
DescriptionPerform a reversed in-order traversal of the tree.
Method optimize:BinNode() 'rearrange this entire tree with self as the root so that it's optimal and return the new root
ReturnsThe root of the new, optimized tree.
DescriptionOptimize this node's subtree so that it is as close to balanced as possible and return the new root.
Method orphan()
DescriptionSever links to and from the node's parent.
Method postorder:Object[]()
ReturnsAn array of objects organized such that this node's subtree was traversed post-order.
DescriptionPerform a post-order traversal of the tree.
Method predecessor:BinNode()
ReturnsThe node in the tree with the next least key, null if none exists.
DescriptionIf the node has a left child then return that node's rightmost child, otherwise return the first node possessing a left child found while travelling up its ancestry.
Method preorder:Object[]()
ReturnsAn array of objects organized such that this node's subtree was traversed pre-order.
DescriptionPerform a pre-order traversal of the tree.
Method remove:BinNode()
ReturnsNode with the new equivalent position as the removed one, null if none such node exists.
DescriptionRemove a node and return the node which replaces it, null if none does.
Method removeallvalues:BinNode(flag%=False)
ReturnsThe node which takes its place if this node gets removed, otherwise returns itself.
DescriptionRemove all the values from a node, And the node only If flag is True.
Method removevalue:BinNode(flag%=True)
ReturnsThe node which takes its place if this node gets removed, otherwise returns itself.
DescriptionRemove a single value from a node, and the node only if no values remain and flag is true.
Method reverseorder:Object[]()
ReturnsAn array of objects organized such that this node's subtree was traversed reverse in-order.
DescriptionPerform a reversed in-order traversal of the tree.
Method rightmostchild:BinNode()
ReturnsThe rightmost child of the node.
DescriptionIterates through the right children starting at this node until a node is found which does not have a right child, and returns that node.
Method successor:BinNode()
ReturnsThe node in the tree with the next greatest key, null if none exists.
DescriptionIf the node has a right child then return that node's leftmost child, otherwise return the first node possessing a right child found while travelling up its ancestry.
Method value:Object()
ReturnsAn object.
DescriptionGet the first value the node contains.
Method valuecount%()
ReturnsThe number of values.
DescriptionGet the number of values belonging to the node.
Method values:TList()
ReturnsA TList.
DescriptionGet all the values the node contains as a list.
Function Create:BinNode(key$,o:Object)
ReturnsA new node.
DescriptionCreate a new node.

Type BinTree
DescriptionA binary tree object.
Methods Summary
clear Clear all contents of the tree.
contains Determine whether some key is present in the tree.
copy Copy the tree.
count Count the number of nodes.
countvalues Count the number of values.
find Get the object associated with some key.
findall Get a list of all the objects associated with some key.
findclosest Get the object associated with the closest key to some key.
findclosestnode Get the node with the closest key to some key.
findnode Get the node with some key.
height A tree with no nodes is considered to have a height of 0, and a tree with only a root to have a height of 1.
insert Insert a new key and value pair into the tree.
isempty Determine whether the tree is empty.
issplay Determine whether the tree is set to be a splay tree.
KeyEnumerator Method implements EachIn support.
NodeEnumerator Method implements EachIn support.
ObjectEnumerator Method implements EachIn support.
optimize Optimize the tree so that it is as close to balanced as possible.
remove Remove the first associated object with the desired key.
removeall Remove the all associations with the desired key.
removenode Remove a node from the tree.
rotleft Node rotation left.
rotright Node rotation right.
setsplay Set whether the tree is set to be a splay tree.
splay Splay a node such that it becomes the new root of the tree.
Functions Summary
Create Create a new tree.
Method clear()
DescriptionClear all contents of the tree.
Method contains%(key$,dosplay%=0)
Returns1 if there is any node in the tree with the specified key, 0 if there is not.
DescriptionDetermine whether some key is present in the tree.
Method copy:BinTree()
ReturnsA tree with identical key and value pairs but different node objects.
DescriptionCopy the tree.
Method count%()
ReturnsThe number of nodes in the tree.
DescriptionCount the number of nodes.
Method countvalues%()
ReturnsThe number of values in the tree.
DescriptionCount the number of values.
Method find:Object(key$,dosplay%=-1)
ReturnsThe first value in the tree associated with the desired key, null if one does not exist.
DescriptionGet the object associated with some key.
Method findall:TList(key$,dosplay%=-1)
ReturnsA list containing all the values in the tree associated with the desired key.
DescriptionGet a list of all the objects associated with some key.
Method findclosest:Object(key$,dosplay%=-1)
ReturnsThe first value in the tree associated with the desired key, or the value associated with the key closest to the desired key.
DescriptionGet the object associated with the closest key to some key.
Method findclosestnode:BinNode(key$,dosplay%=-1)
ReturnsThe first node in the tree with the desired key, or the node with a value closest to the desired key.
DescriptionGet the node with the closest key to some key.
Method findnode:BinNode(key$,dosplay%=-1)
ReturnsThe first node in the tree with the desired key, null if one does not exist.
DescriptionGet the node with some key.
Method height%()
ReturnsThe height of the tree.
DescriptionA tree with no nodes is considered to have a height of 0, and a tree with only a root to have a height of 1.
Method insert:BinNode(key$,o:Object=Null,dosplay%=-1)
ReturnsThe newly inserted node.
DescriptionInsert a new key and value pair into the tree.
Method isempty%()
Returns1 if the tree is empty, 0 if it contains at least a root.
DescriptionDetermine whether the tree is empty.
Method issplay%()
Returns1 if the tree is set to splay automatically, 0 if not.
DescriptionDetermine whether the tree is set to be a splay tree.
Method KeyEnumerator:BinEnum()
ReturnsAn iterator object.
DescriptionMethod implements EachIn support.
InformationIterates through the keys in the tree.
Method NodeEnumerator:BinEnum()
ReturnsAn iterator object.
DescriptionMethod implements EachIn support.
InformationIterates through the nodes in the tree.
Method ObjectEnumerator:BinEnum()
ReturnsAn iterator object.
DescriptionMethod implements EachIn support.
InformationIterates through the objects in the tree.
Method optimize()
DescriptionOptimize the tree so that it is as close to balanced as possible.
Method remove:BinNode(key$)
ReturnsThe node that the association was removed from, null if no node was affected.
DescriptionRemove the first associated object with the desired key.
Method removeall:BinNode(key$)
ReturnsThe node that was removed.
DescriptionRemove the all associations with the desired key.
Method removenode:BinNode(n:BinNode)
ReturnsThe node which took its new position, if any.
DescriptionRemove a node from the tree.
Method rotleft(n:BinNode)
DescriptionNode rotation left.
Method rotright(n:BinNode)
DescriptionNode rotation right.
Method setsplay%(dosplay%)
DescriptionSet whether the tree is set to be a splay tree.
Method splay(n:BinNode)
DescriptionSplay a node such that it becomes the new root of the tree.
Function Create:BinTree(splay%=True)
ReturnsA new tree.
DescriptionCreate a new tree.

Module Information

Version1.01
AuthorSophie Kirschner : meapineapple@gmail.com
LicenseCreative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)
Modserverpine
History1.02 Release
HistoryAdded TreeCountValues and BinNodeValue
History1.01 Release
HistoryAdded splay tree functionality
Historychanged BinTree.remove() to return a node instead of a boolean and added TreeRemoveFirst
HistoryRevised handling of duplicate keys