Unikal İkili Axtarış Ağacları

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg google
İkili Axtarış Ağacı İkili ağac Dinamik proqramlaşdırma AğacBaxılıb 40

Əvvəlcə biz tapmalıyıq ümumi sayma sayı unikal ikili axtarış ağacı yaratmaq. Bundan sonra mümkün olan bütün bənzərsiz BST-ni qururuq. Əvvəlcə BST-nin tikintisini bilməliyik. Bir İkili Axtarış Ağacı, sol alt ağacda olan qovşaqlar wrt. içindəki hər hansı bir qovşaq həmişə sağ alt ağacdakı qovşaqlardan azdır. N qovşaqlarının (1-dən N-ə) yaratdığı BST-nin aşağıdakı diaqramlarına baxaq.

Üçün N, bütün mümkün unikal BST formasını hazırlayırıq:

Unikal İkili Axtarış AğaclarıPin

Unikal İkili Axtarış AğaclarıPin

Unikal İkili Axtarış AğaclarıPin

Pin

Pin

N = 3 üçün 5 unikal BST qurduq.

BST-nin ümumi sayı kök seçmə üsullarının, sol alt ağacların sayının və sağ alt ağacların sayının məhsuluna bərabərdir.

Rekursiyadan istifadə edərək BST sayını tapa bilərik:

  1.  1-i kök olaraq seçin, sol alt ağacda heç bir element yoxdur. N-1 elementləri sağ alt ağacda mövcuddur.
  2.  Sol alt ağacda kök olaraq 2, 1 element seçin. N-2 elementləri sağ alt ağacda mövcuddur.
  3. Eynilə, sol alt ağacda mövcud kök, i-1 elementləri olaraq i seçin. Sağ alt ağacdakı Ni elementləri.

Sonra, BST-lərin ümumi sayı C (N) = C (0) * C (N-1) + C (1) * C (N-2) + ……… + C (i-1) * C (Ni) + …………. + C (N-1) * C (0).

Unikal İkili Axtarış Ağacları

Bu düstura kimi də deyilir Nth-Katalan nömrəsi.

Nth-Katalan nömrəsini tapmaq üçün tətbiqetmə

/*C++ Implementation for finding Nth-Catalan Number*/ 
#include<bits/stdc++.h>
using namespace std;
long long int ncr(long long int n, long long int r) 
{ 
    long long int res=1; 
    /*C(n,r)=C(n,n-r)*/
    if(r>n-r)
    {
        r=n-r;
    }
    /*Calculate value of [n*(n-1)*---*(n-r+1)] / [r*(r-1)*---*1]*/ 
    for(int i=0;i<r;i++) 
    { 
        res*=(n-i); 
        res/=(i+1); 
    } 
    return res; 
} 
/*Function which return Nth Catalan Number*/
long long int nth_catalan(int n) 
{ 
    /*Calculate value of 2nCn*/ 
    long long int c=ncr(2*n,n); 
    /*return 2nCn/(n+1)*/ 
    return c/(n+1); 
}
int main() 
{ 
    int n;
    /*input value*/
    cin>>n;
    cout<<nth_catalan(n)<<endl;
    return 0; 
}
5
42

Zamanın mürəkkəbliyi

O (N) yəni mürəkkəbliyi o deməkdir xətti. [N * (n-1) * - * (n-r + 1)] / [r * (r-1) * - * 1] dəyərini hesablamaq üçün döngə üçün bir təkrarlayın.

Alqoritm

Algorithm:
Step:1 Create a list for storing the root of the BST.
Step:2 For i in range 1 to N:
       i) Create a new node(temp) and assign its data as i.
       ii) Construct list of all left subtrees using recursion.
       iii) Construct list of all right subtrees using recursion.
Step:3 Traverse all left subtrees:
       i) For the current left subtree, traverse all right subtrees.
       ii) Add both left and right subtrees to temp.
       iii) Add temp to the list.

