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

    • m(h) = max number of nodes where $\begin{Bmatrix} 0 & h = -1 \\ 1+2m(h-1) & h > -1\end{Bmatrix} = 2^{h+1}-1$ or $O(2^h)$

    solving the inequality for the height we get $h\leq log_2(n+1)-1$ which means that O(log n) is the lower bound for runtime and O(n) is the upper bound for runtime. The height of the tree depends on the oder of data to insert.

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

    • Left heavy trees: balance factor negative

    • Right heavy trees: balance factor is positive

    • Tree is balanced when |b|≤1

    • Balance is determined at each node.

      

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

  • Must maintain the height of the tree, detect imbalance in the tree and rotate to correct for these.

  • Difference between a “Tree”, “BST”, and an “AVL”

    • AVL is a balanced BST which is a Tree where all the right children are greater than the left children at each level.

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

    Find normal is same as BST

    Find Unbalanced (time complexity O(log n)

    V AVLTree<K>::findLastUnbalanced(Node * root) {
    		Node* left = findLastUnbalanced(root->left);
    		Node* right = findLastUnbalanced(root->right);
    		if (left != NULL || right != NULL) {
    			return height(root->left_) > height(root->right) ? left : right;
    		}
    		return isHeightBalanced(root) ? NULL : root;
    }
    

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

    void AVLTree<K, V>::insert(Node*& subtree, const K& key, const V& value)
    {
        if (subtree == NULL) subtree = new Node(key, value);
        else if (subtree->key < key) {
            insert(subtree->right, key, value);
            rebalance(subtree);
        }
        else {
            insert(subtree->left, key, value);
            rebalance(subtree);
        }
    }
    

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

    pseudocode: first recurse down to the key we are deleting.

    • if there are no children, delete the leaf.
    • If there is one child, perform deletion like you would on a list (aka find the leaf that's not null, delete current node and set the current node to be the leaf).
    • If there are two children, find the In order predecessor (aka the greatest node to the left of the current node), swap this node with the current's left, then delete the current node's left.

    reassign all the heights + rebalance the tree.

    void AVLTree<K, V>::remove(Node*& subtree, const K& key) {
    	if (subtree == NULL)
    	        return;
    	
    	    if (key < subtree->key) {
    	        remove(subtree->left, key);
    	        rebalance(subtree);
    	    } else if (key > subtree->key) {
    	        remove(subtree->right, key);
    	        rebalance(subtree);
    	    } else {
    	        if (subtree->left == NULL && subtree->right == NULL) {
    	            /* no-child remove */
    	            delete subtree;
    	            subtree = NULL;
    	        } else if (subtree->left != NULL && subtree->right != NULL) {
    	            /* two-child remove */
    	            Node * pre = subtree->left;
    	            while (pre->right != NULL) {
    	                pre = pre->right; //finding IOP
    	            }
    	            swap(pre, subtree);
    	            remove(subtree->left, key);
    	        } else {
    	            /* one-child remove */
    	            Node * newSubtree = subtree->right != NULL ? subtree->right: subtree->left;
    	            delete subtree;
    	            subtree = newSubtree;
    	        }
    	        rebalance(subtree);
    	    }
    }
    

  • AVL Tree Rotations

    When abs(balance) ≥2, we need to rotate the tree R, L RL or LR

    

    

    Pseudocode:

    • Insert at proper place; Check for imbalance; rotate if nessecary; recurse up (reverse this code for rotate left)

    void AVLTree<K, V>::rotateRight(Node*& t)
    {
        Node * temp = t->left;
        t->left = temp->right;
        temp->right = t;
        reassignHeights(t);
        t = temp;
    
        reassignHeights(temp);
    }
    

    Rebalance:

    void AVLTree<K, V>::rebalance(Node*& subtree)
    {
        if (subtree == NULL) return;
        reassignHeights(subtree);
    
        int balance = heightOrNeg1(subtree->right) - heightOrNeg1(subtree->left); 
        if (abs(balance) <= 1) return;
        if (balance < 0) { //left heavy
            int balanceLeft = heightOrNeg1(subtree->left->right) - heightOrNeg1(subtree->left->left);
            if (balanceLeft < 0) { //left subtree left heavy
                rotateRight(subtree);
            } else {
                rotateLeftRight(subtree);
            }
        } else if (balance > 0) {        //right heavy
            int balanceRight = heightOrNeg1(subtree->right->right) - heightOrNeg1(subtree->right->left);
            if (balanceRight > 0) { //right subtree right heavy
                rotateLeft(subtree);
            } else {
                rotateRightLeft(subtree);
            }
        }
    }
    

  • Minimum/maximum nodes in an AVL tree

  Runtimes

  | --- | --- | --- | --- | --- | --- | --- | --- | --- |