Package algs33

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

java.lang.Object

algs33.XRedBlackLiteBST<K,V>

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

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor	Description
XRedBlackLiteBST()

Method Summary

Modifier and Type	Method	Description
private boolean	check()
boolean	contains(K key)
private void	flipColors(XRedBlackLiteBST.Node<K,V> h)
V	get(XRedBlackLiteBST.Node<K,V> x, K key)
V	get(K key)
int	height()
private int	height(XRedBlackLiteBST.Node<K,V> x)
private XRedBlackLiteBST.Node<K,V>	insert(XRedBlackLiteBST.Node<K,V> h, K key, V val)
private boolean	is23()
private boolean	is23(XRedBlackLiteBST.Node<K,V> x)
private boolean	isBalanced()
private boolean	isBalanced(XRedBlackLiteBST.Node<K,V> x, int black)
private boolean	isBST()
private boolean	isBST(XRedBlackLiteBST.Node<K,V> x, K min, K max)
boolean	isEmpty()
private boolean	isRed(XRedBlackLiteBST.Node<K,V> x)
Iterable<K>	keys()
private void	keys(XRedBlackLiteBST.Node<K,V> x, Queue<K> queue)
static void	main(String[] args)
K	max()
private K	max(XRedBlackLiteBST.Node<K,V> x)
K	min()
private K	min(XRedBlackLiteBST.Node<K,V> x)
void	put(K key, V val)
private XRedBlackLiteBST.Node<K,V>	rotateLeft(XRedBlackLiteBST.Node<K,V> h)
private XRedBlackLiteBST.Node<K,V>	rotateRight(XRedBlackLiteBST.Node<K,V> h)
int	size()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, 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 XRedBlackLiteBST.Node<K extends Comparable<? super K>,V> root

N

private int N

Constructor Details

XRedBlackLiteBST

public XRedBlackLiteBST()

Method Details

get

public V get(K key)

get

public V get(XRedBlackLiteBST.Node<K,V> x,
 K key)

contains

public boolean contains(K key)

put

public void put(K key,
 V val)

insert

private XRedBlackLiteBST.Node<K,V> insert(XRedBlackLiteBST.Node<K,V> h,
 K key,
 V val)

isRed

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

rotateRight

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

rotateLeft

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

flipColors

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

size

public int size()

isEmpty

public boolean isEmpty()

height

public int height()

height

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

min

public K min()

min

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

max

public K max()

max

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

keys

public Iterable<K> keys()

keys

private void keys(XRedBlackLiteBST.Node<K,V> x,
 Queue<K> queue)

check

private boolean check()

isBST

private boolean isBST()

isBST

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

is23

private boolean is23()

is23

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

isBalanced

private boolean isBalanced()

isBalanced

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

main

public static void main(String[] args)