ក្លូនមែកធាងប្រព័ន្ធគោលពីរជាមួយព្រួញចៃដន្យ


កម្រិតលំបាក រឹង
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន Amazon ស៊ីស្កូ រោងចក្រ និយមជ្រុល ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft ល្ខោនអូប៉េរ៉ា Snapchat
ហាស់ មែកធាង

សេចក្តីថ្លែងការណ៍បញ្ហា។

អ្នកត្រូវបានផ្តល់ឱ្យពេញលេញ មែកធាងគោលពីរ ជាមួយអ្នកចង្អុលបង្ហាញចៃដន្យមួយចំនួន។ ចង្អុលចៃដន្យត្រូវបានគេសំដៅទៅលើថ្នាំងដែលរាល់ថ្នាំងចង្អុលទៅកូនផ្សេងទៀតនិងខាងឆ្វេង។ ដូច្នេះនេះក៏ផ្លាស់ប្តូររចនាសម្ព័ន្ធស្តង់ដារនៃថ្នាំងនៅក្នុងមែកធាងគោលពីរសាមញ្ញ។ ឥឡូវថ្នាំងនៃមែកធាងគោលពីរនឹងរក្សាទុកទិន្នន័យនៅថ្នាំងបច្ចុប្បន្ននិងទ្រនិចចង្អុលទៅខាងឆ្វេងស្តាំនិងព្រួញចង្អុលចៃដន្យ។ ដូច្នេះឥឡូវនេះយើងល្អក្នុងការទៅជាមួយអ្វីដែលសូម្បីតែបញ្ហាសួរ? បញ្ហា“ ក្លូនដើមឈើគោលពីរដែលមានចង្អុលចង្អុលចៃដន្យ” ស្នើឱ្យបង្កើតមែកធាងគោលពីរថ្មីដែលជាច្បាប់ចម្លងពិតប្រាកដនៃដើមដំបូងដែលបានផ្តល់ឱ្យ។ ដូច្នេះនៅក្នុងមែកធាងដែលបានបង្កើតថ្មីប្រសិនបើយើងយកថ្នាំងមួយរបស់វាខាងស្តាំនិងព្រួញចៃដន្យសំដៅទៅលើថ្នាំងនៅក្នុងមែកធាងថ្មីនេះដែលត្រូវនឹងថ្នាំងដែលមាននៅក្នុងមែកធាងដើម។

ឧទាហរណ៍

បញ្ចូល

ក្លូនមែកធាងប្រព័ន្ធគោលពីរជាមួយព្រួញចៃដន្យ

