i206: Lecture 13: Recursion, continued Trees Marti Hearst Spring 2012 1 Recursive Programs / Algorithms An algorithmic technique in which a function, in order to accomplish a task, calls itself with some part of the task. Need A base case (so the program will end)

The recursive step(s) The recursive step must narrow or reduce the problem in some manner. 2 Recursive Summing We can use recursion as an alternative to a loop for our various summation problems. Try it out here: http://people.csail.mit.edu/pgbovine/python/tutor.html#mode =edit def recursiveSum2(n):

if n == 0: return 0 return n + recursiveSum2(n-1) recursiveSum2(5) 3 Recursive Summing We can use recursion as an alternative to a loop for our various summation problems. Try it out here: http://people.csail.mit.edu/pgbovine/python/tutor.html#mode =edit def recursiveSum2(n):

if n == 0: return 0 return n + recursiveSum2(n-1) recursiveSum2(5) 4 From Goodrich & Tamassia 5 Methods and the Operating Systems Runtime Stack Each time a method is called A new copy of the methods data is pushed on the stack This data includes local variables

This applies to all methods, not only recursive ones The return command does two things: Pops the data for the method off the stack Local variables disappear Passes the return value to the calling method If there is no return statement The method is popped Nothing is passed to the calling method 6 Summary: Recursion Recursion is a useful problem-solving technique We will see it again when we study trees and

sorting But it takes some getting used to. To help: Remember that each method call gets put on the stack until the base case is found; then the calls are popped off the stack. You have to understand basic programming concepts like Method calls Returning from methods Passing parameters 7 Data Structures Outline What is a data structure

Basic building blocks: arrays and linked lists Data structures (uses, methods, performance): List, stack, queue Dictionary Tree Graph 8 Trees

9 Trees Trees are very important and useful They are usually drawn upside-down The allow us to represent hierarchy File system Book structure Employees in a bureacracy Every node has exactly one parent Except the root 10 root

siblings parent & child Anatomy of a Tree Ancestor & descendent 11 Tree Data Structure Tree = a collection of data whose entries have a hierarchical

organization Example: Brookshear Figure 8.1 What are some examples of trees in computer systems? 12 Tree Terminology Node = an entry in a tree Nodes are linked by edges Root node = the node at the top Terminal or leaf node = a node at the bottom Brookshear Figure 8.2

Parent of a node = the node immediately above the specified node Child of a node = a node immediately below the specified node Ancestor = parent, parent of parent, etc. Descendent = child, child of child, etc. Siblings = nodes sharing a common parent 13 Tree Terminology Depth of a node The depth of a node v in T is the number of ancestors of v, excluding v itself. More formally: If v is the root, the depth of v is 0 Else the depth of v is one plus the depth of the parent of v

Height (or depth) of a tree The depth of a tree is the maximum depth of any of its leaves x Depth(x) = 1 Depth(y) = 3 Depth(T) = 3 y 14 Types of Trees General tree a node can have any number of children

Binary tree a node can have at most two children 15 Trees vs. Graphs / Networks The Web is not a tree. Why not? Nodes in a tree can have only one parent Graphs / Networks are the more general case

16 Binary Tree The simplest form of tree is a Binary Tree A Binary Tree consists of (a) A node (called the root node) and (b) Left and right subtrees Both the subtrees are themselves binary trees Note: this is a recursive definition 17 Binary Search Tree Differs from Binary tree in that Each internal node has a key

The key is used to give an order to the nodes Nodes often store data But sometimes stored only in leaf (B+Trees) The keys are stored in order such that Keys to the left of a node are less than keys to the right of that node More formally, For each internal node v with key k Keys stored in nodes in the left subtree of v are <= k Keys stored in nodes in the right subtree are >= k 18 Implementing a Binary Tree

Linked list Each node = data cell + two child pointers Accessed through a pointer to root node Brookshear Figure 8.13 19 Implementing a Balanced Binary Tree Balanced: the depth of the two subtrees of every node never differ by more than 1 Array

