announcements‎ > ‎

2016-04-14

posted Apr 14, 2016, 8:38 AM by Samuel Konstantinovich   [ updated Apr 14, 2016, 8:47 AM ]

Goal: More Binary Trees

Balanced Tree Definition:  All subtrees heights differ by no more than 1, and all subtrees are balanced.

IMAGE

IMAGE

IMAGE

Various components that will be in our garbage binary tree: (don't write any of these)

TreeNode<T>{

//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<T>{


add(T data) //wrapper that calls the recursive add function

add(TreeNode<T>,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 height




The 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)

IMAGE

Examples:

        IMAGE


        IMAGE

VCLCR= 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






Comments