pine.BinTree: | Functions | Types | Modinfo | Source |
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.
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. |
BinNode | A single node for a binary tree. |
BinTree | A binary tree object. |
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:
| ||||||||||
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 |
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. |
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 |