ಯಾದೃಚ್ Poin ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಬೈನರಿ ಮರವನ್ನು ಕ್ಲೋನ್ ಮಾಡಿ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಅಮೆಜಾನ್ ಸಿಸ್ಕೋ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಫ್ಯಾನಟಿಕ್ಗಳು ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒಪೆರಾ Snapchat
ಹ್ಯಾಶ್ ಮರ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ನಿಮಗೆ ಸಂಪೂರ್ಣ ನೀಡಲಾಗಿದೆ ಬೈನರಿ ಮರ ಕೆಲವು ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ. ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ನೋಡ್‌ಗಳಿಗೆ ಉಲ್ಲೇಖಿಸಲಾಗುತ್ತದೆ, ಅದು ಪ್ರತಿ ನೋಡ್ ಅದರ ಎಡ ಮತ್ತು ಬಲ ಮಗುವನ್ನು ಹೊರತುಪಡಿಸಿ ಸೂಚಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಇದು ಸರಳ ಬೈನರಿ ಮರದಲ್ಲಿ ನೋಡ್ನ ಪ್ರಮಾಣಿತ ರಚನೆಯನ್ನು ಸಹ ಬದಲಾಯಿಸುತ್ತದೆ. ಈಗ ಬೈನರಿ ಮರದ ನೋಡ್ ಡೇಟಾವನ್ನು ಪ್ರಸ್ತುತ ನೋಡ್‌ನಲ್ಲಿ ಮತ್ತು ಪಾಯಿಂಟರ್‌ನಿಂದ ಎಡ, ಬಲ ಮತ್ತು ಯಾದೃಚ್ ಪಾಯಿಂಟರ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಈಗ ನಾವು ಹೋಗುವುದು ಒಳ್ಳೆಯದು, ಸಮಸ್ಯೆ ಏನು ಕೇಳುತ್ತದೆ? "ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಹೊಂದಿರುವ ಬೈನರಿ ಮರವನ್ನು ಕ್ಲೋನ್ ಮಾಡಿ" ಎಂಬ ಸಮಸ್ಯೆ ಹೊಸ ಬೈನರಿ ಮರವನ್ನು ರಚಿಸಲು ಕೇಳುತ್ತದೆ, ಅದು ಕೊಟ್ಟಿರುವ ಆರಂಭಿಕ ಮರದ ನಿಖರವಾದ ಪ್ರತಿ. ಆದ್ದರಿಂದ ಹೊಸದಾಗಿ ರಚಿಸಲಾದ ಮರದಲ್ಲಿ, ನಾವು ನೋಡ್ ಅನ್ನು ಆರಿಸಿದರೆ ಅದರ ಎಡ, ಬಲ ಮತ್ತು ಯಾದೃಚ್ point ಿಕ ಪಾಯಿಂಟರ್ ಈ ಹೊಸ ಮರದ ನೋಡ್‌ಗಳನ್ನು ಮೂಲ ಮರದ ನೋಡ್‌ಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್

ಯಾದೃಚ್ Poin ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಬೈನರಿ ಮರವನ್ನು ಕ್ಲೋನ್ ಮಾಡಿ

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],

ವಿವರಣೆ

ಬೈನರಿ ಮರದ ಎಡ ಮತ್ತು ಬಲ ನೋಡ್‌ಗಳನ್ನು ಪ್ರತಿ ನೋಡ್‌ನ ಎಡ ಮತ್ತು ಬಲದಲ್ಲಿ ಎಂದಿನಂತೆ ತೋರಿಸಲಾಗುತ್ತದೆ. ಮತ್ತು ಎಲ್ಲಾ ಪಾಯಿಂಟರ್‌ಗಳು ಇತರರು ಎಡ ಮತ್ತು ಬಲ ಪಾಯಿಂಟರ್‌ಗಳು ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳಾಗಿವೆ. ಕೆಲವು ಅಂಚುಗಳು ಎರಡು ಬಾಣಗಳನ್ನು ಹೊಂದಿವೆ (ಅದು ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಸೂಚಿಸುತ್ತದೆ). ನೋಡ್ನ ಯಾವುದೇ ಪೋಷಕರ ನಿರ್ದೇಶನವು ನೋಡ್ಗೆ ಪೋಷಕರಿಗೆ ಯಾದೃಚ್ ಪಾಯಿಂಟರ್ ಹೊಂದಿದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. Current ಟ್ಪುಟ್ ಅನ್ನು [ಪ್ರಸ್ತುತ ನೋಡ್ ಡೇಟಾ / ಯಾದೃಚ್ node ಿಕ ನೋಡ್ ಡೇಟಾ] ಸ್ವರೂಪದಲ್ಲಿ ನೀಡಲಾಗಿದೆ.

ಹ್ಯಾಶಿಂಗ್ ಅಪ್ರೋಚ್

