Skip to Big O runtime

• Trees

  • Basic tree terminology (CS 173)

    • Leaf: Nodes with no children, Internal Node: not a leaf
    • Level: Number of edges away from the root (zero), Height: Maximum Level
    • Ancestor, Descendant, Neighbor: Can be reached by the following parent links:
    • Binary: At most, two children per node
    • Full: either m children or none. Perfect: All leafs are at the same level, and all internal nodes have m children
    • Complete tree: Perfect tree but in the last level, all the leaves are filled from left to right.
    • Full does not imply perfect, so as complete does not imply perfect
    • Not full implies not perfect, thus perfect implies full; perfect also implies complete too.
    • Reference: Chapters 13 in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)

  • Tree Property: Binary

    • T = {TL, TR, r}, where TL, TR are binary trees
    • T = {} = ∅

  • Tree Property: Height: longest path from root to leaf (edges)

    • height(T) = 1+max(height($T_l$)+height($T_r$) where height(null) = -1

  • Tree Property: Full

    • Either: F = {}
    • Or: F = {TL, TR, r} where TL, TR both have either 0 or 2 children

    

  • Tree Property: Perfect

    • P-1 = {}

    • Ph = {r, Ph-1, Ph-1} when h>=0

      

  • Tree Property: Complete (as defined in data structures)

    • Perfect tree except for the last level. All leaves must be pushed to the left.
    • C-1 = {}
    • Ch = {r, TL, TR} where

      • Either: TL = Ch-1 and TR = Ph-2

        Or:      TL = Ph-1   and   TR = Ch-1

        

  • Tree Property: NULL pointers in a BST, including proof

    • Theorem: A binary tree with n data items has n+1 null pointers.

    Proof: Let NULL(n) be the number of null pointers in a tree with n nodes.

    Goal: NULL(n) = n+1 for n ≥ 0

    Proof by induction:

    Base Case: when n=0, NULL(0) = 1. Just an empty tree with the root=nullptr.

    

    when n=1 NULL(1) = 2

    when n=2 NULL(2)=3

    Inductive step:

    Inductive Hypothesis: NULL(j) = j+1 for an j < n

    • Look at the root: # nodes in left subtree + # nodes in right subtree = n-1
    • Suppose that the left subtree as q nodes, the right subtree has n-q-1 nodes.
      • q < n and n-q-1 < n
      • since the root has no null pointers

    NULL(n) = NULL(q) + NULL(n-q-1) = q+1+n-q-1+1 = n+1

  • Traversal: (practice them here: https://yongdanielliang.github.io/animation/web/BST.html)

    • Pre-Order: process the data first, then left child, then the right child
    • In-Order: left child, process the data, right child
    • Post-Order: left child, right child, process the data last

    void BinaryTree<T>::preOrder(TreeNode * cur) {
    	if (cur != NULL) {
    		func(curr->data);
    		preOrder(curr->left);
    		preOrder(curr->right);
    	}
    }
    
    void BinaryTree<T>::inOrder(TreeNode * cur) {
    	if (cur != NULL) {
    		inOrder(curr->left);
    		func(curr->data);
    		inOrder(curr->right);
    	}
    }
    
    void BinaryTree<T>::postOrder(TreeNode * cur) {
    	if (cur != NULL) {
    		postOrder(curr->left);
    		postOrder(curr->right);
    		func(curr->data);
    	}
    }
    

  • Traversal: Level-Order: traverses tree by every level, using queue to keep track of each node that we encounter o=n each level. Pseudocode:

    • enqueue root
    • while the queue is not empty
      • dequeue e
      • func(e→data)
      • enqueue (e→left) and enqueue(e→right)

  • Traversal vs Search: traverse visits every node vs search visits nodes until you find what you want

  • Search Strategy:

    • BFS: breadth first search: visits nodes at each level (level-order traversal): use a queue

      

    • DFS: depth first search: find the endpoint of the path quickly (in order, pre order or post order): use a stack

      

• Binary Search Tree

  • Difference between a “Tree” and a “BST”
    • T = {} or T = {d, TL, TR}, where ∀x, x∈TL , x < d x∈TR , x > d
    • Everything to the left of the root is less than the root and everything to the right of the root is greater than the root. This is recursively true for every node.
  • Operation find, including running times in terms of h and n

  TreeNode *& BST::_find(TreeNode *& root, const K & key) const {
  		if (root == NULL || key == root->key) {
  				return root; //returns null since the root is null
  		}
  		if (key < root->key) {
  				return _find(root->left, key);
  		}
  		if (key > root->key) {
  				return _find(root->right, key)
  		}
  }
  

  • Operation insert, including running times in terms of h and n

    • find the position to insert at using find
    • create new node and insert at position (always should insert at leaf)

    void BST::_insert(TreeNode *& root, K & key, V & value) {
    	TreeNode * t = _find(root, key);
    	t = new TreeNode(key, value);
    }
    

  • Operation delete, including running times in terms of h and n

    • find the element to delete O(h)

    • if it is a leaf, delete it

      

    • if it has one child, delete as you would in a linked list (replace node with child)

      

    • if it has two children, find the inorder predecessor (IOP)—> largest node in the left subtree

      • swap IOP and the node that we actually want to delete

      • the node is now either a leaf or a 1 child so we can remove it

        

    TreeNode * deleteNode(TreeNode * root, K & key) {
    		if (root ->val_ > key) {
    				root->left = deleteNode(root->left, key);
    		} else if (root->val < key) {
    				root->right = deleteNode(root->right, key);
    		} else {
    			//no child
    			if (root->left == NULL && root->right == NULL) {
    					delete root;
    					root = NULL;
    			}
    			TreeNode * temp = root;
    			//one child
    			if (root -> left == NULL) {
    					root = root->right;
    					delete temp;
    			} else if (root ->right == NULL) {
    				root = root->left;
    				delete temp;
    			}
    			//two children
    			else {
    					temp = findMax(root->left); //In order Successor
    					root->val = temp->val;
    					root->left = deleteNode(root->left, temp->val);
    			}
    		}
    		return root;
    }
    

  • BST Property: Min/max nodes in a tree of a given h, and properties

  • BST Property: Height balance factor, b = height($T_r$) - height($T_l$)

• AVL (https://www.cs.usfca.edu/~galles/visualization/AVLtree.html)