Inorder traversal of original binary tree is [current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

Inorder traversal of cloned binary tree is[current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

ការពន្យល់

ថ្នាំងខាងឆ្វេងនិងខាងស្តាំនៃមែកធាងគោលពីរត្រូវបានបង្ហាញជាធម្មតានៅខាងឆ្វេងនិងខាងស្តាំនៃថ្នាំងនីមួយៗ។ ហើយអ្នកចង្អុលបង្ហាញទាំងអស់ផ្សេងទៀតចង្អុលឆ្វេងនិងស្តាំគឺជាអ្នកចង្អុលបង្ហាញ។ គែមខ្លះមានព្រួញទ្វេ (ដែលចង្អុលក្នុងទិសដៅទាំងពីរ) ។ ទិសដៅទៅកាន់ឪពុកម្តាយណាមួយនៃថ្នាំងនេះមានន័យថាថ្នាំងមានទ្រនិចចៃដន្យទៅមេ។ លទ្ធផលត្រូវបានផ្តល់ជាទ្រង់ទ្រាយ [ទិន្នន័យថ្នាំងបច្ចុប្បន្ន / ទិន្នន័យថ្នាំងចៃដន្យ] ។

វិធីសាស្ត្រហួច

ដូច្នេះដូចយើងដឹងហើយថាយើងចាំបាច់ត្រូវបង្កើតដើមឈើថ្មីដែលជាច្បាប់ចម្លងពិតប្រាកដនៃដើមដំបូង។ យើងអាចដំណើរការការឆ្លងកាត់និងបង្កើតច្បាប់ចម្លង។ ប៉ុន្តែយើងនឹងប្រឈមមុខនឹងបញ្ហាជាមួយការចង្អុលចៃដន្យពីព្រោះថ្នាំងខ្លះអាចចង្អុលទៅថ្នាំងដែលមិនទាន់បានសាងសង់។ ដូច្នេះដើម្បីកម្ចាត់កំហុសនេះ។ ដំបូងយើងនឹងសាងសង់ដើមឈើថ្មី។ បន្ទាប់មកប្រើក ហាស់ម៉ាប់ ដែលរក្សាទុកអាសយដ្ឋានរបស់ថ្នាំងថ្មីដែលត្រូវគ្នានឹងថ្នាំងនីមួយៗក្នុងមែកធាងដើម។ ដូច្នេះជាថ្មីម្តងទៀតយើងដំណើរការការឆ្លុះបញ្ចាំងពីខាងក្នុងហើយធ្វើការចង្អុលបង្ហាញដោយចៃដន្យទៅថ្នាំងនៃមែកធាងថ្មី (ដែលត្រូវបានរក្សាទុកជាតម្លៃនៅក្នុងហាស់ម៉ាស) ។

វិធីសាស្ត្រមានប្រសិទ្ធភាព

នៅក្នុងវិធីសាស្រ្តខាងលើយើងត្រូវរក្សាទុកក ហាស់ម៉ាប់ ដែលរក្សាទុកអាស័យដ្ឋានក្លូនដែលត្រូវគ្នានឹងថ្នាំងនីមួយៗនៅក្នុងមែកធាងដើម។ ដូច្នេះជំនួសឱ្យការធ្វើដូច្នេះយើងនឹងធ្វើអ្វីមួយដែលបានធ្វើដើម្បីក្លូនក បញ្ជីដែលបានភ្ជាប់ ជាមួយនឹងចង្អុលចៃដន្យ។ យើងនឹងរុញថ្នាំងដែលបានបង្កើតថ្មីរវាងកូនខាងឆ្វេងនិងថ្នាំងដែលត្រូវគ្នានៅក្នុងដើមឈើដើម។ ដូច្នេះរហូតមកដល់ពេលនេះយើងបានផ្លាស់ប្តូររចនាសម្ព័ន្ធដើមឈើដំបូង។ ដើម្បីកំណត់ចង្អុលចៃដន្យយើងដឹងថាថ្នាំងថ្មីដែលត្រូវគ្នានឹងថ្នាំងគឺតែងតែជាកូនខាងឆ្វេងរបស់វា។ ដូច្នេះយើងគ្រាន់តែកំណត់ទ្រនិចចៃដន្យទៅកូនខាងឆ្វេងនៃថ្នាំងនៅក្នុងមែកធាងបញ្ចូល។ ប៉ុន្តែនៅតែយើងមានរឿងមួយដែលត្រូវយកចិត្តទុកដាក់។ យើងត្រូវស្តារកូនខាងឆ្វេងនៃថ្នាំងនៃដើមនិងក្លូន។ នៅពេលដែលបានធ្វើរួចយើងបានក្លូនដើមឈើគោលមួយដែលមានអ្នកសរសេរអក្សរចៃដន្យ។

លេខកូដ

កូដ C ++ ដើម្បីក្លូនដើមឈើគោលពីរជាមួយព្រួញចៃដន្យ

#include <iostream>
using namespace std;

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

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

// print inorder traversal of the given tree in [node, random node] format
void inorder(node* root)
{
  if(root == NULL)
    return;
  // print inorder traversal of left tree
  inorder(root->left);
  // print in [current node, random node] format
  cout << "[" << root->data << " ";
  if (root->random == NULL)
    cout << "NULL], ";
  else
    cout << root->random->data << "], ";
  // print inorder traversal of right tree
  inorder(root->right);
}

// insert clone nodes between the original node and its left child
node* insertCloneNode(node* originalNode)
{
  if (originalNode == NULL)
    return NULL;

  node* left = originalNode->left;
  originalNode->left = create(originalNode->data);
  originalNode->left->left = left;
  if(left != NULL)
    left->left = insertCloneNode(left);

  originalNode->left->right = insertCloneNode(originalNode->right);
  return originalNode->left;
}

// sets the random pointers in clone tree
void setRandomNode(node* originalNode, node* cloneNode)
{
  if (originalNode == NULL)
    return;
  if(originalNode->random != NULL)
    cloneNode->random = originalNode->random->left;
  else
    cloneNode->random = NULL;

  if(originalNode->left != NULL && cloneNode->left != NULL)
    setRandomNode(originalNode->left->left, cloneNode->left->left);
  setRandomNode(originalNode->right, cloneNode->right);
}

// after all the work restore the left pointers in original and clone tree
void restoreTreeLeftNode(node* originalNode, node* cloneNode)
{
  if (originalNode == NULL)
    return;
  if (cloneNode->left != NULL)
  {
    node* cloneLeft = cloneNode->left->left;
    originalNode->left = originalNode->left->left;
    cloneNode->left = cloneLeft;
  }
  else
    originalNode->left = NULL;

  restoreTreeLeftNode(originalNode->left, cloneNode->left);
  restoreTreeLeftNode(originalNode->right, cloneNode->right);
}

// constructs the new clone tree
node* cloneTree(node* originalNode)
{
  if (originalNode == NULL)
    return NULL;
  node* cloneNode = insertCloneNode(originalNode);
  setRandomNode(originalNode, cloneNode);
  restoreTreeLeftNode(originalNode, cloneNode);
  return cloneNode;
}


int main()
{
  node *root = create(3);
  node* two = create(2);
  node* one = create(1);
  node* seven = create(7);
  node* five = create(5);
  node* nine = create(9);

  root->left = two;
  root->left->left = one;
  root->right = seven;
  root->right->left = five;
  root->right ->right = nine;

  root->random = nine;
  root->left->random = seven;
  root->left->left->random = two;
  root->right->random = one;
  root->right->left->random = one;
  root->right->right->random = five;

  cout << "Inorder traversal of original binary tree is [current node data, random pointer data]: \n";
  inorder(root);

  node *clone = cloneTree(root);

  cout << "\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n";
  inorder(clone);

  return 0;
}
Inorder traversal of original binary tree is [current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

Inorder traversal of cloned binary tree is[current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

កូដចាវ៉ាដើម្បីក្លូនដើមប្រព័ន្ធគោលពីរជាមួយចៃដន្យចង្អុល

import java.util.*;
// Class that denotes a node of the tree
class node
{ 
    int data; 
    node left, right, random; 
 
    public node(int data) 
    { 
        this.data = data;
        left = right = random = null; 
    } 
}
 
class Tree 
{ 
    static node root;
  static node create(int data) {
    node tmp = new node(data);
    return tmp;
  }
  // print inorder traversal of the given tree in [node, random node] format
  static void inorder(node root){
    if(root != null){
      // print inorder traversal of left tree
      inorder(root.left);
      // print in [current node, random node] format
      System.out.print("[" + root.data + " ");
      if(root.random == null)
        System.out.print("null], ");
      else
        System.out.print(root.random.data +"], ");
      // print inorder traversal of right tree
      inorder(root.right);
    }
  }
 
  // insert clone nodes between the original node and its left child
  static node insertCloneNode(node originalNode) 
  { 
    if (originalNode == null) 
      return null; 
 
    node left = originalNode.left; 
    originalNode.left = create(originalNode.data); 
    originalNode.left.left = left; 
    if(left != null) 
      left.left = insertCloneNode(left); 
 
    originalNode.left.right = insertCloneNode(originalNode.right); 
    return originalNode.left; 
  } 
 
  // sets the random pointers in clone tree
  static void setRandomNode(node originalNode, node cloneNode) 
  { 
    if (originalNode != null){
      if(originalNode.random != null) 
        cloneNode.random = originalNode.random.left; 
      else
        cloneNode.random = null; 
 
      if(originalNode.left != null && cloneNode.left != null) 
        setRandomNode(originalNode.left.left, cloneNode.left.left); 
      setRandomNode(originalNode.right, cloneNode.right); 
    }
  } 
 
  // after all the work restore the left pointers in original and clone tree
  static void restoreTreeLeftNode(node originalNode, node cloneNode) 
  { 
    if (originalNode != null) {
      if (cloneNode.left != null) 
      { 
        node cloneLeft = cloneNode.left.left; 
        originalNode.left = originalNode.left.left; 
        cloneNode.left = cloneLeft; 
      } 
      else
        originalNode.left = null; 
 
      restoreTreeLeftNode(originalNode.left, cloneNode.left); 
      restoreTreeLeftNode(originalNode.right, cloneNode.right); 
    }
  } 
 
  // constructs the new clone tree
  static node cloneTree(node originalNode) 
  { 
    if (originalNode == null)
      return null;
    node cloneNode = insertCloneNode(originalNode); 
    setRandomNode(originalNode, cloneNode); 
    restoreTreeLeftNode(originalNode, cloneNode); 
    return cloneNode; 
  } 
 
  public static void main(String[] args) {
    node root = create(3);
    node two = create(2);
    node one = create(1);
    node seven = create(7);
    node five = create(5);
    node nine = create(9);
 
    root.left = two;
    root.left.left = one;
    root.right = seven;
    root.right.left = five;
    root.right .right = nine;
 
    root.random = nine;
    root.left.random = seven;
    root.left.left.random = two;
    root.right.random = one;
    root.right.left.random = one;
    root.right.right.random = five;
 
    System.out.print("Inorder traversal of original binary tree is[current node data, random pointer data]: \n");
    inorder(root);
 
    node clone = cloneTree(root);
 
    System.out.print("\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n");
    inorder(clone);
  }
}
Inorder traversal of original binary tree is[current node data, random pointer data]: 
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5], 

Inorder traversal of cloned binary tree is[current node data, random pointer data]: 
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

ការវិភាគស្មុគស្មាញដើម្បីក្លូនមែកធាងប្រព័ន្ធគោលពីរជាមួយព្រួញចៃដន្យ

ស្មុគស្មាញពេលវេលា 

O (N), យើងទើបតែឆ្លងកាត់ថ្នាំងនៅក្នុងមែកធាងគោលពីរហើយចាប់តាំងពីមានថ្នាំង N នៅក្នុងមែកធាងគោលពីរ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដូចដែលយើងមិនបានរក្សាទុកព័ត៌មានណាមួយនៅក្នុងអារេឬផែនទីទេ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។