EDA T6 — AVL trees and Heaps

Ilario Bonacina
ilario.bonacina+EDA@upc.edu

This presentation is an adaptation of material from Antoni Lozano and Conrado Martinez

Agenda

Last theory class

  • Dictionaries
    • Hash Tables
    • Binary Search Trees

Today

  • AVL Trees

  • Heaps & Priority Queues

Before we start: Questions on previous material?

AVL trees

Binary Search Trees (recap)

A Binary Search tree (cat: Arbre Binari de Cerca, ABC) is a binary tree such that each vertex v in it has associated a key \mathsf{KEY}(v) and

  • for each vertex w in the left subtree of v, \mathsf{KEY}(w)<\mathsf{KEY}(v),
  • for each vertex u in the right subtree of v, \mathsf{KEY}(u)>\mathsf{KEY}(v).

We saw how to use a BST to implement a dictionary, i.e. how to search / insert / remove elements.

For a BST of depth/height h the worst-case cost of a search / insertion / deletion has cost \Theta(h).

This is great if h\approx \log n but bad when h\approx n (which can happen).

AVL trees

An AVL tree1 T is a binary search tree such that for every node v in T, let h_{\mathsf{left}} and h_{\mathsf{right}} be the height of the left (resp. right) sub-trees of v, then \mathsf{balance}(v)=h_{\mathsf{right}}-h_{\mathsf{left}}\in \{-1,0,1\}\ .

  • if h_{\mathsf{right}}-h_{\mathsf{left}}=1 we say that v is right-heavy.
  • if h_{\mathsf{right}}-h_{\mathsf{left}}=0 we say that v is balanced.
  • if h_{\mathsf{right}}-h_{\mathsf{left}}=-1 we say that v is left-heavy.


Balance Factors

Red = left-heavy
green = right-heavy
bold indicates where tree is too unbalanced.

Implementation

As for the BSTs (see last class) but in Node we also store the height of the node.

template <typename Key, typename Info>
class Dictionary {
    private:
        struct Node {
            Key key;
            Info info;
            Node* left;  // Pointer to left child
            Node* right; // Pointer to right child
            int height; // Height of the tree
            Node (const Key& c, const Info& i, Node* l, Node* r, int h)
            : key(c), info(i), left(l), right(r), height(h)
            { }
        };
        int n;  // Number of keys
        Node* root; // Pointer to the root of the AVL
        ...
};

See the full implementation in the Algorismes en C++.

Why AVL trees?

  • Every AVL tree with n nodes has height \Theta(\log n).
  • After each insertion in an AVL tree (as done for BSTs in the last class), with an extra cost of \Theta(1) we can restore the tree to be an AVL.
  • After each deletion in an AVL tree (as done for BSTs in the last class), with an extra cost of \mathcal O(\log n) we can restore the tree to be an AVL.

Theorem 1 Every AVL tree with n nodes has height h=\Theta(\log n).

Proof.

  • h=\Omega(\log n): since AVLs trees are binary trees n\leq 2^{h+1}-1.
  • h=\mathcal O(\log n): let T(h) be the smallest number of nodes in any AVL tree with height h. We have that T(0)=1 and T(1)=2 and T(h)=T(h-1)+T(h-2)+1

This is very similar to the recurrence for the h-th Fibonacci number F_h, indeed (by induction on h) we can prove that T(h)=F_{h+2}-1=\Theta(\varphi^h), where \varphi=\frac{1+\sqrt{5}}{2}. Since n\geq T(h), we get n=\mathcal O(\log n).

Search in an AVL

This is done as in any other BST (see last class).


By the previous theorem, the cost of any search for a key in an AVL tree of size n is O(\log n), even in the worst case.

Insertion in an AVL

Insertion in an AVL tree at first is done as for generic BSTs, but this might invalidate the balance of some nodes.

What numbers could be the out-of-bounds balance?

Where could be in the tree the nodes with out-of-bounds balance?

How could we restore the balance efficiently?

