// // 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 }