Перетворіть BST в Min-Heap без використання масиву  


Рівень складності Жорсткий
Часто запитують у Амазонка Cisco Microsoft Лабораторії SAP
Бінарне дерево пошуку Бінарне дерево Дерево

Постановка проблеми  

Проблема «Перетворити BST у міні-купу без використання масиву» говорить про те, що вам надано BST (двійкове дерево пошуку), і вам потрібно перетворити його у міні-купу. Міні-куча повинна містити всі елементи у двійковому дереві пошуку. Алгоритм повинен працювати в лінійній часовій складності.

Приклад  

вхід

Перетворіть BST в Min-Heap без використання масивуPin

Вихід

Перетворіть BST в Min-Heap без використання масивуPin

Підхід до перетворення BST в Min-Heap без використання масиву  

Наївний підхід

Проблему "Перетворити BST у міні-купу без використання масиву" можна вирішити, якщо спочатку ми збережемо обхід в порядку двійкове дерево пошуку. І після пошуку обходу в порядку, ми починаємо створювати min-heap (повне бінарне дерево, у якому всі дочірні елементи в піддереві менші за батьківські). Отже, як ми створимо 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 (журнал N), тому що ми використовували чергу для зберігання дітей на одному рівні. Це вимагає складності логарифмічного простору. Але сам алгоритм працює на місці.