Chapter 13. Balanced tree | Data Structures and Algorithms in C++

The following source codes are used in this chapter.

AVL trees

1. Main function using AVLtree class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 13: Balanced trees

// AVL: Demonstration program for AVL trees;
//      insertion and deletion of nodes

#include "avl_tree.h"



int main() {
  int x;
  char ch;
  AVLtree<int> t;
  cout <<
    "\nAVL tree displayed by this program has\n"
    "its root on the left. Turn it 90 degrees\n"
    "clockwise to obtain its usual representation.\n\n";
  for ( ; ; ) {
    cout <<
      "Enter an integer, then  I for insertion\n"
      "or by D for deletion, or enter Q to quit: ";
    cin >> x >> ch;
    if (cin.fail()) break;
    ch = toupper(ch);
    if (ch == 'I') t.insert(t.getroot(),x); else
      if (ch == 'D') t.delNode(t.getroot(),x);
    t.print(t.getroot());
  }
  return 0;
}

2. Header file: avl_tree.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 13: Balanced trees

// AVL: Demonstration program for AVL trees;
//      insertion and deletion of nodes
// File name: avl_tree.h

#include <iostream>
#include <iomanip>
using namespace std;

template <class Type>
class AVLtree {
  struct Node {
    Type data;
    int bf; 
    Node *l, *r;
  };
  Node *root;
  void rrRotate(Node* &p);
  void llRotate(Node* &p);
public:
  AVLtree():root(NULL){}
  Node *&getroot() { return root; }
  int insert(Node* &p, Type x);
  int delNode(Node* &p, Type x);
  void print(Node *p, int ws = 0); 
};

template <class Type>
void AVLtree<Type>::rrRotate(Node* &p) {
  Node *q = p;
  p = p->r;
  q->r = p->l;
  p->l = q;
  q->bf--;
  if (p->bf > 0) q->bf -= p->bf;
  p->bf--;
  if (q->bf < 0) p->bf += q->bf;
}

template <class Type>
void AVLtree<Type>::llRotate(Node* &p) {
  Node *q = p;
  p = p->l;
  q->l = p->r;
  p->r = q;
  q->bf++;
  if (p->bf < 0) q->bf -= p->bf;
  p->bf++;
  if (q->bf > 0) p->bf += q->bf;
}

template <class Type>
int AVLtree<Type>::insert(Node* &p, Type x) {
  int dh=0;
  if (p == NULL) {
    p = new Node;
    p->data = x; p->bf = 0;
    p->l = p->r = NULL;
    dh = 1; // Tree height increased by 1
  } else
    if (x > p->data) {
      if (insert(p->r, x)) {
    p->bf++; // Height of right subtree increased 
    if (p->bf == 1) dh = 1; else
      if (p->bf == 2) {
        if (p->r->bf == -1) llRotate(p->r);
            rrRotate(p);
      }
      }
    } else
      if (x < p->data) {
    if (insert(p->l, x)) {
      p->bf--; // Height of left subtree increased 
      if (p->bf == -1) dh = 1; else
        if (p->bf == -2) {
          if (p->l->bf == 1) rrRotate(p->l);
          llRotate(p);
        }
    }
      }
  return dh;
}

template <class Type>
int AVLtree<Type>::delNode(Node* &p, Type x) {
  Node **qq, *p0;
  int dh=0;
  if (p == NULL) return 0;
  if (x < p->data) {
    if (delNode(p->l, x)) {
      p->bf++; // Height left subtree decreased
      if (p->bf == 0) dh = 1; else
    if (p->bf == 2) {
      if (p->r->bf == -1) llRotate(p->r);
      rrRotate(p);
      if (p->bf == 0) dh = 1;
    }
    }
  } else
    if (x > p->data) {
      if (delNode(p->r, x)) {
    p->bf--; // Height right subtree decreased
    if (p->bf == 0) dh = 1; else
      if (p->bf == -2) {
        if (p->l->bf == 1) rrRotate(p->l);
            llRotate(p);
            if (p->bf == 0) dh = 1;
      }
      }
    } else {  // x == p->data
      if (p->r == NULL) {
    p0 = p; p = p->l; delete p0; return 1;
      } else
    if (p->l == NULL) {
      p0 = p; p = p->r; delete p0; return 1;
    } else {
      qq = & p->l;
      while ((*qq)->r != NULL) qq = & (*qq)->r;
      p->data = (*qq)->data;
      (*qq)->data = x;
      if (delNode(p->l, x)) {
        p->bf++; // Height left subtree decreased
            if (p->bf == 0) dh = 1; else
          if (p->bf == 2) {
        if (p->r->bf == -1) llRotate(p->r);
        rrRotate(p);
        if (p->bf == 0) dh = 1;
          }
      }
    }
    }
  return dh;
}

template <class Type>
void AVLtree<Type>::print(Node *p, int ws) {
  if (p != NULL) {
    print(p->r, ws+=6);
    cout << setw(ws) << p->data << " " << p->bf << endl;
    print(p->l, ws);
  }
}

AVL trees using Friend class

1. Main function using AVLtree class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 13: Balanced trees

