sorted_binary_tree

class SortedBinaryTree < Object

A sorted binary tree, also known as a binary search tree.

Public Methods

default

default=

initialize(hash=nil)

Create a new SortedBinaryTree. TODO: Should a Hash be used to create the tree, or should a set of [key => value]* objects be used, like with Hash itself? Would this be possible?

hash	a hash with which to initialize the tree.

self.[](hash=nil)

Construct a Sorted BinaryTree from a Hash (or any other data structure with an each method that iterates through key/value pairs).

Returns: a new BinaryTree containing the data from Hash.

[](key, node=@tree.root)

Retrieve an element from the tree.

Returns: the element associated with key, or @default if there is no such key.

fetch(key, default=NIL, node=@tree.root)

[]=(key, value)

Insert a new element into the tree. If there is already an element in the tree with the given key, then the given key/value pair will replace the element.

Returns: the value that was inserted.

store

store is an alias for []=.

first

last

each(node=@tree.root, &block)

each_pair

each_pair is an alias for each.

reverse_each(node=@tree.root, &block)

reverse_each_pair

reverse_each_pair is an alias for reverse_each.

clear()

empty?()

size()

length

length is an alias for size.

clone()

Protected Methods

tree

tree=

Private Methods

__find__(key, node)

Given a key, find a node associated with that key.

the	key to search for.

Returns: the node associated with key.

Constants

NIL

Mixins

Enumerable
Comparable
EnumerableContainer
PairEnumerableContainer
PairUpdatableContainer
IndexableContainer

Constants

BinarySearchTree

class BinarySearchTree < Object

BinarySearchTree is an alternative name for SortedBinaryTree.

Requires