STL багц ашиглан хоёртын модноос хоёртын хайлтын модыг хөрвүүлэх


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Coursera Google-ийн Үнэндээ Microsoft- OYO өрөөнүүд
Хоёртын хайлтын мод Хоёртын мод Мод

Асуудлын мэдэгдэл

Бидэнд a хоёртын мод бид үүнийг а болгон хөрвүүлэх хэрэгтэй хоёртын хайлтын мод. Асуудал нь "STL багц ашиглан хоёртын модноос хоёртын хайлтын модыг хөрвүүлэх" нь STL багц ашиглан хөрвүүлэлт хийхийг хүсдэг. Бид аль хэдийн хэлэлцсэн хоёртын модыг BST болгон хөрвүүлэх гэхдээ бид Set ашиглан хөрвүүлэх талаар ярилцаагүй байсан. Хөрвүүлэлтийг шалгах шаардлагатай бол модны анхны бүтэц өөрчлөгдөхгүй байх ёстой.

Жишээ нь

Оролт

гаралтын

STL багц ашиглан хоёртын модноос хоёртын хайлтын модыг хөрвүүлэх

 

Set-ийг ашиглан хоёртын модыг BST болгон хөрвүүлэх арга

Хоёртын модыг хоёртын хайлтын мод болгон хөрвүүлэх талаар бид аль хэдийн ярилцсан боловч энд суулгаагүй STL багцыг ашиглах болно. Тиймээс нэг арга бол тэнцвэртэй хоёртын хайлтын модыг бүтээх явдал юм AVL мод эсвэл Улаан-Хар мод. Дараа нь бид шинээр бүтээсэн модны хөндлөн огтлолцол хийж, агуулгыг анхны мод руу ижил төстэй хэв маягаар хуулж ав.

Дээр дурдсан арга барил нь шаардлагагүй өөрийгөө тэнцвэржүүлэх хоёртын модыг бий болгохыг шаарддаг. Үүнээс зайлсхийхийн тулд массивт суурилсан хандлагын талаар ярилцав. Энэ хандлагаар бид эхлээд a хөндлөн гурвын дараа массивыг ангилав. Дахин хөндлөн огтлолоор бид эхний модны элементүүдийг сольсон.

Энэ аргаар бид массив үүсгэхгүй бөгөөд дараа нь эрэмбэлэх болно. Бид элементийг эрэмбэлсэн хэлбэрээр хадгалах багцыг ашиглах болно. Тиймээс бид модыг туулж, элементийг үргэлжлүүлэн оруулах болно багц. Үүний дараа бид өгөгдсөн модны элементүүдийг орлуулах болно.

код

Set + ашиглан хоёртын модыг BST болгон хөрвүүлэх C ++ код

#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 ашиглан хоёртын модыг BST болгон хөрвүүлэх Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N log N),  энд N нь модны элементүүдийн тоо юм. Олонлогийн улмаас логарифмын хүчин зүйл энд ирэв. Өгөгдлийн бүтцийг тохируулахдаа элемент оруулах, хайх, устгахад бүртгэлийн N цаг хугацаа шаардагдана.

Сансрын нарийн төвөгтэй байдал

O (N), энд бид багц дахь зангилааг хадгалах нэмэлт зай ашигласан болно. Тиймээс хөрвүүлэх алгоритм нь өөрөө шугаман орон зайн нарийн төвөгтэй бөгөөд програм нь бүхэлдээ орон зайн шугаман нарийн төвөгтэй байдаг.