BinarySearchTree

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>

Summary
BinarySearchTreeA Binary Search Tree (BST).
Variables
rootThe root node being referenced.
Functions
BinarySearchTreeInitializes a BST tree with a given comparison function.
insertInserts an item into the tree.
findFinds 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.
removeRemoves a node from the BST.
contains@inheritDoc
clearThe tree is cleared recursively, starting from the node on which the method is called.
getIteratorAn iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead.
Properties
size@inheritDoc
Functions
isEmpty@inheritDoc
toArray@inheritDoc
toStringPrints out a string representing the current object.
dumpPrints out all elements (for debug/demo purposes).

Variables

root

public var root: BinaryTreeNode

The root node being referenced.

Functions

BinarySearchTree

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.

Parameters

compareThe comparison function. 

insert

public function insert(obj: *):void

Inserts an item into the tree.

Parameters

objThe data. 

find

public function find(obj: *):BinaryTreeNode

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.

Parameters

objThe data to find. 

Returns

A node containing the data or null if the data wasn’t found. 

remove

public function remove(node: BinaryTreeNode):void

Removes a node from the BST.

Parameters

nodeThe node to remove. 

contains

public function contains(obj: *):Boolean

@inheritDoc

clear

public function clear():void

The tree is cleared recursively, starting from the node on which the method is called.

@copy Collection#clear()

getIterator

public function getIterator():Iterator

An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead.

See Also

* @see BinaryTreeNode#inorder * @see BinaryTreeNode#postorder

Properties

size

public function get size():int

@inheritDoc

Functions

isEmpty

public function isEmpty():Boolean

@inheritDoc

toArray

public function toArray():Array

@inheritDoc

toString

public function toString():String

Prints out a string representing the current object.

Returns

A string representing the current object. 

dump

public function dump():String

Prints out all elements (for debug/demo purposes).

Returns

A human-readable representation of the structure. 

A ‘java-style’ collection interface.
public var root: BinaryTreeNode
The root node being referenced.
public function BinarySearchTree(compare: Function = null)
Initializes a BST tree with a given comparison function.
public function insert(obj: *):void
Inserts an item into the tree.
public function find(obj: *):BinaryTreeNode
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 remove(node: BinaryTreeNode):void
Removes a node from the BST.
public function contains(obj: *):Boolean
@inheritDoc
public function clear():void
The tree is cleared recursively, starting from the node on which the method is called.
public function getIterator():Iterator
An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead.
public function get size():int
@inheritDoc
public function isEmpty():Boolean
@inheritDoc
public function toArray():Array
@inheritDoc
public function toString():String
Prints out a string representing the current object.
public function dump():String
Prints out all elements (for debug/demo purposes).
public static function preorder(node: BinaryTreeNode,
process: Function):void
Performs a preorder traversal on a tree.
Close