Փոխակերպել BST- ն Min-Heap- ի ՝ առանց զանգված օգտագործելու


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Cisco Microsoft SAP լաբորատորիաներ
Երկուական որոնման ծառ Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«Փոխակերպել BST- ն` Min-Heap առանց զանգված օգտագործելու »խնդրում նշվում է, որ ձեզ տրվում է BST (երկուական որոնման ծառ) և անհրաժեշտ է այն վերածել min- կույտի: Min-heap- ը պետք է պարունակի երկուական որոնման ծառի բոլոր տարրերը: Ալգորիթմը պետք է աշխատի գծային ժամանակի բարդության մեջ:

Օրինակ

Մուտքային

Փոխակերպել BST- ն Min-Heap- ի ՝ առանց զանգված օգտագործելու

Արտադրողականություն

Փոխակերպել BST- ն Min-Heap- ի ՝ առանց զանգված օգտագործելու

Առանց զանգված օգտագործելու BST- ը Min-Heap- ի վերածելու մոտեցում

Միամիտ մոտեցում

«Փոխակերպել BST- ն Min-Heap առանց զանգված օգտագործելու» խնդիրը կարող է լուծվել, եթե մենք նախ պահենք կարգի անցումը երկուական որոնման ծառ, Եվ ըստ կարգի անցումը, մենք սկսում ենք ստեղծել min-heap (ամբողջական երկուական ծառ, որի բոլոր երեխաները ենթածառի մեջ ավելի փոքր են, քան ծնողը): Այսպիսով, ինչպե՞ս ենք ստեղծելու min- կույտը: Մենք կստեղծենք min- կույտ մակարդակով տարրերը տեղադրելով մակարդակի կարգի անցման մեջ, որը կապահովի երկուական ծառի ամբողջական հատկությունը: Եվ քանի որ մենք ունենք պատվերի շրջանցում, համոզված ենք, որ min-heap- ի հատկությունը բավարարված է (ծնողը փոքր է, քան իր երկու երեխաները): Բայց սա պահանջում է կարգի անցումային պահուստ:

Արդյունավետ մոտեցում

Մենք կարող ենք լուծել այս խնդիրը O (1) տարածքում, եթե նախ մեր երկուական որոնման ծառը վերածենք կապակցված ցուցակի: Կապված ցուցակում նույնպես կա մի պայման, որ այն պետք է լինի տեսակավորված ըստ հերթականության: Դա անելու համար մենք նախ անցնում ենք աջ ենթափայտը և այնուհետև անցնում ձախ ստորոտը: Քանի որ դրա սկզբում մենք հանգույցները տեղադրում ենք կապված ցուցակում: Այսպիսով, մենք ապահովում ենք, որ կապված ցանկը շարված լինի տեսակավորված: Մի անգամ, մենք ունենք մեր տեսակավորված կապակցված ցուցակը: Մենք վերադասավորում ենք հանգույցների ձախ և աջ ցուցիչները այնպես, որ մեր ամբողջական երկուական ծառի հատկությունը բավարարվի: Երբ մենք անում էինք միամիտ մոտեցում, մենք օգտագործեցինք մակարդակի կարգի անցում ՝ min-heap ստեղծելու համար: Այստեղ նույնպես մենք կօգտագործենք նույնը:

Կոդ

C ++ կոդ ՝ BST- ն Min-Heap փոխակերպելու համար ՝ առանց զանգված օգտագործելու

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

struct node{
    int data;
    node* left;
    node* right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// prints the level order traversal of the tree
void levelOrderTraversal(node *root)
{
  if (root == NULL) return;
    queue<node*> q;
    q.push(root);
  while(!q.empty()){
        int qSize = q.size();
        while(qSize--){
            node* nodeAtFront = q.front();
            q.pop();
            if(nodeAtFront->left)
                q.push(nodeAtFront->left);
            if(nodeAtFront->right)
                q.push(nodeAtFront->right);
            cout<<nodeAtFront->data<<" ";
        }
        cout<<endl;
  }
}

void convertBSTToLinkedList(node* root, node* &head_ref)
{
    if(!root)
        return;

  //first convert right subtree into linked list
  convertBSTToLinkedList(root->right, head_ref);
  // insert root into the linked list
  root->right = head_ref;
  //if head pointer exists, then point left pointer to NULL
  if(head_ref)
        head_ref->left = NULL;
    // now head of linked list is current root
    head_ref = root;
    // convert left subtrree recursively
  convertBSTToLinkedList(root->left, head_ref);
}

void convertLinkedListToMinHeap(node* &root, node* head)
{
  // Base Case
  if(!head)
    return;

    //traverse over the linked list in level order traversal fashion
  queue<node*> q;
    //first node of min heap will be smallest element
    //i.e. first element of inorder traversal
    root = head;
    // point head to next node
    head = head->right;
    // left is already null
    root->right = NULL;
    // insert into queue
    q.push(root);
  while(head)
  {
      node* nodeAtFront = q.front();
      q.pop();
      // now remove one node from linked list and make left child
      // if there are more nodes make a right child
      // push them into queue
      node* leftNode = head;
      head = head->right;
      leftNode->right = NULL;
      nodeAtFront->left = leftNode;
      q.push(leftNode);
      // similarly do the same for right child if it exists
      if(head){
            node* rightNode = head;
            head = head->right;
            rightNode->right = NULL;
            nodeAtFront->right = rightNode;
            q.push(rightNode);
      }
  }
}

// Function to convert BST into a Min-Heap
// without using any extra space
node* BSTToMinHeap(node* &root)
{
  // head of Linked List
  node *head = NULL;
  // get converted linked list
  convertBSTToLinkedList(root, head);
  // now set the root for min heap
  root = NULL;
  // convert the linked list into min heap
  convertLinkedListToMinHeap(root, head);
}

int main()
{

  node* root = create(5);
  root->left = create(4);
  root->right = create(6);
  root->left->left = create(2);
  root->left->right = create(3);

  BSTToMinHeap(root);

        levelOrderTraversal(root);

  return 0;
}
2
4 3
5 6

Java կոդ ՝ BST- ն Min-Heap փոխակերպելու համար ՝ առանց զանգված օգտագործելու

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }
 
  static void levelOrderTraversal(node root)
  {
    if (root == null) return;
      Queue<node> q = new LinkedList<>();
      q.add(root);
    while(!q.isEmpty()){
          int qSize = q.size();
          while(qSize-- > 0){
              node nodeAtFront = q.peek();
              q.remove();
              if(nodeAtFront.left != null)
                  q.add(nodeAtFront.left);
              if(nodeAtFront.right != null)
                  q.add(nodeAtFront.right);
              System.out.print(nodeAtFront.data+" ");
          }
          System.out.println();
    }
  }
  
  static node convertBSTToLinkedList(node root, node head_ref)
  {
      if(root == null)
          return head_ref;
  
    //first convert right subtree into linked list
    head_ref = convertBSTToLinkedList(root.right, head_ref);
    // insert root into the linked list
    root.right = head_ref;
    //if head pointer exists, then point left pointer to NULL
    if(head_ref != null)
          head_ref.left = null;
      // now head of linked list is current root
      head_ref = root;
      // convert left subtrree recursively
    head_ref = convertBSTToLinkedList(root.left, head_ref);
    
    return head_ref;
  }
  
  static node convertLinkedListToMinHeap(node root, node head)
  {
    // Base Case
    if(head == null)
      return null;
  
      //traverse over the linked list in level order traversal fashion
    Queue<node> q = new LinkedList<>();
      //first node of min heap will be smallest element
      //i.e. first element of inorder traversal
      root = head;
      // point head to next node
      head = head.right;
      // left is already null
      root.right = null;
      // insert into queue
      q.add(root);
    while(head != null)
    {
        node nodeAtFront = q.peek();
        q.remove();
        // now remove one node from linked list and make left child
        // if there are more nodes make a right child
        // push them into queue
        node leftNode = head;
        head = head.right;
        leftNode.right = null;
        nodeAtFront.left = leftNode;
        q.add(leftNode);
        // similarly do the same for right child if it exists
        if(head != null){
              node rightNode = head;
              head = head.right;
              rightNode.right = null;
              nodeAtFront.right = rightNode;
              q.add(rightNode);
        }
    }
    return root;
  }
  
  // Function to convert BST into a Min-Heap
  // without using any extra space
  static node BSTToMinHeap(node root)
  {
    // head of Linked List
    node head = null;
    // get converted linked list
    head = convertBSTToLinkedList(root, head);
    // now set the root for min heap
    root = null;
    // convert the linked list into min heap
    root = convertLinkedListToMinHeap(root, head);
    return root;
  }
  
  public static void main(String[] args)
  {
  
    node root = create(5);
    root.left = create(4);
    root.right = create(6);
    root.left.left = create(2);
    root.left.right = create(3);
  
    root = BSTToMinHeap(root);
  
      levelOrderTraversal(root);
  }

}
2 
4 3 
5 6 

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք նախ ծառը վերածել ենք կապակցված ցուցակի, այնուհետև id մակարդակի կարգի անցում: Երկուսն էլ pf, որոնք շարային ժամանակի բարդության գործողություն են: Այսպիսով, հասնում է գծային ժամանակի բարդությանը:

Տիեզերական բարդություն

O (տեղեկամատյան N), քանի որ մենք հերթ ենք օգտագործել ՝ երեխաներին մեկ մակարդակի վրա պահելու համար: Սա տևում է լոգարիթմական տիեզերական բարդությունից: Բայց ալգորիթմն ինքնին գործում է տեղում: