Package algs33

Class RedBlackBST<K extends Comparable<? super K>,V>

java.lang.Object

algs33.RedBlackBST<K,V>

public class RedBlackBST<K extends Comparable<? super K>,V>
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	RedBlackBST.Node<K,V>

Field Summary

Fields

Modifier and Type	Field	Description
private static final boolean	BLACK
private static final boolean	RED
private RedBlackBST.Node<K,V>	root

Constructor Summary

Constructors

Constructor	Description
RedBlackBST()

Method Summary

Modifier and Type	Method	Description
private RedBlackBST.Node<K,V>	balance(RedBlackBST.Node<K,V> h)
private RedBlackBST.Node<K,V>	ceiling(RedBlackBST.Node<K,V> x, K key)
K	ceiling(K key)
private boolean	check()
private boolean	contains(RedBlackBST.Node<K,V> x, K key)
boolean	contains(K key)
private RedBlackBST.Node<K,V>	delete(RedBlackBST.Node<K,V> h, K key)
void	delete(K key)
void	deleteMax()
private RedBlackBST.Node<K,V>	deleteMax(RedBlackBST.Node<K,V> h)
void	deleteMin()
private RedBlackBST.Node<K,V>	deleteMin(RedBlackBST.Node<K,V> h)
void	drawTree()
private void	drawTree(RedBlackBST.Node<K,V> n, double x, double y, double range, int depth)
private void	flipColors(RedBlackBST.Node<K,V> h)
private RedBlackBST.Node<K,V>	floor(RedBlackBST.Node<K,V> x, K key)
K	floor(K key)
private V	get(RedBlackBST.Node<K,V> x, K key)
V	get(K key)
int	height()
private int	height(RedBlackBST.Node<K,V> x)
private boolean	is23()
private boolean	is23(RedBlackBST.Node<K,V> x)
private boolean	isBalanced()
private boolean	isBalanced(RedBlackBST.Node<K,V> x, int black)
private boolean	isBST()
private boolean	isBST(RedBlackBST.Node<K,V> x, K min, K max)
boolean	isEmpty()
private boolean	isRankConsistent()
private boolean	isRed(RedBlackBST.Node<K,V> x)
private boolean	isSizeConsistent()
private boolean	isSizeConsistent(RedBlackBST.Node<K,V> x)
Iterable<K>	keys()
private void	keys(RedBlackBST.Node<K,V> x, Queue<K> queue, K lo, K hi)
Iterable<K>	keys(K lo, K hi)
private Iterable<RedBlackBST.Node<K,V>>	levelOrderNodes()
static void	main(String[] args)
K	max()
private RedBlackBST.Node<K,V>	max(RedBlackBST.Node<K,V> x)
K	min()
private RedBlackBST.Node<K,V>	min(RedBlackBST.Node<K,V> x)
private RedBlackBST.Node<K,V>	moveRedLeft(RedBlackBST.Node<K,V> h)
private RedBlackBST.Node<K,V>	moveRedRight(RedBlackBST.Node<K,V> h)
private RedBlackBST.Node<K,V>	put(RedBlackBST.Node<K,V> h, K key, V val)
void	put(K key, V val)
int	rank(K key)
private int	rank(K key, RedBlackBST.Node<K,V> x)
private RedBlackBST.Node<K,V>	rotateLeft(RedBlackBST.Node<K,V> h)
private RedBlackBST.Node<K,V>	rotateRight(RedBlackBST.Node<K,V> h)
K	select(int k)
private RedBlackBST.Node<K,V>	select(RedBlackBST.Node<K,V> x, int k)
int	size()
private int	size(RedBlackBST.Node<K,V> x)
int	size(K lo, K hi)
void	toGraphviz(String filename)
private void	toGraphviz(GraphvizBuilder gb, RedBlackBST.Node<K,V> parent, RedBlackBST.Node<K,V> n)
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

RED

private static final boolean RED

See Also:

• Constant Field Values

BLACK

private static final boolean BLACK

See Also:

• Constant Field Values

root

private RedBlackBST.Node<K extends Comparable<? super K>,V> root

