Табдил додани BST бидуни массив


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Cisco Microsoft Лабораторияҳои SAP
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Дарахт

Изҳороти мушкилот

Масъалаи "Табдил додани BST ба Min-Heap бидуни истифодаи массив" мегӯяд, ки ба шумо BST дода мешавад (дарахти ҷустуҷӯии дуӣ) ва шумо бояд онро ба min-heap табдил диҳед. Min-heap бояд тамоми унсурҳои дарахти ҷустуҷӯии дутарафаро дар бар гирад. Алгоритм бояд дар мураккабии вақти хаттӣ иҷро шавад.

мисол

вуруди

Табдил додани BST бидуни массив

Натиҷаи

Табдил додани BST бидуни массив

Усули табдили BST ба Min-Heap бидуни истифодаи массив

Усули соддалавҳона

Масъалаи "Табдил додани BST-ро ба миқдори ками массив" ҳал кардан мумкин аст, агар мо аввал амали фармоишии фармоишро нигоҳ дорем дарахти ҷустуҷӯи бинарӣ. Ва пас аз ёфтани гардиши тартибӣ, мо ба сохтани min-heap шурӯъ мекунем (дарахти пурраи дуӣ, ки ҳамаи кӯдакон дар зери дарахт камтар аз волидайн доранд). Пас, чӣ гуна мо мина-теппа эҷод мекунем? Мо эҷод мекунем мина-теппа бо гузоштани сатҳи унсурҳо дар гардиши тартибот, ки хосияти пурраи дарахти дутарафаро таъмин мекунад. Ва азбаски мо гардиши фармоишӣ дорем, мо итминон дорем, ки хосияти min-heap қонеъ карда мешавад (волидайн нисбат ба ҳарду фарзандаш хурдтар аст). Аммо ин талаб мекунад, ки траверзи фармоишӣ нигоҳ дошта шавад.

Усули самаранок

Мо метавонем ин масъаларо дар фазои O (1) ҳал кунем, агар аввал дарахти ҷустуҷӯи бинарии худро ба рӯйхати алоқаманд табдил диҳем. Дар рӯйхати алоқаманд як шарт низ мавҷуд аст, ки он бояд бо тартиби мураттаб бошад. Барои ин, мо аввал аз зери дарахти рост мегузарем ва сипас аз зери дарахти чап мегузарем. Зеро мо гиреҳҳоро ба рӯйхати алоқаманд дар оғози он дохил мекунем. Ҳамин тавр, мо кафолат медиҳем, ки рӯйхати алоқаманд мураттаб боқӣ мемонад. Пас аз он, мо рӯйхати алоқаманди мураттабро дорем. Мо нишондиҳандаҳои чап ва рости гиреҳҳоро тавре месозем, ки хусусияти пурраи дарахти дуии мо қонеъ карда шавад. Вақте ки мо бо усули соддалавҳона рафтор мекардем, мо барои фароҳам овардани мин-теппа фармоишҳои дараҷавиро истифода бурдем. Дар ин ҷо низ мо ҳаминро истифода хоҳем кард.

рамз

Коди 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 

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо аввал дарахтро ба рӯйхати алоқаманд табдил додем ва пас гардиши фармоишии сатҳро муайян кардем. Ҳарду pf, ки амалиёти мураккабии вақт мебошанд. Ҳамин тариқ, мураккабии хаттии вақт ба даст оварда мешавад.

Мураккабии фазо

O (log N), зеро мо як навбатро барои дар сатҳи ягона нигоҳ доштани кӯдакон истифода кардем. Ин мураккабии фазои логарифмиро талаб мекунад. Аммо худи алгоритм дар ҷои худ кор мекунад.