Tree 11.9 Latihan (Kelompok 1)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <sstream>
#define pow2(n) (1 << (n))
using namespace std;
struct avl_node {
  int data;
  struct avl_node *left;
  struct avl_node *right;
} *root;
class avlTree {
 public:
  int height(avl_node *);
  int diff(avl_node *);
  avl_node *rr_rotation(avl_node *);
  avl_node *ll_rotation(avl_node *);
  avl_node *lr_rotation(avl_node *);
  avl_node *rl_rotation(avl_node *);
  avl_node *balance(avl_node *);
  avl_node *insert(avl_node *, int);
  void display(avl_node *, int);
  avlTree() { root = NULL; }
};
// Height of AVL Tree
int avlTree::height(avl_node *temp) {
  int h = 0;
  if (temp != NULL) {
    int l_height = height(temp->left);
    int r_height = height(temp->right);
    int max_height = max(l_height, r_height);
    h = max_height + 1;
  }
  return h;
}
// Height Difference
int avlTree::diff(avl_node *temp) {
  int l_height = height(temp->left);
  int r_height = height(temp->right);
  int b_factor = l_height - r_height;
  return b_factor;
}
// Right- Right Rotation
avl_node *avlTree::rr_rotation(avl_node *parent) {
  avl_node *temp;
  temp = parent->right;
  parent->right = temp->left;
  temp->left = parent;
  return temp;
}
// Left- Left Rotation
avl_node *avlTree::ll_rotation(avl_node *parent) {
  avl_node *temp;
  temp = parent->left;
  parent->left = temp->right;
  temp->right = parent;
  return temp;
}
// Left - Right Rotation
avl_node *avlTree::lr_rotation(avl_node *parent) {
  avl_node *temp;
  temp = parent->left;
  parent->left = rr_rotation(temp);
  return ll_rotation(parent);
}
// Right- Left Rotation
avl_node *avlTree::rl_rotation(avl_node *parent) {
  avl_node *temp;
  temp = parent->right;
  parent->right = ll_rotation(temp);
  return rr_rotation(parent);
}
// Balancing AVL Tree
avl_node *avlTree::balance(avl_node *temp) {
  int bal_factor = diff(temp);
  if (bal_factor > 1) {
    if (diff(temp->left) > 0)
      temp = ll_rotation(temp);
    else
      temp = lr_rotation(temp);
  } else if (bal_factor < -1) {
    if (diff(temp->right) > 0)
      temp = rl_rotation(temp);
    else
      temp = rr_rotation(temp);
  }
  return temp;
}
// Insert Node Kedalam Tree
avl_node *avlTree::insert(avl_node *root, int value) {
  if (root == NULL) {
    root = new avl_node;
    root->data = value;
    root->left = NULL;
    root->right = NULL;
    return root;
  } else if (value < root->data) {
    root->left = insert(root->left, value);
    root = balance(root);
  } else if (value >= root->data) {
    root->right = insert(root->right, value);
    root = balance(root);
  }
  return root;
}
// Menampilkan AVL Tree
void avlTree::display(avl_node *ptr, int level) {
  int i;
  if (ptr != NULL) {
    display(ptr->right, level + 1);
    cout << endl;
    if (ptr == root){
        cout << "Root -> ";
    }
    for (i = 0; i < level && ptr != root; i++){
        cout << "        ";
    }
    cout << ptr->data;
    display(ptr->left, level + 1);
  }
}
int main() {
  avlTree avl;
  int nilai;
  cout << "Masukkan nilai data berikut:" << endl;
  // sisip data 10 bilangan acak dari 0-99 ke dalam tree
  srand(time(NULL));
  for (int i = 0; i < 5; i++) {
    nilai = rand() % 100;
    cout << nilai << " ";
    root = avl.insert(root, nilai);
  }
  avl.display(root, 1);
  return 0;
}