A08- Balanced Search Tree

A08-PA1 Create Balanced Search Trees

Task 1: Create all balanced search trees with a given size(drawing)

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 1 for instructions
• 11. Create all balanced search trees templates (structures) with a size of 9 (for letters from A to I) Drawing only No coding

Task 2: Create a balanced search trees for a given input sequence(drawing)

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 2 for instructions
• 21. Create a balanced search tree (2-3 tree) for the input sequence given by the first 10 distinct letters of your first name followed by last name, preffered color(s) and food items (different for each student). Drawing only No coding

Task 3: Represent a balanced 2-3 search tree

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 3 for the code
• 31. Implement the representation for a balanced 2-3 search tree

Task 4: Analyze the represention of a balanced 2-3 search tree (Analysis writing no coding)

• 41. Analyze the previous implementation. How easy will be to implement the processing methods? Why is easy? Why is hard?

Submission:

• A ZIP file containing all Java files in the package a051 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
• A PDF file with the new source code that you wrote included as text (not screenshots).
• A PDF file with the answers to the enclosed questions

A08-PA2 Create Red-Black BST

Task 1: Create all red-black balanced search trees with a given size based on the 2-3 tree

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 4 for instructions

• 11. Create all red-black balanced search trees templates (structures) with a size of 6 (for letters from A to F) Drawing only No coding

Task 2: Create a red-black balanced search trees for a given input sequence

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 5 for instructions

• 21. Create a red-black balanced search tree for the input sequence given by the first 10 distinct letters of your lsst name followed by first name, preffered singer name(s). Drawing only No coding

Task 3: Represent a red-black BST

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 6 for the code
• 31. Implement the representation for a red-black BST

Task 4: Analyze the represention of a red-black BST (Analysis writing no coding)

• 41. Analyze the previous implementation. Compare it with the 2-3 representation. Why is better? Why is worse?
• 42. How easy will be to implement the processing methods? Why is easy? Why is hard?

Submission:

• A ZIP file containing all Java files in the package a051 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
• A PDF file with the new source code that you wrote included as text (not screenshots).
• A PDF file with the answers to the enclosed questions

A08-PA3 Insert in Red-Black BST

Task 1: Insert a sequence of keys in a red-black BST

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 7 for instructions
• 11. Create a red-black BST with the distinct letters of the name of your best friend (without duplications in order in which they appear in the name). Identify alll basic operations that you perform. You can draw on paper and post a PDF with the pictures or using a drawing program.Drawing only No coding

Task 2: Implementation for inserting a node in a red-black BST

• LEARN:
  • Watch the demo from the lecture (if not present in class)
  • Slides: Attachment 8 for instructions and code
• 21. Create the implementation for adding a node to a red-black BST as described above Drawing
• 22. Create a test program for the insertion (an example provided) coding
• 23. Test your code with the input: N U M B E R
• 24. Test your code with the input from 11, and check if you obtained the same result.

Submission:

• A ZIP file containing all Java files in the package a051 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
• A PDF file with the new source code that you wrote included as text (not screenshots).
• A PDF file with the answers to the enclosed questions