//

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

}

}