announcements‎ > ‎

### 2016-04-14

posted Apr 14, 2016, 8:38 AM by Samuel Konstantinovich   [ updated Apr 14, 2016, 8:47 AM ]
 Goal: More Binary TreesBalanced Tree Definition:  All subtrees heights differ by no more than 1, and all subtrees are balanced.IMAGEIMAGEIMAGEVarious components that will be in our garbage binary tree: (don't write any of these)TreeNode{ //what goes here?}TreeNode.java-getData() (maybe) setData... but making a new node to replace it works too. -getLeft() -setLeft() -getRight() -setRight()//If the tree is tally based rather than storing duplicates:-getCount() -setCount()                                      BTree{ add(T data) //wrapper that calls the recursive add function add(TreeNode,T data) // if there is space: add it   // otherwise, move on to the next child}ADD LOGIC:    if (null) → new root    if (root does not have two children) → add to the null spot    else → add to one of the subtrees using recursive add(root,value)how to pick which child?-randomly -the shorter heightThe height of the tree is log n. Ideally, the add function is O(log n) and the worst case scenario is O(n). How do we print these trees? Traversals!Tree Transversals - O(n) IMAGEExamples:        IMAGE        IMAGEVCLCR= 5 6 8 9 7 1 2   (Pre-Order)CLCRV= 8 9 6 1 2 7 5   (Post-Order)CLVCR= 8 6 9 5 1 7 2   (In-Order)V=Value CL=Left Child CR=Right Child