S1: Dynamic Data Structures (e.g. Trees)
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
    • using a given tree.
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)