S1: Dynamic Data Structures (e.g. Trees)
- Goals
- Learn about Trees
- functional specifications
- Manipulation: tree traversals
- Implementation via Recursion, stacks and queues
- Learn about Binary Search Trees
- Outline
- Tree Vocabulary and Properties
- Tree Abstract Data Type: data and operations
- Tree Traversals: BFS, DFS (pre/ in/ post order)
- Binary Search Trees
- Reading
- Chapter 4.2 - Trees (pp 151-2)
- Chapter 11.1-3 - Trees
- Chapter 11.4-6 Binary Search Trees
- Recommended Ex.: 11.1-13, 11.15-17, 11.24-25
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S2: Tree Data Structure
- Definition - Tree is a collection of NODES.
- The collection is either empty or
- has a ROOT node R, and upto two(N) (SUB)TREES,
- whose roots (e.g. R1, R2) are directly connected to R.
- Q? Recognize trees in the following :
- road-map, structure-chart, unix directory, branch of oak-tree
- Analogy to "modern" family tree
- R is PARENT of R1 and R2
- R1 is a CHILD of R. R1 is a SIBLING of R2.
- Example from previous slide
- Ex. Define is-grandparent-of, is-ancestor-of
- More on vocabulary
- LEAF nodes - no children (i.e. subtrees are empty)
- INTERIOR nodes - has > = 1 child
- DEPTH(node)= if ROOT(node) then 0 else 1 + DEPTH(parent(node))
- HEIGHT(node)= if LEAF(node) then 0 else 1 + HEIGHT(aChild(node))
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S3: Tree Structure: Invariant Properties
- Which of the following are true about rooted Trees?
- A Tree can have many roots and many leafs
- no cycles, however all nodes are connected
- path(node i , node j) is unique
- Each node has two unique parents
- Each node has a unique height and depth
- (number of edges) = (number of nodes) - 1
- (number of leafs ) = (number of interior nodes)
- Q? Recognize trees in the following :
- road-map, structure-chart, unix directory, EE circuits
- Minneapolis airport (gates), Family tree.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S4: Trees: A Non-linear Dynamic data structure
- Dynamic data structures:
- Trees can expand and contract as program executes.
- Has Pointers
- Allocates memory at run-time as elements come
- Deallocate memory if elements are deleted
- Non-Linear data structures:
- Q? Can the elements/nodes be sorted?
- Is there a first node, a last node?
- Different from Stacks, Queues, Priority Lists etc.
- Hierarchical data structures:
- Q? Can items be partially ordered into a hierarchy?
- Yes, via Parent-Child Relationship
- Root node is at the top of the hierarchy
- Leafs are at the bottom layer of the hierarchy
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S5: Implementation Choices
- Two Major Choices for Implementing Data Structures
- Array Based OR Pointer Based
- Ex. Binary Tree - which implementation is preferred?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S6: Implementing Binary Trees Using Pointers
- BINARY Tree - a node has at most TWO children
- An important special case - see Huffman codes
- Using pointers and structs
- struct Tree_node {
- Element_type Element;
- Tree_Node *lChild, *rChild; //pointers
- }
- Using arrays
- struct Tree_node {
- Element_type Element;
- int lChild, rChild; //non-negative index to array
- }
- Tree_node myTree[10];
- Tree Operations (WTree.h) - constructor, accessor
- Common operation: Tree Traversals
- Ex. Find the node with minimum value of Element
- Ex. List all files under my home directory (%ls -R)
- Ex. List the leaf nodes of a tree.
- Ex. Recognize WTree.h operations with traversals
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S7: Constructing Binary Trees Using Pointers
- BINARY Tree - a node has at most TWO children
- An important special case - see Huffman codes
- Using pointers and structs
- class Tree_Node {
- Element_type Element;
- Tree_Node *lChild, *rChild; //pointers
- }
- Tree Construction (Ex. Huffman Code Tree)
- Top-down
- Create root
- Create children of root
- Create grandchildren of root
- ...
- Bottom-up
- Create two leafs L1, L2
- Create I1 = parent-of(L1, L2) & L3 = other child of I1
- Create I2 = parent-of(I1, L3) & other child of I2
- ...
- Q? Which method is relevant to Huffman.C, WTree.h ?
- What constructors are needed for
- top-down construction method?
- bottom-up construction method?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S8: Implementing Binary Trees Using Pointers
- Q? Recognize the construction method used in following
- box-pointer diagram
- Q? Draw diagram for the other construction method
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S9: Manipulating Trees
- Manipulating Trees - Tree Traversals
- Ex. Find the node with minimum value of Element
- Ex. List all files under my home directory (%ls -R)
- Ex. Find the node with Element = "G"
- Ex. List the leaf nodes of a tree.
- Tree Traversal is a common operation.
- It consists of visiting every node in tree once
- We will focus on traversals in 3321.
- Insert and Delete operation need further semantics
- e.g. binary search tree or B-tree etc.
- Q? Write psuedo-code for Insert(an element, a sorted tree).
- Element inserted as a new leaf.
- You must keep the tree sorted.
- i.e. (leafs in left subtree) < (leafs in right subtree)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S10: Traversal Order
- Traversal Order - may visit nodes in different orders
- Depth first or Breadth first
- Breadth First - Print nodes by depth
- e.g. iterative implementation using a queue
- Depth first - print nodes in subtree to the LEFT first
- e.g. iterative implementation using a stack
- Ex. Fig. 4.14/Weiss - Recognize DFS and BFS traversals
- + + a * b c * + * d e f g
- + + * a * + g b c * f d e
- DFS Traversal: Preorder vs. Postorder
- Preorder - print node before printing its children
- Postorder - print node after printing its children
- For binary tree - inorder DFS can be defined.
- Example 11.2 (pp 549)
- Ex. Fig. 4.14/Weiss - Perform preorder and postorder traversals.
- Q?. Determine the traversal order for recursive implementation.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S11: Ex. on Traversal Order
- Q? Write psuedo code for the following:
- 1. Given an arithmetic expression in tree form
- Output a postfix expression for the arithmetic expression.
- 2. Given a postfix arithmetic expression, and a stack
- Output a TREE representing the arithmetic expression.
- Q? Recognize the order of node printing by print()
//3 data members per node: data, lchild*, rchild*
Tree::print() {
if (lchild != NULL) lchild.print();
if (rchild != NULL) rchild.print();
cout << data;
}
//Hint: Work with a small tree with 5 nodes.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S12: Constructor/Destructors and Implicit Traversal Orders
- Q? Recognize the order of node deletion by Tree destructor.
//Hint: Work with a small tree with 5 nodes.
//Assume 2 pointer data members (lchild, rchild) per node
Tree::~Tree() {
if (lchild != NULL) delete lchild;
if (rchild != NULL) delete rchild;
}
//Q? Where is the recursive call? (Hint: Chapter 8)
- Q? Recognize the order of node copying by copy constructor.
//Hint: Work with a small tree with 5 nodes.
//3 data members per node: data, lchild*, rchild*
Tree::Tree(const Tree& T) {
data = T.data; lchild = NULL; rchild = NULL;
if (T.lchild != NULL) { lchild = new Tree(); lchild.Tree(T.lchild);}
if (T.rchild != NULL) { rchild = new Tree(T.rchild);}
}
- Consider a tree T with 5 nodes for the following questions:
- Q? How many calls to copy constructor occur to copy T?
- Q? How many calls to destructor occur for "delete T"?
- Q? How many calls to delete operator occur for "delete T"?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S13: Implementing Tree Traversals
- Tree Traversal is a common operation.
- It consists of visiting every node in tree once
- (i)Iterative implementation - using a queue or a stack
- function print_node_elements( aTree ) {
- 1. Insert the root node to queue Q.
- 2. DO
- 2.1 Retrieve and remove a node from Q
- 2.2 Print node.Element
- 2.3a If (node- > lchild != NULL) Q.Insert(node- > lChild)
- 2.3b If (node- > rchild != NULL) Q.Insert(node- > rChild)
- 2.4 WHILE (NOT Q.is_empty()) // end DO loop
- }
- Q? What will print_node_elements print on tree in Ex. 11.2 (pp 549)
- Q? What will print_node_elements print on tree in Ex. 11.2 (pp 549)
- if a Q is a stack rather than a queue?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S14: Implementing Tree Traversals
- (ii) Recursive Implementation
- function print_node_elements( aTree ) {
- 1. Print root_node.Element ;
- 2. if root_node- > lchild != NULL
- print_node_elements(root_node- > lChild) ;
- 3. if root_node- > rchild != NULL
- print_node_elements(root_node- > rChild) ;
- }
- Q? What will print_node_elements print on tree in Ex. 11.2 (pp 549)
- if recursive implementation is used?
- Q? Compare the output of recursive implementation with
- outputs of queue-based and stack-based implementations.
- Recursion has an implicit stack!
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S15: Using Stacks to Process Trees
- Strategy
- 1. Read a symbol
- 2. Scan input left to right
- 3. Leafs - > push on stack
- 4. Interior node or matching node - >
- 4.1 pop relevant children,
- 4.2 compute (e.g. create new tree, evaluate, ..)
- 4.3 push result (e.g. new tree) on stack
- 5. Go back to step 1
- Q? Write psuedo code for the following:
- 1. Given a postfix arithmetic expression, and a stack
- Output a TREE representing the arithmetic expression.
- 2. Given a postfix arithmetic expression, and a stack
- Output the value of the the arithmetic expression.
- 3. Given a parenthesized arithmetic expression, and a stack
- check if parenthesis are well-formed,
- i.e. each '(' is matched with ')'.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S16: Exercises
- Example on tree from Ex. 11.2 (pp 549)
- Q?. Determine the traversal order for Queue based implementation.
- Q?. Determine the traversal order for Stack based implementation.
- Q?. Determine the traversal order for recursive implementation.
- Q?. Change the Stack based implementation for Post-order traversal.
- Ex. Fig. 4.8/Weiss - Perform preorder and postorder traversals.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S17: 11.4-6 Binary Search Trees (BSTs)
- Purpose: An efficient collection for search(), insert(), delete()
- By key value (e.g. id = 32) or by rank (e.g. fifth smallest)
- Ex. Find an element with key = 21, Insert an element and find its rank
- Ex. Find the 3rd smallest element, Delete the 5th smallest element
- Recursive Definition: A BST is a binary tree, s.t.
- Base Case: empty BST (NULL)
- Recursive Case has the following properties:
- (P1) Every element/node has a unique key
- (P2) The keys (if any) in the left subtree are smaller than key(root)
- (P3) The keys (if any) in the right subtree are larger than key(root)
- (P4) The left and right subtrees are also BSTs
- Q? Are the following trees BSTs? If not, then identify the properties violated.
- (a-f)Various possible (6) balanced binary trees with the keys 1, 2, 3;
- (g)WTrees (ref. Huffman codes); (h) Unix directories; (i) arithmetic expressions
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S18: Finding Min and Max keys in BSTs
- Recursive Formulation of Maximal Element
- Base Case: Leaf BST = > key at root is maximal element
- Recursive Case1: Has a right subtree but not a left subtree
- Recursive Case 2: Has a left subtree but not a right subtree
- Recursive Case 3: Has a left subtree and a right subtree
- Q? For each case, Determine T.max() as a function of
- (i) this.data, (ii) left- > max(), and (iii) right- > max()
- Assuming struct { String key, data; Node* left, right } Node;
- Q? Write psuedo-code for recursively finding maximal element.
String BST::max( )
{ if (right =! NULL) return right- > max(); else return key; }
- Iterative Formulation:
- Note tail recursion can be converted to iteration.
- Ex. Convert the recursive max() to an iterative one.
String BST::max( ) {
for( BST* T = this; (T- > right != NULL); ) T = T- > right;
return T- > key;
}
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S19: Searching BSTs For a Given Key
- Recursive Formulation: Finding a key, or Max/Min Keys
- Base Case: leaf BST OR (this.key == k)
- Recursive Case 1. Key is in root node
- Recursive Case 2. Key is in the left subtree
- Recursive Case 3. Key is in the right subtree
- Q? Write conditions for the above 3 cases. Are the cases disjoint?
- Q? Write psuedo-code for searching for a key and returning data.
//struct { String key, data; Node* left, right } Node;
int BST::get( String k; String& d ) {
if (key == k) {d = data ; return TRUE;}
else if leaf() return FALSE;
else if ((left != NULL)&&(k < key)) return left- > max(k,d);
else if ((right != NULL)&&(k > key)) return right- > max(k,d);
}
- Iterative Formulation: Note tail recursion can be converted to iteration.
- Ex. Convert the recursive find() to an iterative one.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S20: Ordering Properties of BST Traversals
- Consider a BST for 5 nodes. Say a balanced BST with 1,2,3,4,5.
- Show the output from preoder, inorder and postorder traversal.
- Q? Which traversal produces the keys in sorted order?
- Q? Will this traversal sort the keys in any arbitrary BST? Why?
- Q? Write a function using this traversal to find 3rd smallest key?
- .. find the key with rank R ?
- Sorting a BST: Inorder traversal sorts the nodes by key-value
- Proof Sketch: By Induction.
- True for base case (leaf BST).
- True for general case if it is true for the subtrees (smaller BSTs).
- Finding an element with a given rank:
- Option 1: Use an inorder traversal and keep track of the rank.
- Option 2: Maintain rank (or number of nodes in left subtree)
struct BSTnode { String key, data; int rank; BST* left, right }
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S21: BST::Insert()
- Steps:
- 1. Find the correct place (a parent) for the new key
- 2. Update relevant pointer in the parent node
- 3. Update other fields if needed (e.g. ranks)
- Locating place for < key, data > : Place(BST, item)
- Null BST = > BST := leaf-node(item); // Base case
- (BST.left == NULL && BST.key < K) = > BST.left := leaf-node(item);
- (BST.right == NULL && BST.key > K) = > BST.right := leaf-node(item);
- BST.key < K = > Place(BST.left, item)
- BST.key > K = > Place(BST.left, item)
//Assumes class T has operator > , key and data.
template < class T >
void insert( TreeNode < T > * & t, T item)
{
if (t == NULL)
t = GetTreeNode(item, NULL, NULL); // insert!
// locate place recursively
else if (item > t- > data) F( t- > right, item);
else F( t- > left, item);
}
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)