Package algs32

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

java.lang.Object

algs32.BST<K,V>

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	BST.Node<K extends Comparable<? super K>,V>

Field Summary

Fields

Modifier and Type	Field	Description
private BST.Node<K,V>	root

Constructor Summary

Constructors

Constructor	Description
BST()

Method Summary

Modifier and Type	Method	Description
private BST.Node<K,V>	ceiling(BST.Node<K,V> x, K key)
K	ceiling(K key)
private boolean	check()
boolean	contains(K key)
private BST.Node<K,V>	delete(BST.Node<K,V> x, K key)
void	delete(K key)
void	deleteMax()
private BST.Node<K,V>	deleteMax(BST.Node<K,V> x)
void	deleteMin()
private BST.Node<K,V>	deleteMin(BST.Node<K,V> x)
void	drawTree()
private void	drawTree(BST.Node<K,V> n, double x, double y, double range, int depth)
private BST.Node<K,V>	floor(BST.Node<K,V> x, K key)
K	floor(K key)
private V	get(BST.Node<K,V> x, K key)
V	get(K key)
int	height()
private int	height(BST.Node<K,V> x)
private void	inOrder(BST.Node<K,V> x, Queue<K> q)
private void	inOrder(BST.Node<K,V> x, Queue<K> queue, K lo, K hi)
private boolean	isBST()
private boolean	isBST(BST.Node<K,V> x, K min, K max)
boolean	isEmpty()
private boolean	isRankConsistent()
private boolean	isSizeConsistent()
private boolean	isSizeConsistent(BST.Node<K,V> x)
Iterable<K>	keys()
Iterable<K>	keys(K lo, K hi)
Iterable<K>	levelOrder()
static void	main(String[] args)
K	max()
private BST.Node<K,V>	max(BST.Node<K,V> x)
K	min()
private BST.Node<K,V>	min(BST.Node<K,V> x)
private BST.Node<K,V>	put(BST.Node<K,V> x, K key, V val)
void	put(K key, V val)
int	rank(K key)
private int	rank(K key, BST.Node<K,V> x)
K	select(int k)
private BST.Node<K,V>	select(BST.Node<K,V> x, int k)
int	size()
private int	size(BST.Node<K,V> x)
int	size(K lo, K hi)
void	toGraphviz(String filename)
private void	toGraphviz(GraphvizBuilder gb, BST.Node<K,V> parent, BST.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

root

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

Constructor Details

BST

public BST()

Method Details

isEmpty

public boolean isEmpty()

size

public int size()

size

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

contains

public boolean contains(K key)

get

public V get(K key)

get

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

put

public void put(K key,
 V val)

put

private BST.Node<K,V> put(BST.Node<K,V> x,
 K key,
 V val)

deleteMin

public void deleteMin()

deleteMin

private BST.Node<K,V> deleteMin(BST.Node<K,V> x)

deleteMax

public void deleteMax()

deleteMax

private BST.Node<K,V> deleteMax(BST.Node<K,V> x)

delete

public void delete(K key)

delete

private BST.Node<K,V> delete(BST.Node<K,V> x,
 K key)

min

public K min()

min

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

max

public K max()

max

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

floor

public K floor(K key)

floor

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

ceiling

public K ceiling(K key)

ceiling

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

select

public K select(int k)

select

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

rank

public int rank(K key)

rank

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

keys

public Iterable<K> keys()

inOrder

private void inOrder(BST.Node<K,V> x,
 Queue<K> q)

keys

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

inOrder

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

size

public int size(K lo,
 K hi)

height

public int height()

height

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

levelOrder

public Iterable<K> levelOrder()

check

private boolean check()

isBST

private boolean isBST()

isBST

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

isSizeConsistent

private boolean isSizeConsistent()

isSizeConsistent

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

isRankConsistent

private boolean isRankConsistent()

toString

public String toString()

Overrides:

toString in class Object

toGraphviz

public void toGraphviz(String filename)

toGraphviz

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

drawTree

public void drawTree()

drawTree

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

main

public static void main(String[] args)