Lab 3 - Trees - COMP2100/6442 Skip navigation COMP2100/6442 ANU College of Engineering & Computer Science Search query Search ANU web, staff & maps Search COMP2100/6442 Exams menu Search query Search ANU web, staff & maps Search Search COMP2100/6442 labs Overview Lab 1 - Install Lab 2 - Git / SSH Lab 3 - Trees Lab 4 - Parser Lab 5 - Android 1 Lab 6 - Android 2 Lab 7 - Persistent Data Lab 8 - PHP Lab 9 - Lab Test 1 Lab Test 2 related sites Wattle Lab 3 - Trees Task 1 - Binary Search Tree [0.5 marks] The main objective of this part is to understand how to insert and delete nodes in a Binary Search Tree (BST). The partial code for this part could be found here. Go through and read the file BinaryTree.java. It is just a simple abstract class for a BST. Go through the implementation of EmptyBinaryTree.java and NonEmptyBinaryTree.java which inherit BinaryTree class. We use a recursive definition of binary search tree in this implementation. A tree consist of 1) root node 2) left sub-tree (which is again a tree), and 3) right sub-tree (which is again a tree). Implement the method insert() in NonEmptyBinaryTree.java. Implement the method delete() in NonEmptyBinaryTree.java. If the target node, which we want to delete, has two children, replace the target node its successor in its descendant (See lecture slides for details). Use BinaryTreeTest.java to check whether your implementation is correct or not. Use the provided test code to check the correctness of your implementation. Please be aware that we may use additional test cases to verify of your code. Please implement your code within a block indicated by comments; ‘YOUR CODE STARTS HERE’ and ‘YOUR CODE ENDS HERE’ for each task. Task 2 - Red-Black Tree [0.5 marks] Red-Black Tree (R-B Tree) is a special Binary Search Tree (BST). It has all the properties of BST and some extras. For each node of the R-B Tree, it stores a color, it should only be red or black. Here are some properties of R-B Trees: Each node should be either black or red. The root node should be black. The null leaf node should be black. For each red node, its children nodes must be black. Each node should have the same number of black nodes from itself to all its children. The main objective of this part is to implement the insert part of the red-black tree. The code for this part could be found here. Read the code in ‘RedBlackTree.java’, implement your insert() method and try your code with the ‘RBTreeTest.java’. Note that to complete insert() function, you also need to implement rotateRight() correctly. Use the provided test code to check the correctness of your implementation. Please be aware that we may use additional test cases to verify of your code. Please implement your code within a block indicated by comments; ‘YOUR CODE STARTS HERE’ and ‘YOUR CODE ENDS HERE’ for each task. Submission Guideline Assignment deadline: 30 March (Monday) 9:00am Submission mode: Electronic, via Wattle (Lab 3) Submission format (IMPORTANT): Upload your final version of NonEmptyBinaryTree.java (for task 1) and RBTree.java (for task 2) to Wattle. Do not change file name. Do not upload any other files. Do not upload a folder (your submission should be two java files). The answers will be marked by an automated marker. Do not change the structure of the source code including class name, package structure, etc. You are only allowed to edit the designated code segment indicated in the comments. Do not import packages outside of the standard java SE package. The list of available packages can be found here: https://docs.oracle.com/en/java/javase/12/docs/api/index.html Violation of the submission format will have their assignment not evaluated by an autograder and get zero marks. Reference: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) Chap. 13. Updated: / Responsible Officer: / Page Contact: Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future