If the balance condition at some node is not valid anymore (it can only become +2 or -2) we must do something to fix it and re-establish the invariant. This is done via left and right rotations (or combinations of them).

The “magic” of AVL trees

After the insertion of a vertex in an AVL tree, at most 2 rotations are enough to re-establish the balances on every vertex.

root = the deepest vertex not respecting the balance condition before any rotation

pivot = its child along the path towards the new vertex added

We have 4 possibilities:

root pivot short name
balance +2 +1 or 0 RR
balance +2 -1 RL
balance -2 -1 LL
balance -2 +1 or 0 LR

LL case

Balance Factors before & after a single right rotation
The dotted lines denote the new vertex added.

Implementation of an LL rotation

static void update_height (Node* p) {
    p->height = 1 + max(height(p->left), height(p->right));
}

static void LL (Node*& p) {
    Node* q = p;
    p = p->left;
    q->left = p->right;
    p->right = q;
    update_height(q);
    update_height(p);
}

LL rotations are not expensive: just change a couple of pointers.

LL rotations — correctness

  • LL rotations preserve the BST properties of the tree (check!)
  • LL rotations fix the unbalance (in the LL case) (check!)

RR case

The RR case (both root and pivot right heavy) is symmetric w.r.t. the LL case

static void RR (Node*& p) {
    Node* q = p;
    p = p->right;
    q->right = p->left;
    p->left = q;
    update_height(q);
    update_height(p);
}

As for LL rotations, RR rotations can also be done essentially changing a couple of pointers.

LR case

static void LR (Node*& p) {
    RR(p->left);
    LL(p);
}

LR double rotations — correctness

  • LR rotations preserve the BST properties of the tree (check!)
  • LR rotations fix the unbalance (in the LL case) (check!)

RL rotation

analogous to the LR case, just symmetric.

static void RL (Node*& p) {
    LL(p->right);
    RR(p);
}

Insertion in an AVL — implementation

public: 
    void assign (const Key& key, const Info& info) {
        assign(root, key, info);
    }
private:    
    void assign (Node*& p, const Key& key, const Info& info) {
        if (p) {
            if (key < p->key) {
                assign(p->left, key, info);
                if (height(p->left)-height(p->right) == 2) {
                    if (key < p->left->key) LL(p);
                    else LR(p);
                }
                update_height(p);
            } else if (key > p->key) {
                assign(p->right, key, info);
                if (height(p->right)-height(p->left) == 2) {
                    if (key > p->right->key) RR(p);
                    else RL(p);
                }
            } else {
                update_height(p);
                p->info = info;
            }
        } else {
            ++n;
            p = new Node(key, info, nullptr, nullptr, 0);
        } 
    }
1
This is the same as the usual BST tree.

The worst-case cost of an insertion in an AVL is \Theta(\log n).

Deletion in an AVL

The deletion algorithm for AVLs draws upon the same ideas: delete as in a normal BST and then fix the unbalances. The analysis to determine what rotation must be applied is a bit more complex.

The worst-case of deletions in AVLs is \Theta(\log n). Unbalance in a node is corrected by a simple or a double rotation, but it might be necessary to apply several rotations to fix the balance. However, not more than a rotation is necessary in any given node in the path from the root to the deletion point, since they are only \mathcal O(\log n), the worst-case is also \Theta(\log n).

Heaps and Priority Queues

Perfect Binary Tree

A binary tree is perfect if all the internal nodes have 2 children and all the leaves have the same depth/height.

Theorem 2 For a perfect binary tree of depth d and n nodes, it holds that n=2^{d+1}-1\ .

(Proof at the blackboard)

Complete Binary Tree

A binary tree of depth d is complete if

  • all the nodes at depth \leq d-2 have exactly 2 children
  • the nodes at depth d are filled from left to right without leaving empty spots

Theorem 3 For a complete binary tree of depth d and n nodes, it holds that 2^d\leq n\leq 2^{d+1}-1\ . Which implies, d=\lfloor \log_2 n\rfloor and d=\Theta(\log n).

