Package algs32

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

java.lang.Object

algs32.XBSTWithNonStaticNode<K,V>

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	XBSTWithNonStaticNode.Node

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor	Description
XBSTWithNonStaticNode()

Method Summary

Modifier and Type	Method	Description
private XBSTWithNonStaticNode<K,V>.Node	ceiling(XBSTWithNonStaticNode<K,V>.Node x, K key)
K	ceiling(K key)
private boolean	check()
boolean	contains(K key)
private XBSTWithNonStaticNode<K,V>.Node	delete(XBSTWithNonStaticNode<K,V>.Node x, K key)
void	delete(K key)
void	deleteMax()
private XBSTWithNonStaticNode<K,V>.Node	deleteMax(XBSTWithNonStaticNode<K,V>.Node x)
void	deleteMin()
private XBSTWithNonStaticNode<K,V>.Node	deleteMin(XBSTWithNonStaticNode<K,V>.Node x)
private XBSTWithNonStaticNode<K,V>.Node	floor(XBSTWithNonStaticNode<K,V>.Node x, K key)
K	floor(K key)
private V	get(XBSTWithNonStaticNode<K,V>.Node x, K key)
V	get(K key)
int	height()
private int	height(XBSTWithNonStaticNode<K,V>.Node x)
private boolean	isBST()
private boolean	isBST(XBSTWithNonStaticNode<K,V>.Node x, K min, K max)
boolean	isEmpty()
private boolean	isRankConsistent()
private boolean	isSizeConsistent()
private boolean	isSizeConsistent(XBSTWithNonStaticNode<K,V>.Node x)
Iterable<K>	keys()
private void	keys(XBSTWithNonStaticNode<K,V>.Node x, Queue<K> queue, K lo, K hi)
Iterable<K>	keys(K lo, K hi)
static void	main(String[] args)
K	max()
private XBSTWithNonStaticNode<K,V>.Node	max(XBSTWithNonStaticNode<K,V>.Node x)
K	min()
private XBSTWithNonStaticNode<K,V>.Node	min(XBSTWithNonStaticNode<K,V>.Node x)
private XBSTWithNonStaticNode<K,V>.Node	put(XBSTWithNonStaticNode<K,V>.Node x, K key, V val)
void	put(K key, V val)
int	rank(K key)
private int	rank(K key, XBSTWithNonStaticNode<K,V>.Node x)
K	select(int k)
private XBSTWithNonStaticNode<K,V>.Node	select(XBSTWithNonStaticNode<K,V>.Node x, int k)
int	size()
private int	size(XBSTWithNonStaticNode<K,V>.Node x)
int	size(K lo, K hi)

Methods inherited from class java.lang.Object

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

Field Details

root

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

Constructor Details

XBSTWithNonStaticNode

public XBSTWithNonStaticNode()

Method Details

isEmpty

public boolean isEmpty()

size

public int size()

size

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

contains

public boolean contains(K key)

get

public V get(K key)

get

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

put

public void put(K key,
 V val)

put

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

deleteMin

public void deleteMin()

deleteMin

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

deleteMax

public void deleteMax()

deleteMax

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

delete

public void delete(K key)

delete

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

min

public K min()

min

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

max

public K max()

max

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

floor

public K floor(K key)

floor

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

ceiling

public K ceiling(K key)

ceiling

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

select

public K select(int k)

select

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

rank

public int rank(K key)

rank

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

keys

public Iterable<K> keys()

keys

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

keys

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

size

public int size(K lo,
 K hi)

height

public int height()

height

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

check

private boolean check()

isBST

private boolean isBST()

isBST

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

isSizeConsistent

private boolean isSizeConsistent()

isSizeConsistent

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

isRankConsistent

private boolean isRankConsistent()

main

public static void main(String[] args)