//
// LLRB — L(eft)-L(eaning) R(ed)-B(lack) BST
//
// This class stores a set of integer keys using a left-leaning red-black BST
//
// HOMEWORK in this file is to implement:
//
// 1) public void insert()
// 2) public boolean containsRightRedEdge()
// 3) public boolean containsConsecutiveLeftRedEdges()
// 4) public int countBlackEdgesOnLeftmostPath()
// 5) public boolean sameBlackEdgesCountOnAllPaths(int count)
//
// As BONUS, there is one additional method to implement
//
// 1) public void fixLLRB()
//
package hw4;
public class LLRB {
private static final boolean RED = true;
private static final boolean BLACK = false;
public Node root;
public class Node {
public int key;
public boolean color;
public Node left, right;
public Node(int key, boolean color) {
this.key = key;
this.color = color;
}
}
// Constructor for LLRB
public LLRB() {
}
// Is parent link for node x red? false if x is null
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
// Inserts a key without fixing the tree
public void bstInsert(int key) {
root = bstInsert(root, key);
}
// Recursive helper method for bstInsert
private Node bstInsert(Node x, int key) {
if (x == null) return new Node(key, RED);
if (key < x.key) x.left = bstInsert(x.left, key);
else if (key > x.key) x.right = bstInsert(x.right, key);
return x;
}
// Inserts a key fixing the red-black tree property
public void insert(int key) {
// TODO : complete this method
}
// Checks whether the tree contains a red right edge
public boolean containsRightRedEdge() {
// TODO : complete this method
return false;
}
// Checks whether the tree contains two left red edges in a row
public boolean containsConsecutiveLeftRedEdges() {
// TODO : complete this method
return false;
}
// Returns the maximum number of black edges (nodes) on any path from root to null
public int maxBlackEdgesDepth() {
// TODO : complete this method
return 0;
}
// Returns the minimum number of black edges (nodes) on any path from root to null
public int minBlackEdgesDepth() {
// TODO : complete this method
return 0;
}
// Checks whether the BST is a valid left leaning red-black tree
public boolean isValidLLRB() {
return (maxBlackEdgesDepth() == minBlackEdgesDepth() &&
!containsRightRedEdge() &&
!containsConsecutiveLeftRedEdges());
}
// Fixes the red-black tree if there is something to fix
public void fixLLRB() {
// TODO : complete this method
}
}
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
