BinarySearchTree |
A Binary Search Tree (BST).
A BST stores data in a recursive manner so that you can access it quickly by using a key. Therefore, a BST automatically sorts data as it is inserted. For a BST to be valid, every node has to follow two rules: <ol><li>The data value in the left subtree must be less than the data value in the current node.</li><li>The data value in the right subtree must be greater than the data value in the current node.</li></ol>
| BinarySearchTree | A Binary Search Tree (BST). |
| Variables | |
| root | The root node being referenced. |
| Functions | |
| BinarySearchTree | Initializes a BST tree with a given comparison function. |
| insert | Inserts an item into the tree. |
| find | Finds a piece of data in the tree and returns a reference to the node that contains a match, or null if no match is found. |
| remove | Removes a node from the BST. |
| contains | @inheritDoc |
| clear | The tree is cleared recursively, starting from the node on which the method is called. |
| getIterator | An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead. |
| Properties | |
| size | @inheritDoc |
| Functions | |
| isEmpty | @inheritDoc |
| toArray | @inheritDoc |
| toString | Prints out a string representing the current object. |
| dump | Prints out all elements (for debug/demo purposes). |
public function BinarySearchTree( compare: Function = null )
Initializes a BST tree with a given comparison function. The function should return -1 if the left is ‘less than’ the right, 0 if they are equal, and 1 if the left is ‘greater than’ the right. If the function is omitted, the BST uses a default function for comparing integers.
| compare | The comparison function. |
public function getIterator():Iterator
An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead.
* @see BinaryTreeNode#inorder * @see BinaryTreeNode#postorder
The root node being referenced.
public var root: BinaryTreeNode
Initializes a BST tree with a given comparison function.
public function BinarySearchTree( compare: Function = null )
Inserts an item into the tree.
public function insert( obj: * ):void
Finds a piece of data in the tree and returns a reference to the node that contains a match, or null if no match is found.
public function find( obj: * ):BinaryTreeNode
Removes a node from the BST.
public function remove( node: BinaryTreeNode ):void
@inheritDoc
public function contains( obj: * ):Boolean
The tree is cleared recursively, starting from the node on which the method is called.
public function clear():void
An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead.
public function getIterator():Iterator
@inheritDoc
public function get size():int
@inheritDoc
public function isEmpty():Boolean
@inheritDoc
public function toArray():Array
Prints out a string representing the current object.
public function toString():String
Prints out all elements (for debug/demo purposes).
public function dump():String
Performs a preorder traversal on a tree.
public static function preorder( node: BinaryTreeNode, process: Function ):void