GODPAPER | All Packages | All Classes | Index | Frames No Frames |
BinarySearchTree

Package | de.polygonal.ds
Class | public class BinarySearchTree
Inheritance | BinarySearchTree Object
Implements | Collection

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:

1. The data value in the left subtree must be less than the data value in the current node.
2. The data value in the right subtree must be greater than the data value in the current node.

Public Properties

| Property | Defined By
--- | --- | ---
|  | root : BinaryTreeNode The root node being referenced. | BinarySearchTree
|  | size : int [read-only] The total number of items. | BinarySearchTree

Public Methods

| Method | Defined By
--- | --- | ---
|  | BinarySearchTree(compare:Function = null) Initializes a BST tree with a given comparison function. | BinarySearchTree
|  | clear():void The tree is cleared recursively, starting from the node on which the method is called. | BinarySearchTree
|  | contains(obj:*):Boolean Determines if the collection contains a given item. | BinarySearchTree
|  | dump():String Prints out all elements (for debug/demo purposes). | BinarySearchTree
|  | 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. | BinarySearchTree
|  | getIterator():Iterator An iterator is not supported, use BinaryTreeNode.preorder(), inorder() and postorder() instead. | BinarySearchTree
|  | insert(obj:*):void Inserts an item into the tree. | BinarySearchTree
|  | isEmpty():Boolean Checks if the collection is empty. | BinarySearchTree
|  | remove(node:BinaryTreeNode):void Removes a node from the BST. | BinarySearchTree
|  | toArray():Array Converts the collection into an array. | BinarySearchTree
|  | toString():String Prints out a string representing the current object. | BinarySearchTree

Property Detail

root | property

`public var root:BinaryTreeNode`

The root node being referenced.

size | property |

`size:int` [read-only]

The total number of items.

Implementation
`public function get size():int`
Constructor Detail

BinarySearchTree | () | Constructor

`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

| `compare:Function` (default = `null`)`` — The comparison function.

Method Detail

clear | () | method

`public function clear():void`

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

Clears all items.

contains | () | method |

`public function contains(obj:*):Boolean`

Determines if the collection contains a given item.

Parameters

| `obj:*` — The item to search for.

Returns

| `Boolean` — True if the item exists, otherwise false.

dump | () | method |

`public function dump():String`

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

Returns

| `String` — A human-readable representation of the structure.

find | () | method |

`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

| `obj:*` — The data to find.

Returns

| `BinaryTreeNode` — A node containing the data or null if the data wasn't found.

getIterator | () | method |

`public function getIterator():Iterator`

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

Returns

| `Iterator`

See also

BinaryTreeNode.preorder
BinaryTreeNode.inorder
BinaryTreeNode.postorder

insert | () | method |

`public function insert(obj:*):void`

Inserts an item into the tree.

Parameters

| `obj:*` — The data.

isEmpty | () | method |

`public function isEmpty():Boolean`

Checks if the collection is empty.

Returns

| `Boolean` — True if empty, otherwise false.

remove | () | method |

`public function remove(node:BinaryTreeNode):void`

Removes a node from the BST.

Parameters

| `node:BinaryTreeNode` — The node to remove.

toArray | () | method |

`public function toArray():Array`

Converts the collection into an array.

Returns

| `Array` — An array.

toString | () | method |

`public function toString():String`

Prints out a string representing the current object.

Returns

| `String` — A string representing the current object.

Thu Jan 16 2014, 01:11 PM +08:00