Add a method to RedBlackBST to print a RB-BST indexing the
subnodes.
Test the tree inserting element by element and printing the results
with (1) S E A R C H E X A M P L E (where the value is the index of
the letter in the initial word) and (2) K R I S T E N
public class RedBlackBST<Key extends Comparable<Key>,
Value>
{
private Node root;
private class Node // BST node with color bit (see page 433)
private boolean isRed(Node h) // See page 433.
private Node rotateLeft(Node h) // See page 434.
private Node rotateRight(Node h) // See page 434.
private void flipColors(Node h) // See page 436.
private int size() // See page 398.
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if
new.
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val)
{
if (h == null) // Do standard insert, with red link to
parent.
return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if (isRed(h.right) && !isRed(h.left)) h =
rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h =
rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
}
import java.util.NoSuchElementException;
public class RedBlackBST<Key extends Comparable<Key>, Value> { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; // root of the BST // BST helper node data type private class Node { private Key key; // key private Value val; // associated data private Node left, right; // links to left and right subtrees private boolean color; // color of parent link private int size; // subtree count public Node(Key key, Value val, boolean color, int size) { this.key = key; this.val = val; this.color = color; this.size = size; } } /** * Initializes an empty symbol table. */ public RedBlackBST() { } /*************************************************************************** * Node helper methods. ***************************************************************************/ // is node x red; false if x is null ? private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; } // number of node in subtree rooted at x; 0 if x is null private int size(Node x) { if (x == null) return 0; return x.size; } /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */ public int size() { return size(root); } /** * Is this symbol table empty? * @return {@code true} if this symbol table is empty and {@code false} otherwise */ public boolean isEmpty() { return root == null; }
public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } root = put(root, key, val); root.color = BLACK; // assert check(); } // insert the key-value pair in the subtree rooted at h private Node put(Node h, Key key, Value val) { if (h == null) return new Node(key, val, RED, 1); int cmp = key.compareTo(h.key); if (cmp < 0) h.left = put(h.left, key, val); else if (cmp > 0) h.right = put(h.right, key, val); else h.val = val; // fix-up any right-leaning links if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.size = size(h.left) + size(h.right) + 1; return h; }
Get Answers For Free
Most questions answered within 1 hours.