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)

The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.