Unikal ikili axtarış ağacları üçün tətbiqetmə

/*C++ Implementation for Print the inorder traversal of all possible BST's by constructing them.*/ 
#include<bits/stdc++.h>
using namespace std;
struct node 
{ 
  int data; 
  struct node *left, *right; 
}; 
/*create a Node*/ 
struct node *newNode(int item) 
{ 
  struct node *temp = new node; 
  temp->data = item; 
  temp->left = temp->right = NULL; 
  return temp; 
}
void preorder(struct node *root) 
{ 
  if(root!=NULL) 
  { 
      cout<<root->data<<" ";
      preorder(root->left);
    preorder(root->right); 
  } 
}
/*function for constructing BST's*/
vector<struct node *> bst(int start, int end) 
{ 
  vector<struct node *> list; 
  /*if start>end then subtree will be empty so returning NULL in the list */
  if(start>end) 
  { 
    list.push_back(NULL); 
    return list; 
  } 
  /*iterating through all values from start to end for constructing left and right subtree recursively */
  for(int i=start;i<=end;i++) 
  { 
    /* constructing left subtree */
    vector<struct node *> leftSubtree = bst(start, i - 1); 
    /* constructing right subtree */
    vector<struct node *> rightSubtree = bst(i + 1, end); 
    /* now looping through all left and right subtrees and connecting them to ith root below */
    for(int j=0;j<leftSubtree.size();j++) 
    { 
      struct node* left = leftSubtree[j]; 
      for(int k=0;k<rightSubtree.size();k++) 
      { 
        struct node* right = rightSubtree[k]; 
        struct node* node = newNode(i);// making value i as root 
        node->left = left;// connect left subtree 
        node->right = right;// connect right subtree 
        list.push_back(node);// add this tree to list 
      } 
    } 
  } 
  return list; 
} 
int main() 
{ 
    int n;
    /*input value*/
    cin>>n;
    /*construct all bst's*/
    vector<struct node *> all_bst= bst(1,n);
    cout<<"Printing Preorder traversal of all constructed BSTs are: "<<endl; 
    for(int i=0;i<all_bst.size();i++) 
    { 
       preorder(all_bst[i]); 
       cout<<endl; 
    } 
    return 0; 
}
5
Printing Preorder traversal of all constructed BSTs are: 
1 2 3 4 5 
1 2 3 5 4 
1 2 4 3 5 
1 2 5 3 4 
1 2 5 4 3 
1 3 2 4 5 
1 3 2 5 4 
1 4 2 3 5 
1 4 3 2 5 
1 5 2 3 4 
1 5 2 4 3 
1 5 3 2 4 
1 5 4 2 3 
1 5 4 3 2 
2 1 3 4 5 
2 1 3 5 4 
2 1 4 3 5 
2 1 5 3 4 
2 1 5 4 3 
3 1 2 4 5 
3 1 2 5 4 
3 2 1 4 5 
3 2 1 5 4 
4 1 2 3 5 
4 1 3 2 5 
4 2 1 3 5 
4 3 1 2 5 
4 3 2 1 5 
5 1 2 3 4 
5 1 2 4 3 
5 1 3 2 4 
5 1 4 2 3 
5 1 4 3 2 
5 2 1 3 4 
5 2 1 4 3 
5 3 1 2 4 
5 3 2 1 4 
5 4 1 2 3 
5 4 1 3 2 
5 4 2 1 3 
5 4 3 1 2 
5 4 3 2 1

Zaman mürəkkəbliyi

O (N * V) burada N - qovşaq sayı, V - Nth Katalan nömrəsinin dəyəri. Bütün bst-lərin n Katalon ədədi ilə bərabər olan əvvəlcədən sifariş keçidini çap edirik və əvvəlcədən keçidin zaman mürəkkəbliyinin BT-dəki N qovluq sayının O (N) olduğunu bilirik.

References

Translate »