Package algs33

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

java.lang.Object

algs33.XRandomizedBST<K,V>

All Implemented Interfaces:

Iterable<K>

public class XRandomizedBST<K extends Comparable<? super K>,V>
extends Object
implements Iterable<K>

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor	Description
XRandomizedBST()

Method Summary

Modifier and Type	Method	Description
private XRandomizedBST.Node<K,V>	ceil(XRandomizedBST.Node<K,V> x, K key, XRandomizedBST.Node<K,V> best)
K	ceil(K key)
K	ceil2(K key)
boolean	check()
private boolean	checkCount()
private boolean	checkCount(XRandomizedBST.Node<K,V> x)
boolean	contains(K key)
private boolean	eq(K k1, K k2)
private void	fix(XRandomizedBST.Node<K,V> x)
private V	get(XRandomizedBST.Node<K,V> x, K key)
V	get(K key)
int	height()
private int	height(XRandomizedBST.Node<K,V> x)
private boolean	isBST()
private boolean	isBST(XRandomizedBST.Node<K,V> x, K min, K max)
Iterator<K>	iterator()
private XRandomizedBST.Node<K,V>	joinLR(XRandomizedBST.Node<K,V> a, XRandomizedBST.Node<K,V> b)
private boolean	less(K k1, K k2)
static void	main(String[] args)
K	max()
K	min()
private XRandomizedBST.Node<K,V>	put(XRandomizedBST.Node<K,V> x, K key, V val)
void	put(K key, V val)
private XRandomizedBST.Node<K,V>	putRoot(XRandomizedBST.Node<K,V> x, K key, V val)
private XRandomizedBST.Node<K,V>	remove(XRandomizedBST.Node<K,V> x, K key)
V	remove(K key)
private XRandomizedBST.Node<K,V>	rotL(XRandomizedBST.Node<K,V> h)
private XRandomizedBST.Node<K,V>	rotR(XRandomizedBST.Node<K,V> h)
K	select(int k)
private XRandomizedBST.Node<K,V>	select(XRandomizedBST.Node<K,V> x, int k)
int	size()
private int	size(XRandomizedBST.Node<K,V> x)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

root

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

Constructor Details

XRandomizedBST

public XRandomizedBST()

Method Details

contains

public boolean contains(K key)

get

public V get(K key)

get

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

put

public void put(K key,
 V val)

put

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

putRoot

private XRandomizedBST.Node<K,V> putRoot(XRandomizedBST.Node<K,V> x,
 K key,
 V val)

joinLR

private XRandomizedBST.Node<K,V> joinLR(XRandomizedBST.Node<K,V> a,
 XRandomizedBST.Node<K,V> b)

remove

private XRandomizedBST.Node<K,V> remove(XRandomizedBST.Node<K,V> x,
 K key)

remove

public V remove(K key)

select

public K select(int k)

select

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

min

public K min()

max

public K max()

ceil

public K ceil(K key)

ceil

private XRandomizedBST.Node<K,V> ceil(XRandomizedBST.Node<K,V> x,
 K key,
 XRandomizedBST.Node<K,V> best)

ceil2

public K ceil2(K key)

iterator

public Iterator<K> iterator()

Specified by:

iterator in interface Iterable<K extends Comparable<? super K>>

size

public int size()

size

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

height

public int height()

height

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

fix

private void fix(XRandomizedBST.Node<K,V> x)

rotR

private XRandomizedBST.Node<K,V> rotR(XRandomizedBST.Node<K,V> h)

rotL

private XRandomizedBST.Node<K,V> rotL(XRandomizedBST.Node<K,V> h)

check

public boolean check()

checkCount

private boolean checkCount()

checkCount

private boolean checkCount(XRandomizedBST.Node<K,V> x)

isBST

private boolean isBST()

isBST

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

less

private boolean less(K k1,
 K k2)

eq

private boolean eq(K k1,
 K k2)

main

public static void main(String[] args)