Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

이진 검색 트리에서 왼쪽 회전을 수행하는 C++ 프로그램

<시간/>

이진 검색 트리는 모든 노드가 다음과 같은 두 가지 속성을 갖는 정렬된 이진 트리입니다.

노드의 오른쪽 하위 트리에는 상위 노드의 키보다 큰 모든 키가 있습니다.

노드의 왼쪽 하위 트리에는 상위 노드의 키보다 작은 모든 키가 있습니다. 각 노드는 2개 이상의 자식을 가질 수 없습니다.

트리 회전은 이진 트리에서 요소의 순서를 방해하지 않고 구조를 변경하는 작업입니다. 트리에서 한 노드를 위로 이동하고 아래로 한 노드를 이동합니다. 트리의 모양을 변경하고 작은 하위 트리를 아래로 이동하고 큰 하위 트리를 위로 이동하여 높이를 줄이는 데 사용되어 많은 트리 작업의 성능이 향상됩니다. 회전 방향은 트리 노드가 이동하는 쪽에 의존하지만 다른 사람들은 그것이 루트의 자리를 차지하는 자식에 달려 있다고 말합니다. 이진 탐색 트리에서 왼쪽 회전을 수행하는 C++ 프로그램입니다.

기능 설명:

높이(avl *) :주어진 AVL 트리의 높이를 계산합니다.

차이(avl *) :주어진 트리의 하위 트리 높이의 차이를 계산합니다.

avl *rr_rotat(avl *) :오른쪽 오른쪽 회전은 오른쪽 회전과 오른쪽 회전의 조합입니다.

avl *ll_rotat(avl *) :왼쪽-왼쪽 회전은 왼쪽 회전과 왼쪽 회전의 조합입니다.

avl *lr_rotat(avl*) :좌우 회전은 왼쪽 회전과 오른쪽 회전의 조합입니다.

이진 검색 트리에서 왼쪽 회전을 수행하는 C++ 프로그램

avl *rl_rotat(avl *) :오른쪽 회전과 왼쪽 회전의 조합입니다.

이진 검색 트리에서 왼쪽 회전을 수행하는 C++ 프로그램

avl * 균형(avl *) :균형 계수를 구하여 트리에 균형 연산을 수행합니다.

이진 검색 트리에서 왼쪽 회전을 수행하는 C++ 프로그램

avl * 삽입(avl*, int) :삽입 연산을 수행합니다. 이 함수를 사용하여 트리에 값을 삽입합니다.

show(avl*, int) :트리의 값을 표시합니다.

순차(avl *) :트리를 순서대로 순회합니다.

선주문(avl *) :사전 주문 방식으로 나무를 순회합니다.

포스터(avl*) :후순위 방식으로 나무를 순회합니다.

예시

#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
   int d;
   struct avl *l;
   struct avl *r;
}*r;
class avl_tree {
   public:
      int height(avl *);
      int difference(avl *);
      avl *rr_rotat(avl *);
      avl *ll_rotat(avl *);
      avl *lr_rotat(avl*);
      avl *rl_rotat(avl *);
      avl * balance(avl *);
      avl * insert(avl*, int);
      void show(avl*, int);
      void inorder(avl *);
      void preorder(avl *);
      void postorder(avl*);
      avl_tree() {
         r = NULL;
      }
};
int avl_tree::height(avl *t) {
   int h = 0;
   if (t != NULL) {
      int l_height = height(t->l);
      int r_height = height(t->r);
      int max_height = max(l_height, r_height);
      h = max_height + 1;
   }
   return h;
}
int avl_tree::difference(avl *t) {
   int l_height = height(t->l);
   int r_height = height(t->r);
   int b_factor = l_height - r_height;
   return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
   avl *t;
   t = parent->r;
   parent->r = t->l;
   t->l = parent;
   cout<<"Right-Right Rotation";
   return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
   avl *t;
   t = parent->l;
   parent->l = t->r;
   t->r = parent;
   cout<<"Left-Left Rotation";
   return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
   avl *t;
   t = parent->l;
   parent->l = rr_rotat(t);
   cout<<"Left-Right Rotation";
   return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
   avl *t;
   t= parent->r;
   parent->r = ll_rotat(t);
   cout<<"Right-Left Rotation";
   return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
   int bal_factor = difference(t);
   if (bal_factor > 1) {
      if (difference(t->l) > 0)
         t = ll_rotat(t);
      else
         t = lr_rotat(t);
   }
   else if (bal_factor < -1) {
      if (difference(t->r) > 0)
         t= rl_rotat(t);
      else
         t = rr_rotat(t);
   }
   return t;
}
avl *avl_tree::insert(avl *r, int v) {
   if (r == NULL) {
      r= new avl;
      r->d = v;
      r->l = NULL;
      r->r= NULL;
      return r;
   }
   else if (v< r->d) {
      r->l= insert(r->l, v);
      r = balance(r);
   }
   else if (v >= r->d) {
      r->r= insert(r->r, v);
      r = balance(r);
   }
   return r;
}
void avl_tree::show(avl *p, int l) {
   int i;
   if (p != NULL) {
      show(p->r, l+ 1);
      cout<<" ";
      if (p == r)
         cout << "Root -> ";
      for (i = 0; i < l&& p != r; i++)
         cout << " ";
      cout << p->d;
      show(p->l, l + 1);
   }
}
void avl_tree::inorder(avl *t) {
   if (t == NULL)
      return;
   inorder(t->l);
   cout << t->d << " ";
   inorder(t->r);
}
void avl_tree::preorder(avl *t) {
   if (t == NULL)
      return;
   cout << t->d << " ";
   preorder(t->l);
   preorder(t->r);
}
void avl_tree::postorder(avl *t) {
   if (t == NULL)
      return;
   postorder(t ->l);
   postorder(t ->r);
   cout << t->d << " ";
}
int main() {
   int c, i;
   avl_tree avl;
   while (1) {
      cout << "1.Insert Element into the tree" << endl;
      cout << "2.show Balanced AVL Tree" << endl;
      cout << "3.InOrder traversal" << endl;
      cout << "4.PreOrder traversal" << endl;
      cout << "5.PostOrder traversal" << endl;
      cout << "6.Exit" << endl;
      cout << "Enter your Choice: ";
      cin >> c;
      switch (c) {
         case 1:
            cout << "Enter value to be inserted: ";
            cin >> i;
            r= avl.insert(r, i);
         break;
         case 2:
            if (r == NULL) {
               cout << "Tree is Empty" << endl;
               continue;
            }
            cout << "Balanced AVL Tree:" << endl;
            avl.show(r, 1);
            cout<<endl;
         break;
         case 3:
            cout << "Inorder Traversal:" << endl;
            avl.inorder(r);
            cout << endl;
         break;
         case 4:
            cout << "Preorder Traversal:" << endl;
            avl.preorder(r);
            cout << endl;
         break;
         case 5:
            cout << "Postorder Traversal:" << endl;
            avl.postorder(r);
            cout << endl;
         break;
         case 6:
            exit(1);
         break;
         default:
            cout << "Wrong Choice" << endl;
      }
   }
   return 0;
}

출력

1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 13
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 10
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 15
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 5
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 11
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 4
Left-Left Rotation1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 8
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
4 5 8 10 11 13 15 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 4
Preorder Traversal:
10 5 4 8 13 11 15 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 5
Postorder Traversal:
4 8 5 11 16 15 13 10
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 14
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 3
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 7
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 9
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 52
Right-Right
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 6