// AVL: Demonstration program for AVL trees;
//      insertion and deletion of nodes
// using friend class

#include "avl_tree_fc.h"

int main() {
  int x;
  char ch;
  AVLtree<int> t;
  cout <<
    "\nAVL tree displayed by this program has\n"
    "its root on the left. Turn it 90 degrees\n"
    "clockwise to obtain its usual representation.\n\n";
  for ( ; ; ) {
    cout <<
      "Enter an integer, then  I for insertion\n"
      "or by D for deletion, or enter Q to quit: ";
    cin >> x >> ch;
    if (cin.fail()) break;
    ch = toupper(ch);
    if (ch == 'I') t.insert(t.getroot(),x); else
      if (ch == 'D') t.delNode(t.getroot(),x);
    t.print(t.getroot());
  }
  return 0;
}

2. Header file: avl_tree_fc.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 13: Balanced trees

// AVL: Demonstration program for AVL trees;
//      insertion and deletion of nodes
// using friend class
// File name : avl_tree_fc.h

#include <iostream>
#include <iomanip>
using namespace std;

template <class Type>
class Node {
  template <class> friend class AVLtree;
  Type data;
  int bf; 
  Node *l, *r;
};

template <class Type>
class AVLtree {
  Node<Type> *root;
  void rrRotate(Node<Type>* &p);
  void llRotate(Node<Type>* &p);
public:
  AVLtree():root(NULL){}
  Node<Type> *&getroot() { return root; }
  int insert(Node<Type>* &p, Type x);
  int delNode(Node<Type>* &p, Type x);
  void print(Node<Type> *p, int ws = 0); 
};

template <class Type>
void AVLtree<Type>::rrRotate(Node<Type>* &p) {
  Node<Type> *q = p;
  p = p->r;
  q->r = p->l;
  p->l = q;
  q->bf--;
  if (p->bf > 0) q->bf -= p->bf;
  p->bf--;
  if (q->bf < 0) p->bf += q->bf;
}

template <class Type>
void AVLtree<Type>::llRotate(Node<Type>* &p) {
  Node<Type> *q = p;
  p = p->l;
  q->l = p->r;
  p->r = q;
  q->bf++;
  if (p->bf < 0) q->bf -= p->bf;
  p->bf++;
  if (q->bf > 0) p->bf += q->bf;
}

template <class Type>
int AVLtree<Type>::insert(Node<Type>* &p, Type x) {
  int dh=0;
  if (p == NULL) {
    p = new Node<Type>;
    p->data = x; p->bf = 0;
    p->l = p->r = NULL;
    dh = 1; // Tree height increased by 1
  } else
    if (x > p->data) {
      if (insert(p->r, x)) {
    p->bf++; // Height of right subtree increased 
    if (p->bf == 1) dh = 1; else
      if (p->bf == 2) {
        if (p->r->bf == -1) llRotate(p->r);
            rrRotate(p);
      }
      }
    } else
      if (x < p->data) {
    if (insert(p->l, x)) {
      p->bf--; // Height of left subtree increased 
      if (p->bf == -1) dh = 1; else
        if (p->bf == -2) {
          if (p->l->bf == 1) rrRotate(p->l);
          llRotate(p);
        }
    }
      }
  return dh;
}

template <class Type>
int AVLtree<Type>::delNode(Node<Type>* &p, Type x) {
  Node<Type> **qq, *p0;
  int dh=0;
  if (p == NULL) return 0;
  if (x < p->data) {
    if (delNode(p->l, x)) {
      p->bf++; // Height left subtree decreased
      if (p->bf == 0) dh = 1; else
    if (p->bf == 2) {
      if (p->r->bf == -1) llRotate(p->r);
      rrRotate(p);
      if (p->bf == 0) dh = 1;
    }
    }
  } else
    if (x > p->data) {
      if (delNode(p->r, x)) {
    p->bf--; // Height right subtree decreased
    if (p->bf == 0) dh = 1; else
      if (p->bf == -2) {
        if (p->l->bf == 1) rrRotate(p->l);
            llRotate(p);
            if (p->bf == 0) dh = 1;
      }
      }
    } else {  // x == p->data
      if (p->r == NULL) {
    p0 = p; p = p->l; delete p0; return 1;
      } else
    if (p->l == NULL) {
      p0 = p; p = p->r; delete p0; return 1;
    } else {
      qq = & p->l;
      while ((*qq)->r != NULL) qq = & (*qq)->r;
      p->data = (*qq)->data;
      (*qq)->data = x;
      if (delNode(p->l, x)) {
        p->bf++; // Height left subtree decreased
            if (p->bf == 0) dh = 1; else
          if (p->bf == 2) {
        if (p->r->bf == -1) llRotate(p->r);
        rrRotate(p);
        if (p->bf == 0) dh = 1;
          }
      }
    }
    }
  return dh;
}

template <class Type>
void AVLtree<Type>::print(Node<Type> *p, int ws) {
  if (p != NULL) {
    print(p->r, ws+=6);
    cout << setw(ws) << p->data << " " << p->bf << endl;
    print(p->l, ws);
  }
}