name: inverse layout: true class: taylor msoe --- class: center, middle .title[ # Trees ## A non-linear data structure ] ??? * **P** speaker view * **C** clone slideshow * **?** help --- # Tree Data Structure * Consists of zero or more nodes -- * The **root** node is the entry point into the structure -- * Each node can have zero or more children -- - Binary trees limit each node to no more than two children -- - Binary **search** trees require: + Left child less than parent + Right child greater than parent --- # Terminology .left-column[
] .right-column[ * node * root * subtree * parent * left child * right child * leaf * height: 2 * book height: 3 ] --- # Terminology - Perfect Tree .left-column[
] .right-column[ All but bottom-level nodes have two children ] --- # Terminology - Complete Tree .left-column[
] .right-column[ Almost perfect: may be missing right-most nodes from bottom level ] --- # Terminology - Full Tree .left-column[
All nodes have zero or two children. ] .right-column[
] --- # Recursive Structure * Each child node represents a subtree -- * Most methods implemented via recursion -- - Expose non-recursive method that calls `private` recursive method -- ``` public int size() { return size(root); } private int size(Node
subroot) { return subroot == null ? 0 : 1 + size(subroot.lKid) + size(subroot.rKid); } ``` --- # Binary Search Tree Superpower * For a perfect binary search tree, `contains()` takes $O(\log n)$ time -- * Works because we eliminate half the data each step down a branch of the tree -- .left-column[ * Perfect tree is not needed * Balanced tree still gives us $O(\log n)$ time * Balanced: distance from root to any leaf differs by no more than a constant multiple ] .right-column[
] --- # Tip on $O()$ * $O(1)$ — No recurision needed (`root` is enough) -- * $O(\log n)$ — Recursive step only called on one child -- * $O(n)$ — Recursive step is called on both children --- # Other Trees: Morse Decoder Tree .left-column[ * Binary tree, not binary _**search**_ tree * Path to node determines the morse code - dot — go left - dash — go right ] .right-column[
] --- # Other Trees: Trie
-- * Each node has up to 26 children -- * Nodes with non-null values represent words -- * Path to node spells word contained at node -- * $O(1)$ for `contains()`, `add()`, `remove()` for a list of words --- # Other Trees: Expression Tree
-- * Represents $(w + (x \times y)) / z$ -- * Reverse Polish Notation: $x$, $y$, $\times$, $w$, $+$, $z$, $/$ --- # In-Order Tree Traversal To display elements in a binary search tree, we can use in-order tree traversal: ``` public void printInOrder() { inOrder(root); } private void inOrder(Node
subroot) { if(subroot!=null) { inOrder(subroot.lKid, consumer); System.out.println(subroot.value); inOrder(subroot.rKid, consumer); } } ``` --- # In-Order Tree Traversal cont... We can use a lambda expression to specify what to do at each node. ``` public void printInOrder() { * Consumer
print = e -> System.out.println(e); * inOrder(root, print); } * private void inOrder(Node
subroot, Consumer
consumer) { if(subroot!=null) { inOrder(subroot.lKid, consumer); * consumer.accept(subroot.value); inOrder(subroot.rKid, consumer); } } ``` --- # In-Order Tree Traversal cont... If we want a list in order: ``` public List
toSortedList() { * final List
list = new LinkedList<>(); * Consumer
add = e -> list.add(e); inOrder(root, add); * return list; } private void inOrder(Node
subroot, Consumer
consumer) { if(subroot!=null) { inOrder(subroot.lKid, consumer); consumer.accept(subroot.value); inOrder(subroot.rKid, consumer); } } ``` --- # Post-Order Tree Traversal Use post-order tree traversal to get RPN entries for an expression tree. .left-column[ ``` public List
expPostOrder() { final List
list = new List<>(); Consumer
add = e -> list.add(e); postOrder(root, add); return list; } private void postOrder(Node
subroot, Consumer
c) { if(subroot!=null) { postOrder(subroot.lKid, c); postOrder(subroot.rKid, c); c.accept(subroot.value); } } ``` ] .right-column[
] --- # Pre-Order Tree Traversal Use pre-order tree traversal to clone a BST ``` public BST
clone() { final BST
bst = new BST<>(); Consumer
add = e -> bst.add(e); preOrder(root, add); return bst; } private void preOrder(Node
subroot, Consumer
c) { if(subroot!=null) { c.accept(subroot.value); preOrder(subroot.lKid, c); preOrder(subroot.rKid, c); } } ```