pine.BinTree:

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)
Returns	A TList containing all the objects associated with this node's key.
Description	Gets 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)
Returns	The node's key.
Description	Gets 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)
Returns	A string containing objects cast as strings separated by commas.
Description	Gets 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)
Returns	The node's value.
Description	Gets node value.
Information	Only the first value is returned, not any others with duplicate keys.

Function ClearTree(tree:BinTree)

Description

Clear 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)
Returns	A tree with identical key and value pairs but different node objects.
Description	Copy 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)
Returns	The number of values in the tree.
Description	Count 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)
Returns	The number of nodes in the tree.
Description	Count 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)
Returns	A new tree.
Description	Create a new tree.
Example	SuperStrict 'import required modules Framework pine.BinTree 'create a new tree object Local tree:BinTree=CreateTree()

Function OptimizeTree(tree:BinTree)

Description

Optimize 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)
Returns	1 if there is any node in the tree with the specified key, 0 if there is not.
Description	Determine 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)
Returns	The first value in the tree associated with the desired key, null if one does not exist.
Description	Get 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)
Returns	A list containing all the values in the tree associated with the desired key.
Description	Get 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)
Returns	The node in the tree with the specified key, null if none exists.
Description	Get 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)
Returns	1 if the tree is set to splay automatically, 0 if not.
Description	Get 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)
Returns	The height of the tree.
Description	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.
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)
Returns	The newly inserted node.
Description	Insert 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)
Returns	1 if the tree is empty, 0 if it contains at least a root.
Description	Determine 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)
Returns	An iterator object.
Description	Returns an iterator object to that can be used with EachIn.
Information	Iterates 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)
Returns	An iterator object.
Description	Returns an iterator object to that can be used with EachIn.
Information	Iterates 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)
Returns	An iterator object.
Description	Returns an iterator object to that can be used with EachIn.
Information	Iterates 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)
Returns	The number of values removed.
Description	Remove 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)
Returns	The node the value was removed from, or null if nothing was found to be removed.
Description	Remove 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)

Description

Remove 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)
Returns	The root node of the tree.
Description	Get 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)

Description

Set 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)

Description

Splay 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)

Returns

An array containing the objects in the tree.

Description

Get an array for the contents of a tree.

Information

sort can be one of:

Value	Result
0	Elements in the array are ordered via an in-order traversal
1	Elements in the array are ordered via a reversed in-order traversal
2	Elements in the array are ordered via a pre-order traversal
3	Elements 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
Description	A 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)
Description	Add value(s) to this node, for handling duplicate keys.
Information	Takes a BinNodeData for an argument, and appends all members of it onto the beginning of the node's existing list of values.

Method clearlinks()
Description	Recursive algorithm which discards all links between nodes in this node's subtree.

Method copy:BinNode()
Returns	A subtree with identical key and value pairs but different node objects.
Description	Copy the subtree which this node is the root of.

Method count%()
Returns	The number of nodes in this node's subtree.
Description	Recursive counting algorithm.

Method countvalues%()
Returns	The number of values in this node's subtree.
Description	Recursive counting algorithm.

Method csv$()
Returns	A string containing objects cast as strings separated by commas.
Description	Gets node contents as a list of comma separated values.

Method findclosest:BinNode(k$)
Returns	The first node in this node's subtree with the desired key, or the closest to the desired key.
Description	Recursive search algorithm.

Method height%()
Returns	The height of this node's subtree.
Description	Recursive counting algorithm.
Information	A 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
Returns	An array of objects organized such that this node's subtree was traversed in-order.
Description	Perform an in-order traversal of the tree.

Method insert:BinNode(n:BinNode)
Description	Insertion algorithm.

Method leftmostchild:BinNode()
Returns	The leftmost child of the node.
Description	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.

Method movetoleft(t:BinNode)
Description	Move this node so that it becomes the leftmost child of the specified node.

Method movetoright(t:BinNode)
Description	Move 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
Returns	An array of nodes organized such that this node's subtree was traversed in-order.
Description	Perform an in-order traversal of the tree.

Method nodespostorder:BinNode[]()
Returns	An array of nodes organized such that this node's subtree was traversed post-order.
Description	Perform a post-order traversal of the tree.

Method nodespreorder:BinNode[]()
Returns	An array of nodes organized such that this node's subtree was traversed pre-order.
Description	Perform a pre-order traversal of the tree.

Method nodesreverseorder:BinNode[]()
Returns	An array of nodes organized such that this node's subtree was traversed reverse in-order.
Description	Perform 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
Returns	The root of the new, optimized tree.
Description	Optimize this node's subtree so that it is as close to balanced as possible and return the new root.

Method orphan()
Description	Sever links to and from the node's parent.

Method postorder:Object[]()
Returns	An array of objects organized such that this node's subtree was traversed post-order.
Description	Perform a post-order traversal of the tree.

Method predecessor:BinNode()
Returns	The node in the tree with the next least key, null if none exists.
Description	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.

