የ STL ስብስብን በመጠቀም ሁለትዮሽ ዛፍ ወደ ሁለትዮሽ ፍለጋ የዛፍ መለወጥ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን Coursera google በእርግጥም የ Microsoft ኦዮ ክፍሎች
የሁለትዮሽ ፍለጋ ዛፍ ሁለትዮሽ ዛፍ ዛፍ

የችግሩ መግለጫ

ተሰጠን ሁለትዮሽ ዛፍ እና ወደ ሀ መለወጥ ያስፈልገናል የሁለትዮሽ ፍለጋ ዛፍ. የ “STL ቅንብርን በመጠቀም ከሁለትዮሽ ዛፍ ወደ ሁለትዮሽ ፍለጋ የዛፍ መለወጥ” ችግሩ STL ን በመጠቀም ልወጣ ለማድረግ ይጠይቃል። ቀደም ብለን ተወያይተናል የሁለትዮሽ ዛፍ ወደ BST መለወጥ ግን ሴትን በመጠቀም ስለ መለወጥ አልተነጋገርንም ፡፡ መፈተሽ ያለበት አንድ ነገር መለወጥ ግን ዋናው የዛፉ አወቃቀር ተመሳሳይ መሆን አለበት የሚለው ነው ፡፡

ለምሳሌ

ግቤት

ዉጤት

የ STL ስብስብን በመጠቀም ሁለትዮሽ ዛፍ ወደ ሁለትዮሽ ፍለጋ የዛፍ መለወጥ

 

ሴትን በመጠቀም የሁለትዮሽ ዛፍ ወደ BST ለመቀየር አቀራረብ

እኛ የሁለትዮሽ ዛፍ ወደ ሁለትዮሽ ፍለጋ ዛፍ ስለመቀየር ቀደም ብለን ተወያይተናል ፣ ግን እዚህ እኛ ወደ ውስጥ ያልገባ STL Set ን እንጠቀማለን ፡፡ ስለዚህ አንደኛው መንገድ መጀመሪያ ሚዛናዊ የሁለትዮሽ ፍለጋ ዛፍ መገንባት ሊሆን ይችላል AVL ዛፍ ወይም ቀይ-ጥቁር ዛፍ እና ከዚያ አዲስ የተፈጠረውን ዛፍ ውስጠ-ጥሰትን እናከናውን እና ይዘቱን ወደ መጀመሪያው ዛፍ በተመሳሳይ የመገልበጫ ዘይቤ እንገለብጣለን።

ከላይ የተወያየው አካሄድ አላስፈላጊ ራስን ሚዛናዊ የሁለትዮሽ ዛፍ መፍጠርን ይጠይቃል ፡፡ ስለዚህ ይህንን ለማስቀረት በአንድ ድርድር ላይ የተመሠረተ አቀራረብን ተወያይተናል ፡፡ በዚያ አካሄድ በመጀመሪያ እኛ አደረግን መተላለፍ የሦስቱን እና ከዚያም ድርድርን ደርድር። እንደገና በአይነምድር መተላለፍ ፣ በመነሻ ዛፍ ውስጥ ያሉትን ንጥረ ነገሮች ተክተናል ፡፡

በዚህ አካሄድ ድርድር አንፈጥርም ከዚያ አናስተካክለውም ፡፡ ንጥረ ነገሩን በተስተካከለ ሁኔታ እንዲቆይ የሚያደርግ ስብስብ እንጠቀማለን። ስለዚህ ዛፉን እናቋርጣለን እና ንጥረ ነገሩን ወደ ውስጥ ማስገባት እንቀጥላለን ስብስብ. ከዚያ በኋላ በተሰጠው ዛፍ ውስጥ ያሉትን ንጥረ ነገሮች እንተካለን ፡፡

ኮድ

ሴትን በመጠቀም ሁለትዮሽ ዛፍ ወደ 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

የጃቫ ኮድ ሴትን በመጠቀም የሁለትዮሽ ዛፍ ወደ BST ለመቀየር

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N log N) ፣  N በዛፉ ውስጥ ያሉት ንጥረ ነገሮች ብዛት የት ነው። እዚህ የሎጋሪዝም ንጥረ ነገር ከስብስቡ የተነሳ መጣ ፡፡ አንድን ንጥረ ነገር ለማስገባት ፣ ለመፈለግ እና ለመሰረዝ የውሂብ መዋቅርን ያዘጋጁ የምዝግብ ማስታወሻ N ጊዜ ይፈልጋል።

የቦታ ውስብስብነት

ኦ (ኤን)፣ እዚህ አንጓዎችን በስብስቡ ውስጥ ለማስቀመጥ ተጨማሪ ቦታ ተጠቅመናል። ስለዚህ ለመለወጥ ስልተ ቀመር ራሱ መስመራዊ የቦታ ውስብስብነት አለው እንዲሁም ፕሮግራሙ በአጠቃላይ መስመራዊ የቦታ ውስብስብነት አለው ፡፡