STL dəstini istifadə edərək ikili ağacdan ikili axtarış ağacına çevirmə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Coursera google Həqiqətən microsoft OYO Otaqları
İkili Axtarış Ağacı İkili ağac AğacBaxılıb 51

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bizə a ikili ağac və bunu a-ya çevirməliyik ikili axtarış ağacı. Problem "STL dəsti istifadə edərək ikili ağacdan ikili axtarış ağacına çevrilməyə" problemi, STL dəsti istifadə edərək dönüşüm etməyi istər. Artıq müzakirə etdik ikili ağacın BST-yə çevrilməsi lakin Set istifadə edərək dönüşüm mövzusunu müzakirə etməmişdik. Dönüşüm zamanı yoxlanılması lazım olan bir şey, orijinal ağac quruluşunun eyni qalmasıdır.

misal

Input

Pin

Buraxılış

STL dəstini istifadə edərək ikili ağacdan ikili axtarış ağacına çevirməPin

 

Set istifadə edərək ikili ağacın BST-yə çevrilməsinə yanaşma

İkili ağacın ikili axtarış ağacına çevrilməsini əvvəlcədən müzakirə etdik, ancaq burada quraşdırılmış bir STL dəsti istifadə edəcəyik. Beləliklə yollardan biri əvvəlcə balanslı ikili axtarış ağacının qurulması ola bilər AVL ağacı və ya Qırmızı-Qara ağac. Və sonra yeni yaradılmış ağacın içərisindən keçid aparırıq və içindəki məzmunu bənzər bir qaydada orijinal ağacına köçürürük.

Yuxarıda müzakirə olunan yanaşma lazımsız bir öz-özünə tarazlıq verən ikili ağacın yaradılmasını tələb edir. Bunun qarşısını almaq üçün bir sıra əsaslı bir yanaşmanı müzakirə etdik. Bu yanaşmada əvvəlcə a xain üçündən sonra serialı sıraladı. Yenidən qeyri-qanuni bir keçidlə, başlanğıc ağacındakı elementləri əvəz etdik.

Bu yanaşmada bir sıra yaratmayacağıq və sonra sıralayacağıq. Elementi sıralanmış şəkildə saxlayan bir dəst istifadə edəcəyik. Beləliklə ağacdan keçib elementi içərisinə daxil etməyə davam edəcəyik təyin etmək. Daha sonra verilmiş ağacdakı elementləri əvəz edəcəyik.

Kodu

Set + istifadə edərək ikili ağacı BST-yə çevirmək üçün C ++ kodu

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

// defines the structure of a tree node
struct node{
    int data;
    node* left;
    node* right;
};

// inserts the given tree elements into the set
void insertIntoSet(node* root, set<int> &treeSet){
    if(root){
        insertIntoSet(root->left, treeSet);
        treeSet.insert(root->data);
        insertIntoSet(root->right, treeSet);
    }
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
void modifyBinaryTreeIntoBST(node* root, set<int> &treeSet)
{
    if(root){
        modifyBinaryTreeIntoBST(root->left, treeSet);
        root->data = *(treeSet.begin());
        treeSet.erase(treeSet.begin());
        modifyBinaryTreeIntoBST(root->right, treeSet);
    }
}

// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
    set<int> treeSet;
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
}

// creates and returns a new node with supplied node value
node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// simple in-order traversal
void inorder(node *root){
    if(root){
        inorder(root->left);
        cout<<root->data;
        inorder(root->right);
    }
}

int main()
{
    // constructing a binary tree
    // same as shown above
    node *root = create(1);
    root->right = create(2);
    root->right->left = create(4);
    root->right->left->left = create(5);
    root->right->left->right = create(3);

    cout<<"Inorder Traversal of given binary tree"<<endl;
    inorder(root);cout<<endl;
    binaryTreeToBST(root);
    cout<<"Inorder Traversal of modified tree\n";
    inorder(root);
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

Set istifadə edərək ikili ağacı BST-yə çevirmək üçün Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  // creates and returns a new node with supplied node value
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  // inserts the given tree elements into the set
  static void insertIntoSet(node root, TreeSet<Integer> treeSet){
    if(root != null){
      insertIntoSet(root.left, treeSet);
      treeSet.add(root.data);
      insertIntoSet(root.right, treeSet);
    }
  }

  // replace the elements of the initial tree
  // with elements in treeSet in in-order fashion
  static void modifyBinaryTreeIntoBST(node root, TreeSet<Integer> treeSet)
  {
    if(root != null){
      modifyBinaryTreeIntoBST(root.left, treeSet);
      root.data = treeSet.pollFirst();
      modifyBinaryTreeIntoBST(root.right, treeSet);
    }
  }

  // Converts Binary tree to BST
  static void binaryTreeToBST(node root)
  {
    TreeSet<Integer> treeSet = new TreeSet<>();
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
  }

  // simple in-order traversal
  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data);
      inorder(root.right);
    }
  }

  public static void main(String[] args)
  {
    // constructing a binary tree
    // same as shown above
    node root = create(1);
    root.right = create(2);
    root.right.left = create(4);
    root.right.left.left = create(5);
    root.right.left.right = create(3);

    System.out.println("Inorder Traversal of given binary tree");
    inorder(root);
    System.out.println();
    binaryTreeToBST(root);
    System.out.println("Inorder Traversal of modified tree");
    inorder(root);
  }
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N log N),  burada N ağacdakı elementlərin sayıdır. Burada logaritmik amil setə görə gəldi. Məlumat quruluşunu təyin etmək üçün bir element daxil etmək, axtarmaq və silmək üçün log N vaxtı lazımdır.

Kosmik Mürəkkəblik

O (N), burada qovşaqları dəstdə saxlamaq üçün əlavə yerdən istifadə etdik. Beləliklə, çevrilmə alqoritminin özü xətti kosmik mürəkkəbliyə, bütövlükdə proqramın da xətti kosmik mürəkkəbliyinə malikdir.

Crack Sistemi Dizayn Müsahibələri
Translate »