Constructor Details

RedBlackBST

public RedBlackBST()

Method Details

isRed

private boolean isRed(RedBlackBST.Node<K,V> x)

size

private int size(RedBlackBST.Node<K,V> x)

size

public int size()

isEmpty

public boolean isEmpty()

get

public V get(K key)

get

private V get(RedBlackBST.Node<K,V> x,
 K key)

contains

public boolean contains(K key)

contains

private boolean contains(RedBlackBST.Node<K,V> x,
 K key)

put

public void put(K key,
 V val)

put

private RedBlackBST.Node<K,V> put(RedBlackBST.Node<K,V> h,
 K key,
 V val)

deleteMin

public void deleteMin()

deleteMin

private RedBlackBST.Node<K,V> deleteMin(RedBlackBST.Node<K,V> h)

deleteMax

public void deleteMax()

deleteMax

private RedBlackBST.Node<K,V> deleteMax(RedBlackBST.Node<K,V> h)

delete

public void delete(K key)

delete

private RedBlackBST.Node<K,V> delete(RedBlackBST.Node<K,V> h,
 K key)

rotateRight

private RedBlackBST.Node<K,V> rotateRight(RedBlackBST.Node<K,V> h)

rotateLeft

private RedBlackBST.Node<K,V> rotateLeft(RedBlackBST.Node<K,V> h)

flipColors

private void flipColors(RedBlackBST.Node<K,V> h)

moveRedLeft

private RedBlackBST.Node<K,V> moveRedLeft(RedBlackBST.Node<K,V> h)

moveRedRight

private RedBlackBST.Node<K,V> moveRedRight(RedBlackBST.Node<K,V> h)

balance

private RedBlackBST.Node<K,V> balance(RedBlackBST.Node<K,V> h)

height

public int height()

height

private int height(RedBlackBST.Node<K,V> x)

min

public K min()

min

private RedBlackBST.Node<K,V> min(RedBlackBST.Node<K,V> x)

max

public K max()

max

private RedBlackBST.Node<K,V> max(RedBlackBST.Node<K,V> x)

floor

public K floor(K key)

floor

private RedBlackBST.Node<K,V> floor(RedBlackBST.Node<K,V> x,
 K key)

ceiling

public K ceiling(K key)

ceiling

private RedBlackBST.Node<K,V> ceiling(RedBlackBST.Node<K,V> x,
 K key)

select

public K select(int k)

select

private RedBlackBST.Node<K,V> select(RedBlackBST.Node<K,V> x,
 int k)

rank

public int rank(K key)

rank

private int rank(K key,
 RedBlackBST.Node<K,V> x)

keys

public Iterable<K> keys()

keys

public Iterable<K> keys(K lo,
 K hi)

keys

private void keys(RedBlackBST.Node<K,V> x,
 Queue<K> queue,
 K lo,
 K hi)

size

public int size(K lo,
 K hi)

check

private boolean check()

isBST

private boolean isBST()

isBST

private boolean isBST(RedBlackBST.Node<K,V> x,
 K min,
 K max)

isSizeConsistent

private boolean isSizeConsistent()

isSizeConsistent

private boolean isSizeConsistent(RedBlackBST.Node<K,V> x)

isRankConsistent

private boolean isRankConsistent()

is23

private boolean is23()

is23

private boolean is23(RedBlackBST.Node<K,V> x)

isBalanced

private boolean isBalanced()

isBalanced

private boolean isBalanced(RedBlackBST.Node<K,V> x,
 int black)

levelOrderNodes

private Iterable<RedBlackBST.Node<K,V>> levelOrderNodes()

toString

public String toString()

Overrides:

toString in class Object

toGraphviz

public void toGraphviz(String filename)

toGraphviz

private void toGraphviz(GraphvizBuilder gb,
 RedBlackBST.Node<K,V> parent,
 RedBlackBST.Node<K,V> n)

drawTree

public void drawTree()

drawTree

private void drawTree(RedBlackBST.Node<K,V> n,
 double x,
 double y,
 double range,
 int depth)

main

public static void main(String[] args)