Lecture11

Binary Search Tree

Full vs. Complete Binary Trees

• Full binary tree
  • a tree in which every node other than the leaves has two children

image-20210409124544762.png

• Complete binary tree:
  • a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

image-20210409125055015.png

Complete vs. Incomplete Tree

• Complete Tree:
  • All levels are populated left to right
  • Last level IS populated left to right(even thought it is not fully populated)

image-20210409125438993.png

• Incomplete Tree
  • All levels are populated, BUT
  • Last tree is not populated left to right

image-20210409125638196.png

Terminology: Tree Height

• Tree height: maximum node depth in the tree OR height of the root
• Here: tree height H=2

image-20210409125919886.png

Tree Size: Full Tree

• Tree size: number of all nodes in a tree
• Here: N = 2⁰+ 2¹+ 2²= 2⁽²⁺¹⁾-1=7(but this is a very "neat" FULL tree)
• N=2⁰+ 2¹+ 2²+...+2^H=2^(H+1)-1

image-20210409130539079.png

Tree Height = f(Tree size)

• N- Number of Tree Elements | H-Full Tree Height
• N=7--> H=log₂(N+1)-1 = log₂(7+1)-1=3-1=2

image-20210409130759184.png

BST Operations: Best / Worst Case

image-20210409185533622.png

Binary Trees: Underlying Structure

• Trees can be stored in
  • arrays
  • linked structures
• Trees based on arrays:
  • fast access
  • fixed size
  • deletion
  • possible waste of space("null" nodes) if not full
• Trees based on linked structures
  • dynamic size
  • overhead

Tree as Arrays: Structure

image-20210409190040254.png

image-20210409190151498.png

Tree as Arrays: Indexing

image-20210409190241066.png

Abstract Data Type: Heap

• Heap ADT
  • add (element)
  • top ( )
  • peek ( )
  • size ( )
  • isEmpty ( )

Heap

• A heap is a binary tree with the following characteristics:
  • It is complete: each tree level is completely filled from left to right, with possible exception of the last level (which is still filled from left to right)
  • All nodes/keys satisfy the heap property:
    • in heaps for every node its key is greater [MaxHeap] / less than [MinHeap] (or equal to ) the keys of its children nodes.

Binary Search Tree vs. Heap

• Binary Search Tree Properties:
  • The left subtree of a given node contains only nodes with keys lesser than the node's key.
  • The right subtree of a give node contains only nodes with keys greater than the node's key.

image-20210409221006261.png

• Heap Properties:
  • For every node its key is greater than(or equal to)the keys of its children nodes.

MaxHeap vs. MinHeap

• MaxHeap Properties:
  • For every node its key is greater than (or equal to) the keys of its children ndoes.

image-20210409221414323.png

• MinHeap Properties:
  • For every node its key is less than(or equal to) the keys of its children nodes.

image-20210409221754560.png

Invalid Heaps

• This tree is not complete. It is not a heap.

image-20210409222239012.png

• MinHeap property is violated: child node key is less than parent ndoe key(5>2)

image-20210409222530554.png

Heap: Subtrees are Heaps

Heap property: both left and right subtrees must also be a heap.

image-20210409223318753.png

Heap: Single-node Trees are Heaps

Heap property: single-node trees are valid heaps.

image-20210409223508844.png

Heap: add(Element/Key)

Step1: A valid MaxHeap prior to adding a new node. New node location.

image-20210409231211399.png

Step2: Heap property temporarily violated!

Step3: Swap Parent and Child elements to restore MaxHeap property

Step4: Swap Parent and Child elements AGAIN to restore MaxHeap property

Step5: Now MaxHeap property is violated one level up

Step6: MaxHeap property is restored. Heap is valid

image-20210409231304026.png

Heap: top()

Step1: top(max in this case) element(10) is to be removed

Step2: top is removed, there will be a gap. Let's "fill/swap it" with the "last element"

image-20210409232256244.png

Step3: Now MaxHeap property is violated

Step4: Parent and LARGEST KEY(9) child elements to restore MaxHeap property

image-20210409232413275.png

Step5: MaxHeap property is restored. Heap is valid

Heap: peek()

Step 1: retrieve the top element without removing it.

image-20210410102901149.png

Application: Heap Sort

• Heap Sort Pseudocode

heapSort(Collection c){
    if(c !=null){
    
        Heap h = new Heap();
        List out = new List();
        
        while(!h.isEmpty()){
            out.add(h.top());
        }
    }
    return out;
}

image-20210410103602136.png

Application: TOP K Elements

• TOP K Elements Pseudocode:

topK(Collection c, int k){
    if(c != null & k>0){
        int count = 0;
        Heap h = new Heap();
        List out = new List();
        
        while( !h.isEmpty()){
            out.add(h.top());
            count++;
            if(count > k) break;
        }
    }
    return out;
}

image-20210410104205194.png

Abstract Data Type: Priority Queue

• Priority Queue ADT:

  • enqueue (element)
  • dequeue ( )
  • peek ( )
  • size ( )
  • isEmpty ( )

• Comments:

  • Underlying Structure is "invisible" to the user:
    • different approaches can be used
    • consider performance measures for the problem at hand
  • Needs to accept various elements