pdj555 / java-2-cp8

Class Notes Week 10

Tree in Java

• like a root
• top element represents base of tree
• tips of tree are called leaves

Automatic Maintaining of Tree

• based on compareTo method
• smaller things go on the left, larger on the right

When to use

• NOT when there are a lot of insertion and deletions; hashmap would be better
• very application specific

Creating of Tree

• Tree root is changed for optimization
• logN

Weighted Graph for finding the shortest route

Recurcion

• used to as a good way to reuse code
• not always appicable
• similar to tree sorting
• breaking down until there is just two elements
• On final exam
• essential parts:
  • Base Case: problem can be solved with one step
  • Recursive Case: gets problem to point where it can be solved with one step
• can be used to sort arrays
  • https://www.bigocheatsheet.com/

Steps to use recursion

• know when to stop/when the problem is solved
• how to break it apart
• how to bring it together

Recurcion Example

• hogs memory
• things get stuck at the bottom of the stack

Next Exam

• Java Collections Framework