שיבוט עץ בינארי עם מצביעים אקראיים


רמת קושי קשה
נשאל לעתים קרובות נאמן אמזון בעברית סיסקו סט עובדות קנאות Google מיקרוסופט לפעול 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],

הסבר

הצמתים השמאליים והימניים של העץ הבינארי מוצגים כרגיל בצד שמאל וימין של כל צומת. וכל המצביעים אחרים המצביעים שמאלה וימינה הם מצביעים אקראיים. בחלק מהקצוות יש חצים כפולים (זה מצביע לשני הכיוונים). הכיוון לכל אחד מהורי הצומת מציין כי לצומת יש מצביע אקראי להורה. הפלט ניתן בתבנית [נתוני צומת נוכחי / נתוני צומת אקראיים].

גישת Hashing

אז כידוע עלינו ליצור עץ חדש שהוא העתק מדויק של העץ הראשוני. אנחנו יכולים להעביר חציית הזמנה ולבנות עותק. אך אנו נתקל בבעיות עם מצביעים אקראיים מכיוון שחלק מהצמתים עשויים להצביע על צמתים שעדיין לא בנויים. אז כדי להיפטר מהשגיאה הזו. ראשית נבנה עץ חדש. ואז השתמש ב- מפת גיבוב המאחסן את כתובת הצומת החדש המתאים לכל צומת בעץ המקורי. אז שוב אנו מפעילים מעבר מסדר ועושים את המצביעים האקראיים לצמתים של העץ החדש (המאוחסנים כערכים ב- HashMap).

גישה יעילה

בגישה לעיל היינו צריכים לשמור על מפת גיבוב ששמרה כתובת צומת שיבוט המתאימה לכל צומת בעץ המקורי. אז במקום לעשות זאת, אנו נעשה משהו כפי שנעשה כדי לשכפל א רשימה מקושרת עם מצביעים אקראיים. נדחוף את הצמתים שזה עתה נוצרו בין הילד השמאלי לצומת המתאים בעץ המקורי. אז עד עכשיו שינינו את מבנה העץ הראשוני. כדי להגדיר מצביעים אקראיים אנו יודעים שצומת חדש המתאים לצומת הוא תמיד הילד השמאלי שלו. לפיכך אנו פשוט מגדירים את המצביע האקראי לילד השמאלי של הצומת בעץ הקלט. אבל עדיין יש לנו דבר אחד לדאוג לו. עלינו לשחזר את הילד השמאלי של הצמתים של העץ הראשוני והמשובט. לאחר סיום שיבטנו עץ בינארי עם מצביעים אקראיים.

קופונים

קוד 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],

קוד Java לשיבוט עץ בינארי עם מצביעים אקראיים

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 בעץ הבינארי. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (1), מכיוון שלא שמרנו שום מידע במערך או במפה. כך מורכבות החלל קבועה.