Бүлэг 13. Тэнцвэрт мод | Data Structures and Algorithms in C++

Агуулга: Энэ бүлэгт ашигласан программын кодуудыг энд үзүүллээ. Алгоритмын гүйцэтгэлийг сайжруулахын тулд модыг хамгийн муу тохиолдолд оруулахгүй байхаар зохион байгуулах хэрэгтэй. Модыг зохион байгуулах ийм аргыг бид энэ бүлгээр судлах болно. Энэ аргыг баланслах буюу тэнцүүлэх арга гэх бөгөөд тэнцвэрт мод үүсгэх хэд хэдэн алгоритм байдаг.

AVL мод

1. AVLtree классыг main() функцэд

// 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. Толгой файл: 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 модыг найз классаар

1. AVLtree классыг main() функцэд

// 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. Толгой файл: 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);
  }
}