(Proof at the blackboard)

Priority Queues

A priority queue (cat: cua de prioritat; esp: cola de prioridad) stores a collection of elements, each one associated with a value called its priority.

Priority queues support the insertion of new elements and the query and removal of an element of minimum (or maximum) priority.

template <typename Elem, typename Prio>

class PriorityQueue {
    public:
        ...
        void insert(cons Elem& x, const Prio& p);
        Elem min() const;
        Prio min_prio() const;
        void remove_min();
        bool empty() const;
};
1
Adds an element x with priority p to the priority queue.
2
Returns an element of minimum priority; throws an exception if the queue is empty.
3
Returns the priority of an element of minimum priority; throws an exception if the queue is empty.
4
Removes an element of minimum priority; throws an exception if the queue is empty.
5
Returns true iff the priority queue is empty

  • Several techniques that we have seen for the implementation of dictionaries can also be used for priority queues (not hash tables).

  • For instance, AVL trees can be used to implement a priority queue with cost \mathcal O(\log n) for insertions and deletions

Min-Heaps

A min-heap (cat: munt o munticles) is complete binary tree such that for each node its priority is smaller than the one of its children. Max-heaps are defines analogously.

Where is in the tree the element with smaller priority?

Representation of a heap

A (min-)heap with n elements can be represented as a vector T with n+1 positions. T[i] contains the priority of the node i.

  • The root of the tree is the node 1.
  • The left child of i is 2i (if 2i\leq n).
  • The right child of i is 2i +1 (if 2i+1\leq n).
  • For every i, T[i]\leq T[2i] and T[i]\leq T[2i+1].

What would change if we wanted to store a max-heap?

Why using 0 to store the root is not a good idea?

Where is the parent/father of i?

How many leaves a heap with say 2n elements have?

template <typename Elem, typename Prio>
class PriorityQueue {
    public:
        ...
    private:
        vector<pair<Elem, Prio>> h; // Component of index 0 is not used
        int nelems;
        void siftup(int j) throw();
        void sink(int j) throw();
};

template <typename Elem, typename Prio>
bool PriorityQueue<Elem,Prio>::empty() const {
    return nelems == 0;
}
template <typename Elem, typename Prio>
Elem PriorityQueue<Elem,Prio>::min() const {
    if (nelems == 0) throw EmptyPriorityQueue;
    return h[1].first;
}
template <typename Elem, typename Prio>
Prio PriorityQueue<Elem,Prio>::min_prio() const {
    if (nelems == 0) throw EmptyPriorityQueue;
    return h[1].second;
}

Heaps: Removing the minimum

  • Replace the root of the heap with the last element
  • Re-establish the heap order sinking the new root.

(see blackboard)

Removing the minimum — implementation

template <typename Elem, typename Prio>
void PriorityQueue<Elem,Prio>::remove_min() const {
    if (nelems == 0) throw EmptyPriorityQueue;
        swap(h[1], h[nelems]);
        --nelems;
        h.pop_back();
        sink(1);
    }

template <typename Elem, typename Prio>
void PriorityQueue<Elem,Prio>::sink(int j) {
    if (2 * j > nelems) return;
    int minchild = 2 * j;
    if (minchild < nelems and h[minchild].second > h[minchild + 1].second)
        ++minchild;
    if (h[j].second > h[minchild].second) {
        swap(h[j], h[minchild]);
        sink(minchild);
    }
}
1
This function has cost \mathcal O(\log(n/j))
2
if j has no left child we are at the last level
3
minchild is the index of the child with smaller priority

Heaps: Adding a new element

  • Add the new element at the end of the vector (i.e. as rightmost node of the last level of the heap or as the first element of a new deeper level)
  • Re-establish the heap order floating the new added element

(see blackboard)

Adding a new element — implementation