ಆದ್ದರಿಂದ, ನಾವು ಹೊಸ ಮರವನ್ನು ರಚಿಸಬೇಕಾಗಿದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿರುವಂತೆ ಅದು ಆರಂಭಿಕ ಮರದ ನಿಖರವಾದ ಪ್ರತಿ ಆಗಿದೆ. ನಾವು ಇನಾಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಚಲಾಯಿಸಬಹುದು ಮತ್ತು ನಕಲನ್ನು ನಿರ್ಮಿಸಬಹುದು. ಆದರೆ ನಾವು ಯಾದೃಚ್ om ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಸಮಸ್ಯೆಗಳನ್ನು ಎದುರಿಸುತ್ತೇವೆ ಏಕೆಂದರೆ ಕೆಲವು ನೋಡ್‌ಗಳು ಇನ್ನೂ ನಿರ್ಮಿಸದ ನೋಡ್‌ಗಳಿಗೆ ಸೂಚಿಸುತ್ತಿರಬಹುದು. ಆದ್ದರಿಂದ ಈ ದೋಷವನ್ನು ತೊಡೆದುಹಾಕಲು. ನಾವು ಮೊದಲು ಹೊಸ ಮರವನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ. ನಂತರ a ಬಳಸಿ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಇದು ಮೂಲ ಮರದ ಪ್ರತಿಯೊಂದು ನೋಡ್‌ಗೆ ಅನುಗುಣವಾದ ಹೊಸ ನೋಡ್‌ನ ವಿಳಾಸವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ಮತ್ತೊಮ್ಮೆ ನಾವು ಇನಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಚಲಾಯಿಸುತ್ತೇವೆ ಮತ್ತು ಹೊಸ ಮರದ ನೋಡ್‌ಗಳಿಗೆ ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಮಾಡುತ್ತೇವೆ (ಇವುಗಳನ್ನು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಮೌಲ್ಯಗಳಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ).

ಸಮರ್ಥ ವಿಧಾನ

ಮೇಲಿನ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಎ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಇದು ಮೂಲ ಮರದಲ್ಲಿನ ಪ್ರತಿ ನೋಡ್‌ಗೆ ಅನುಗುಣವಾದ ಕ್ಲೋನ್ ನೋಡ್ ವಿಳಾಸವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ಅದನ್ನು ಮಾಡುವ ಬದಲು, ಕ್ಲೋನ್ ಮಾಡಲು ನಾವು ಏನನ್ನಾದರೂ ಮಾಡುತ್ತೇವೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿ ಯಾದೃಚ್ om ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ. ಹೊಸ ಮರವನ್ನು ಎಡ ಮಗು ಮತ್ತು ಅನುಗುಣವಾದ ನೋಡ್ ನಡುವೆ ಮೂಲ ಮರದಲ್ಲಿ ತಳ್ಳುತ್ತೇವೆ. ಆದ್ದರಿಂದ ಇಲ್ಲಿಯವರೆಗೆ, ನಾವು ಆರಂಭಿಕ ಮರದ ರಚನೆಯನ್ನು ಬದಲಾಯಿಸಿದ್ದೇವೆ. ಯಾದೃಚ್ points ಿಕ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಹೊಂದಿಸಲು ನೋಡ್‌ಗೆ ಅನುಗುಣವಾದ ಹೊಸ ನೋಡ್ ಯಾವಾಗಲೂ ಅದರ ಎಡ ಮಗು ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಹೀಗೆ ನಾವು ಇನ್ಪುಟ್ ಟ್ರೀನಲ್ಲಿ ಯಾದೃಚ್ point ಿಕ ಪಾಯಿಂಟರ್ ಅನ್ನು ನೋಡ್ನ ಎಡ ಮಗುವಿಗೆ ಹೊಂದಿಸುತ್ತೇವೆ. ಆದರೆ ಇನ್ನೂ ನಾವು ಕಾಳಜಿ ವಹಿಸಲು ಒಂದು ವಿಷಯವಿದೆ. ಆರಂಭಿಕ ಮತ್ತು ತದ್ರೂಪಿ ಮರದ ನೋಡ್‌ಗಳ ಎಡ ಮಗುವನ್ನು ನಾವು ಮರುಸ್ಥಾಪಿಸಬೇಕಾಗಿದೆ. ಅದು ಮುಗಿದ ನಂತರ ನಾವು ಬೈನರಿ ಮರವನ್ನು ಯಾದೃಚ್ po ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಅಬೀಜ ಸಂತಾನೋತ್ಪತ್ತಿ ಮಾಡಿದ್ದೇವೆ.

ಕೋಡ್

ರಾಂಡಮ್ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಬೈನರಿ ಟ್ರೀ ಅನ್ನು ಕ್ಲೋನ್ ಮಾಡಲು ಸಿ ++ ಕೋಡ್

#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],

ಯಾದೃಚ್ Poin ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಬೈನರಿ ಟ್ರೀ ಅನ್ನು ಕ್ಲೋನ್ ಮಾಡಲು ಜಾವಾ ಕೋಡ್

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],

ಯಾದೃಚ್ Poin ಿಕ ಪಾಯಿಂಟರ್‌ಗಳೊಂದಿಗೆ ಬೈನರಿ ಮರವನ್ನು ಕ್ಲೋನ್ ಮಾಡಲು ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್), ನಾವು ಬೈನರಿ ಮರದಲ್ಲಿ ನೋಡ್‌ಗಳನ್ನು ದಾಟಿದ್ದೇವೆ ಮತ್ತು ಬೈನರಿ ಮರದಲ್ಲಿ ಎನ್ ನೋಡ್‌ಗಳು ಇರುವುದರಿಂದ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಯಾವುದೇ ಮಾಹಿತಿಯನ್ನು ರಚನೆ ಅಥವಾ ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿಲ್ಲ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.