A[1] = root node A[2],A[3] = children of A[1] A[4],A[5],A[6],A[7] = children of A[2] and A[3] Brookshear Figure 8.14 20 A sparse, unbalanced tree Brookshear Figure 8.15 21

Tree Methods search (or get) Return a reference to a node in a tree insert (or put) Put a node into the tree; if the tree is empty the node becomes the root of the tree delete (or remove) Remove a node from the tree traversal access all nodes in the tree 22 Application: Binary Search Recall that binary search algorithm

is O(log n) One way of implementing the algorithm is to use a binary search tree (BST) data structure Brookshear Figure 8.17 23 Binary Search Tree Binary search tree (BST) data structure The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Brookshear Figure 8.17 24 Binary Tree Search Example: Search (Tree, J) Brookshear Figure 8.19 Brookshear Figure 8.18 25 Node Insertion Brookshear Figure 8.23

Example: Insert (Tree, M) Brookshear Figure 8.22 26 4 Node Deletion When you delete a node that has children, you need to re-link the tree 1 Three deletion cases: 2

5 3 Delete node with no children Delete node with one child (which may be a subtree) Delete node with more than one child Last case is a challenge with ordered trees You want to preserve the ordering 27 Delete Nodes No children 4

4 parent parent 2 delet e 1 2 5 3 delet e

1 5 3 parent.left = null; 28 Delete Nodes One child parent delet e parent 4

2 5 delet e 4 2 5 3 3 parent.left = delete.right;

29 Deleting Nodes Multiple parent children 6 delete Assuming you want to preserve the sort order, deletion is not straight forward Replace the deleted node with a node that preserves the sort order the inorder successor node for in-order trees The successor node will be

in the right subtree, left most node (or left most parent node if there is no left most node) 2 7 1 8 4 successor 3

5 parent 6 successor 3 1 7 8 4 5 30

Tree Traversal A systematic way of accessing (or visiting) all the nodes of a tree Example: printing binary search tree in alphabetical order using in-order tree traversal Brookshear Figure 8.21 Brookshear Figure 8.20 31 Tree Traversal Different types of traversal 1

4 2 1 2 5 3 In-order 3 5 3

5 4 Pre-order 1 1 4 2 Post-order 2 4 3

5 level numbering 32 Tree Traversal root b a Preorder Inorder Postorder

aa ab aaa aab All defined in terms of When do you visit the node itself When do you visit the lefthand side When do you visit the righthand side 33 Binary Tree Implementation root b

a aa ab aaa aab 34 root PreOrder b a

aa ab aaa aab Why? Textual representation of the tree (parents before children) 35 root InOrder b

a aa ab aaa aab Why? Useful for searching in ordered trees 36 Depth-first Search A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. Then, it continues at the nearest ancestor that hasn't been searched through yet.

Full tree Note: DFS traversal is equivalent to PreOrder traversal DFS (to see it, run in Presentation Mode) From http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/ExhaustiveSearch.html 37

Breadth-first Search A breadth first search (BFS) through a tree starts at the root and moves from nodes left to right at each level until all the nodes have been looked at or until the value is found. Full tree What do we need besides the runtime stack to make BFS work? BFS (to see it, run in Presentation Mode) From http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/ExhaustiveSearch.html

38 Depth First Search 39 Breadth First Search 40 Efficiency of Binary Search Trees Search, insert, and delete operations: O(height of tree)

Average Case Search: O(log n) Insertion: O(log n) Deletion: O(log n) Traversal: O(n) Worst Case

Search: O(n) Insertion: O(n) Deletion: O(n) Traversal: O(n) AVL trees and Red-Black trees Self-balancing trees with tree height O(log n) Worst case O(logN) searches, insertions, and deletions Many other variations: Splay trees, B-trees, etc. 41