edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree Class Reference
[Examples]

Collaboration diagram for edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree:

[legend]

List of all members.

Classes
class	Node
Package Functions
	RedBlackTree ()
void	clear ()
Node	search (int k)
Node	searchGTE (int k)
Node	searchLTE (int k)
Node	predecessor (Node node)
Node	successor (Node node)
Node	minAll ()
Node	maxAll ()
void	replace (Node o, Node n)
void	insert (Node z)
void	delete (Node z)
Package Attributes
Node	root
Static Package Attributes
static final boolean	BLACK = true
static final boolean	RED = false

---

Detailed Description

Case study of Red-Black trees with integer keys. Stripped down and simplified.

Author:

Kuat Yessenov A tree with integer keys.

Emina Torlak

Definition at line 35 of file RedBlackTree.java.

---

Constructor & Destructor Documentation

edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.RedBlackTree

(

)

[package]

Creates an empty IntTree.

Definition at line 50 of file RedBlackTree.java.

---

Member Function Documentation

void edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.clear

(

)

[package]

Discards all elements from this tree.

Definition at line 58 of file RedBlackTree.java.

void edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.delete

(

Node

z

)

[package]

A slightly modified implementation of the CLR deletion algorithm. requires z in this.nodes effects this.nodes' = this.nodes - z

Definition at line 185 of file RedBlackTree.java.

void edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.insert

(

Node

z

)

[package]

Implementation of the CLR insertion algorithm.

Definition at line 174 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.maxAll

(

)

[package]

Returns the node with the largest key. return key.(max(this.nodes.key))

Definition at line 143 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.minAll

(

)

[package]

Returns the node with the smallest key. return key.(min(this.nodes.key))

Definition at line 134 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.predecessor

(

Node

node

)

[package]

Implementation of the tree-predecessor algorithm from CLR. Returns the given node's predecessor, if it exists. Otherwise returns null. return the given node's predecessor throws NullPointerException - node = null

Definition at line 109 of file RedBlackTree.java.

void edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.replace	(	Node	o,
		Node	n
	)			[package]

Replaces the old node, o, with the given new node, n, in this tree.

Definition at line 161 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.search

(

int

k

)

[package]

Returns the node with the given key, or null no such node exists. return

Definition at line 67 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.searchGTE

(

int

k

)

[package]

Returns the node whose key is the ceiling of k in this tree, or null if no such node exists.

Definition at line 78 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.searchLTE

(

int

k

)

[package]

Returns the node whose key is the floor of k in this tree, or null if no such node exists. return {n: this.nodes | n.key <= k && no n': this.nodes - n | n'.key <= k && n'.key > n.key }

Definition at line 92 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.successor

(

Node

node

)

[package]

Implementation of the tree-successor algorithm from CLR. Returns the given node's successor, if it exists. Otherwise returns null.

Definition at line 125 of file RedBlackTree.java.

---

Member Data Documentation

final boolean edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.BLACK = true [static, package]

Definition at line 37 of file RedBlackTree.java.

final boolean edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.RED = false [static, package]

Definition at line 38 of file RedBlackTree.java.

Node edu.mit.csail.sdg.squander.examples.rbt.RedBlackTree.root [package]

Definition at line 44 of file RedBlackTree.java.

---

The documentation for this class was generated from the following file:

• examples/edu/mit/csail/sdg/squander/examples/rbt/RedBlackTree.java