template <typename Elem, typename Prio>
void PriorityQueue<Elem,Prio>::insert(cons Elem& x, cons Prio& p) {
    ++nelems;
    h.push_back(make_pair(x, p));
    siftup(nelems);
}

template <typename Elem, typename Prio>
void PriorityQueue<Elem,Prio>::siftup(int j) {
    if (j == 1) return;
    int father = j / 2;
    if (h[j].second < h[father].second) {
        swap(h[j], h[father]);
        siftup(father);
    }
}
1
siftup has cost \mathcal O(\log j)
2
if j is the root we are done

Heapsort

Heapsort (Williams, 1964) sorts an array of n elements building a heap with the n elements and extracting them, one by one, from the heap.

The originally given array is used to build the heap; heapsort works in-place and only some constant auxiliary memory space is needed.

Since insertions and deletions in heaps have cost \mathcal O(\log n) the cost of the algorithm is \mathcal O(n\log n).

Heapsort — implementation

template <typename Elem>
void sink(Elem v[], int sz, int pos);
template <typename Elem>
void heapsort(Elem v[], int n) {
    make_heap(v, n);
    for (int i = n; i > 0; --i) {
        swap(v[1], v[i]);
        sink(v, i-1, 1);
    }
}

template <typename Elem>
void make_heap(Elem v[], int n) {
    for (int i = n/2; i > 0; --i)
        sink(v, n, i);
}
1
Sorts v[1..n] in ascending order (v[0] is unused)
2
extract largest element from the heap
3
sink the root to re-establish max-heap order in the subarray v[1..i-1]
4
make_heap establishes a (max) heap order in the array v[1..n] of Elem’s; Elem == priorities this is a.k.a. as heapify

Worst case cost of make_heap

template <typename Elem>
void make_heap(Elem v[], int n) {
    for (int i = n/2; i > 0; --i)
        sink(v, n, i);
}

Let B(n) be the worst-case cost of make_heap. Since the worst-case cost of sink(v,i-1,j) is \mathcal O(\log i). We have \begin{align*} B(n)&=\sum_{i=1}^{n/2} \mathcal O(\log n)=\mathcal O(n\log n) \end{align*}

Worst-case cost of heapsort

void heapsort(Elem v[], int n) {
    make_heap(v, n);
    for (int i = n; i > 0; --i) {
        swap(v[1], v[i]);
        sink(v, i-1, 1);
    }
}

The worst case cost of heapsort H(n) is \begin{align*} H(n)&=B(n)+ \sum_{i=1}^{n}\mathcal O(\log i) \\ &=\mathcal O(n\log n)+ \mathcal O(\log n!) \\ &=\mathcal O(n\log n) \end{align*} 

//Heapsort using priority_queue as a blackbox
#include<queue>
using namespace std;
template <typename elem>
void heap_sort (vector<elem>& v) {
    int n = v.size();
    priority_queue<elem> pq;
    for (int i = 0; i < n; ++i) 
        pq.push(v[i]);
    for (int i = n-1; i >= 0; --i) {
        v[i] = pq.top();
        pq.pop();
    } 
}

A possible visualization of heapsort.

Worst-case cost of make_heap — a better analysis

template <typename Elem>
void make_heap(Elem v[], int n) {
    for (int i = n/2; i > 0; --i)
        sink(v, n, i);
}

Let B(n) be the worst-case cost of make_heap. We have

B(n)=\Theta(n)\ .

(see blackboard)

This, of course, does not change the cost of heapsort but it is still useful.

k-th smallest elements

Suppose that given a vector with n elements we don’t want to completely order it, but say we only want to output in increasing order, for example the k smallest elements.

Using a min-heap to store the elements and getting the minimum k times, we can get the k smallest elements in ascending order with cost B(n)+\mathcal O(k\log n)=\mathcal O(n+k\log n)\ .

Which means \mathcal O(n) if k=\mathcal O(n/\log n).

Upcoming classes

Wednesday
Problem class P4 on dictionaries (do the exercises before class).
Next Monday
Theory class T7 on Graphs!




Questions?