Method preorder:Object[]()
Returns	An array of objects organized such that this node's subtree was traversed pre-order.
Description	Perform a pre-order traversal of the tree.

Method remove:BinNode()
Returns	Node with the new equivalent position as the removed one, null if none such node exists.
Description	Remove a node and return the node which replaces it, null if none does.

Method removeallvalues:BinNode(flag%=False)
Returns	The node which takes its place if this node gets removed, otherwise returns itself.
Description	Remove all the values from a node, And the node only If flag is True.

Method removevalue:BinNode(flag%=True)
Returns	The node which takes its place if this node gets removed, otherwise returns itself.
Description	Remove a single value from a node, and the node only if no values remain and flag is true.

Method reverseorder:Object[]()
Returns	An array of objects organized such that this node's subtree was traversed reverse in-order.
Description	Perform a reversed in-order traversal of the tree.

Method rightmostchild:BinNode()
Returns	The rightmost child of the node.
Description	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.

Method successor:BinNode()
Returns	The node in the tree with the next greatest key, null if none exists.
Description	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.

Method value:Object()
Returns	An object.
Description	Get the first value the node contains.

Method valuecount%()
Returns	The number of values.
Description	Get the number of values belonging to the node.

Method values:TList()
Returns	A TList.
Description	Get all the values the node contains as a list.

Function Create:BinNode(key$,o:Object)
Returns	A new node.
Description	Create a new node.

Type BinTree
Description	A 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()
Description	Clear all contents of the tree.

Method contains%(key$,dosplay%=0)
Returns	1 if there is any node in the tree with the specified key, 0 if there is not.
Description	Determine whether some key is present in the tree.

Method copy:BinTree()
Returns	A tree with identical key and value pairs but different node objects.
Description	Copy the tree.

Method count%()
Returns	The number of nodes in the tree.
Description	Count the number of nodes.

Method countvalues%()
Returns	The number of values in the tree.
Description	Count the number of values.

Method find:Object(key$,dosplay%=-1)
Returns	The first value in the tree associated with the desired key, null if one does not exist.
Description	Get the object associated with some key.

Method findall:TList(key$,dosplay%=-1)
Returns	A list containing all the values in the tree associated with the desired key.
Description	Get a list of all the objects associated with some key.

Method findclosest:Object(key$,dosplay%=-1)
Returns	The first value in the tree associated with the desired key, or the value associated with the key closest to the desired key.
Description	Get the object associated with the closest key to some key.

Method findclosestnode:BinNode(key$,dosplay%=-1)
Returns	The first node in the tree with the desired key, or the node with a value closest to the desired key.
Description	Get the node with the closest key to some key.

Method findnode:BinNode(key$,dosplay%=-1)
Returns	The first node in the tree with the desired key, null if one does not exist.
Description	Get the node with some key.

Method height%()
Returns	The height of the tree.
Description	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.

Method insert:BinNode(key$,o:Object=Null,dosplay%=-1)
Returns	The newly inserted node.
Description	Insert a new key and value pair into the tree.

Method isempty%()
Returns	1 if the tree is empty, 0 if it contains at least a root.
Description	Determine whether the tree is empty.

Method issplay%()
Returns	1 if the tree is set to splay automatically, 0 if not.
Description	Determine whether the tree is set to be a splay tree.

Method KeyEnumerator:BinEnum()
Returns	An iterator object.
Description	Method implements EachIn support.
Information	Iterates through the keys in the tree.

Method NodeEnumerator:BinEnum()
Returns	An iterator object.
Description	Method implements EachIn support.
Information	Iterates through the nodes in the tree.

Method ObjectEnumerator:BinEnum()
Returns	An iterator object.
Description	Method implements EachIn support.
Information	Iterates through the objects in the tree.

Method optimize()
Description	Optimize the tree so that it is as close to balanced as possible.

Method remove:BinNode(key$)
Returns	The node that the association was removed from, null if no node was affected.
Description	Remove the first associated object with the desired key.

Method removeall:BinNode(key$)
Returns	The node that was removed.
Description	Remove the all associations with the desired key.

Method removenode:BinNode(n:BinNode)
Returns	The node which took its new position, if any.
Description	Remove a node from the tree.

Method rotleft(n:BinNode)
Description	Node rotation left.

Method rotright(n:BinNode)
Description	Node rotation right.

Method setsplay%(dosplay%)
Description	Set whether the tree is set to be a splay tree.

Method splay(n:BinNode)
Description	Splay a node such that it becomes the new root of the tree.

Function Create:BinTree(splay%=True)
Returns	A new tree.
Description	Create a new tree.

Module Information

Version	1.01
Author	Sophie Kirschner : meapineapple@gmail.com
License	Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)
Modserver	pine
History	1.02 Release
History	Added TreeCountValues and BinNodeValue
History	1.01 Release
History	Added splay tree functionality
History	changed BinTree.remove() to return a node instead of a boolean and added TreeRemoveFirst
History	Revised handling of duplicate keys