Skip to content

Latest commit

 

History

History
108 lines (77 loc) · 3.44 KB

ex05.md

File metadata and controls

108 lines (77 loc) · 3.44 KB
Raw

Exercise 05

Part A

Write a class called BinaryTreeLeftMaxDelete that does extend MyMapBinarySearchTree. In such class, override the method:

protected TreeNode delete(K key, TreeNode subtreeRoot)

When a node with two children needs to be deleted, instead of replacing it with the min value from the right-subtree, do use the max value from the left-subtree.

Write a test class BinaryTreeLeftMaxDeleteTest that extends MyMapBinarySearchTreeTest, in which you override the method getTreeInstance() to use an instance of BinaryTreeLeftMaxDelete. If your implementation is correct, all tests should pass.

Part B

Write a class called TernaryTreeMap that implements MyMapTreeBased. This class should be similar to MyMapBinarySearchTree, but with a major difference: each node contains two elements (first and second), instead of just one, and three children (left, middle and right). Their ordering relation should be left < first < middle < second < right.

Write a test class called TernaryTreeMapTest that extends MyMapTestTemplate. If your implementation of TernaryTreeMap is correct, then all tests should pass. Similarly to MyMapBinaryTreeTest, add these further new tests:

  • Add 2 distinct elements in a way that the tree depth is only 1 (ie, best case for 2 insertions).
  • Add 3 distinct elements in a way that the tree depth is 3 (ie, worst case for 3 insertions).
  • Add 8 distinct elements in a way that the tree depth is only 2 (ie, best case for 8 insertions).

Part C

Study the source code of MyMapBinarySearchTree. Once you think you fully understand it, write its implementation on paper (e.g., using a pen), without looking at the source code. Once done, compare what you wrote with the actual implementation.

Part D

Write a class called DrawRedBlackTreeMap that extends MyMapRedBlackTree. You need to provide a new method public void draw() that can draw the tree on the standard output. For each node, you should print the key, not the value. Red nodes should be within (), whereas black nodes in []. Following is an example of a printed tree with 5 nodes:

         [5]
        /   \
       /     \
    (3)       [6]
   /   \         
[2]    [4]

When you are implementing the draw() function, you can make the following assumptions:

  • keys are printed with just 1 char (eg, digits from 0 to 9)
  • the depth of the tree will be at most 3 (as in the above example)

In other words, you do not need to write a function that can draw any kind of tree, but just the ones within those constrains (which will make the implementation of draw() much easier).

Write a main method in which you instantiate such tree, and add one element at a time, in an order in which these shapes are obtained:

1) [?]


2)    [?]
     /    
   (?)
   

3)   [?]
    /   \
  [?]   [?]   


4)      [?]
       /   \
      /     \
   [?]       [?]
            /   
          (?)   

5)         [?]
          /   \
         /     \
      (?)       [?]
     /   \         
  [?]    [?]

Note: in the above printed output I replace the keys with a ? placeholder. It is your job to find the right 5 values for which, once inserted, you go through those tree shapes, until the final one.

Solutions

Solutions to this exercise can be found in the solutions module, under the org.pg4200.sol05 package.