Top Down Insertion for Red-Black Trees
To get started, import the starter file, RBTree.java, into the trees package you create in a new Java Project. You CANNOT modify the inner Node class that contains information about the nodes of the binary trees. Please do not change any of the method signatures in the RBTree class, but you are free to add additional helper methods.
Part 1: Top Down Insertion for Red-Black Trees
public boolean insert(Integer i)
This method should use a top down insertion strategy (see below) to insert a Node with data equal to i into the Red-Black Tree provided that a Node with data equal to i does
not already exist in the Red-Black Tree (i.e., no duplicate data). If the node is successfully inserted, return true, otherwise return false (tried to insert a duplicate element).
For the first part of the assignment, you will implement a top-down insertion for a
red-black tree. Basically the idea is to do the recoloring and rotations on the way down instead of after you insert the node. Node that the node to be inserted is always red, you may need to do one final rotation after inserting the node if its parent is red. Note that in this version of the red-black tree, we do not have parent pointers in our Node class. You cannot add a parent pointer to the node class or do additional tree traversals to find parent nodes. You will need to use a Stack to keep track of the ancestors in order to perform the correct rotations.
This is the situation you need to handle on your way down the tree.
Situation: A black node with two red children. Action: - Recolor the node red and the children black. - If the parent is red, perform rotations, otherwise continue down the tree
If the color flip produces a red node with a red child, then perform a single or double rotation depending on the following…
- If the two red nodes are both left children or both right children, perform a single rotation (see example below)
- Otherwise, perform a double rotation (see example below)
Part 2: Other methods on Red-Black Trees
public int height()
This method returns the height of the red-black tree. The height is defined as the longest path from the root to a leaf node. Note that the root has a height of 1.
public int blackHeight()
This method returns the height of the black height of red-black tree. The height black is defined as the number of black nodes from a given node to a leaf node (the NIL node). Note that we do not count the current node in the black height, but we do count the NIL leaf node (e.g. the black height of the root in the red-black tree below is 2). This method can be helpful when testing your insert method to make sure that you do not violate the fifth property of red black trees.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
