โปรแกรม C++ ตรวจสอบว่า Binary Tree เป็น AVL Tree หรือไม่

AVL Tree เป็น Binary Search Tree ที่ปรับสมดุลด้วยตัวเอง โดยที่ความต่างของความสูงระหว่าง subtree ซ้ายและขวาไม่เกิน 1 สำหรับทุกโหนด

นี่คือโปรแกรม C++ เพื่อตรวจสอบว่า Binary Tree ที่กำหนดเป็น AVL Tree หรือไม่

อัลกอริทึม

Begin
  function AVL() คืนค่า true ถ้าต้นไม้เป็น AVL มิฉะนั้น false
    if (root == NULL) return 1
    leftheight = height(root->left)
    rightheight = height(root->right)
    if (abs(leftheight - rightheight) <= 1 && AVL(root->left) && AVL(root->right))
      return 1
    return 0
End

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class nod {
public:
  int data;
  nod* l;
  nod* r;
};

nod* newNod(int d) {
  nod* Nod = new nod();
  Nod->data = d;
  Nod->l = NULL;
  Nod->r = NULL;
  return Nod;
}

int max(int x, int y) {
  return (x >= y) ? x : y;
}

int height(nod* node) {
  if (node == NULL) return 0;
  return 1 + max(height(node->l), height(node->r));
}

bool AVL(nod *root) {
  int lh, rh;
  if (root == NULL) return 1;
  lh = height(root->l);
  rh = height(root->r);
  if (abs(lh - rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1;
  return 0;
}

int main() {
  nod *root = newNod(7);
  root->l = newNod(6);
  root->r = newNod(12);
  root->l->l = newNod(4);
  root->l->r = newNod(5);
  root->r->r = newNod(13);
  if (AVL(root))
    cout << "The Tree is AVL Tree" << endl;
  else
    cout << "The Tree is not AVL Tree " << endl;

  nod *root1 = newNod(7);
  root1->l = newNod(6);
  root1->r = newNod(12);
  root1->l->l = newNod(4);
  root1->l->r = newNod(5);
  root1->r->r = newNod(13);
  root1->r->r->r = newNod(26);
  if (AVL(root1))
    cout << "The Tree is AVL Tree" << endl;
  else
    cout << "The Tree is not AVL Tree " << endl;
  return 0;
}

ผลลัพธ์

The Tree is AVL Tree
The Tree is not AVL Tree