עץ בינארי מושחל | הַכנָסָה
כבר דנו ב עץ בינארי חוט בינארי .
הכנסה בעץ בינארי מושחל דומה להכנסה בעץ בינארי אך נצטרך להתאים את הפתילים לאחר הכנסת כל אלמנט.
ייצוג C של צומת עם הברגה בינארי:
struct Node { struct Node *left *right; int info; // false if left pointer points to predecessor // in Inorder Traversal boolean lthread; // false if right pointer points to successor // in Inorder Traversal boolean rthread; }; בהסבר הבא שקלנו עץ חיפוש בינארי (BST) עבור הכנסה כפי שהוספה מוגדרת על ידי כמה כללים ב-BSTs.
לְאַפשֵׁר tmp יהיה הצומת שהוכנס לאחרונה . יכולים להיות שלושה מקרים במהלך ההחדרה:
מקרה 1: הכנסה בעץ ריק
גם המצביעים השמאלי והימני של tmp יוגדרו ל-NULL והצומת החדש הופך לשורש.
root = tmp; tmp -> left = NULL; tmp -> right = NULL;
מקרה 2: כאשר צומת חדש הוכנס בתור הילד השמאלי
לאחר הכנסת הצומת במקומו המתאים, עלינו להפוך את החוטים השמאלי והימני שלו להצביע על קודמו ויורש הסדר בהתאמה. הצומת שהיה יורש לא-סדר . אז החוטים השמאלי והימני של הצומת החדש יהיו-
tmp -> left = par ->left; tmp -> right = par;
לפני ההכנסה המצביע השמאלי של האב היה שרשור אבל לאחר ההוספה זה יהיה קישור שמצביע לצומת החדש.
par -> lthread = false; par -> left = temp;
הדוגמה הבאה מציגה צומת המוכנס כילד שמאלי של ההורה שלו.
לאחר הכנסת 13
קודמו של 14 הופך לקודמו של 13 אז חוט שמאלי של 13 מצביע על 10.
היורש של 13 הוא 14 אז חוט ימני של 13 מצביע על ילד שמאלי שהוא 13.
מצביע שמאל של 14 אינו שרשור כעת הוא מצביע על ילד שמאלי שהוא 13.
מקרה 3: כאשר צומת חדש מוכנס כילד הנכון
האב של tmp הוא קודמו לא-סדר. הצומת שהיה יורש לא-סדר של האב הוא כעת היורש ב-in-order של הצומת tmp זה. אז החוטים השמאלי והימני של הצומת החדש יהיו-
tmp -> left = par; tmp -> right = par -> right;
לפני ההכנסה המצביע הימני של ההורה היה שרשור אבל לאחר ההוספה זה יהיה קישור המצביע לצומת החדש.
par -> rthread = false; par -> right = tmp;
הדוגמה הבאה מציגה צומת המוכנס כילד ימני של ההורה שלו.
לאחר 15 הוכנס
היורש של 14 הופך ליורש של 15 אז חוט נכון של 15 נקודות ל-16
קודמו של 15 הוא 14 אז חוט שמאלי של 15 נקודות ל-14.
מצביע ימין של 14 אינו שרשור כעת הוא מצביע על ילד נכון שהוא 15.
יישום C++ להוספת צומת חדש בעץ חיפוש בינארי משורשר:
כְּמוֹ תוספת BST סטנדרטית אנו מחפשים את ערך המפתח בעץ. אם המפתח כבר קיים אז נחזור אחרת המפתח החדש מוכנס בנקודה שבה מסתיים החיפוש. ב-BST החיפוש מסתיים או כאשר אנו מוצאים את המפתח או כאשר אנו מגיעים למצביע NULL שמאלה או ימינה. כאן כל מצביעי NULL שמאלה וימינה מוחלפים בשרשורים מלבד המצביע השמאלי של הצומת הראשון והמצביע הימני של הצומת האחרון. אז כאן החיפוש לא יצליח כשנגיע למצביע NULL או לשרשור.
יישום:
C++ // Insertion in Threaded Binary Search Tree. #include using namespace std ; struct Node { struct Node * left * right ; int info ; // False if left pointer points to predecessor // in Inorder Traversal bool lthread ; // False if right pointer points to successor // in Inorder Traversal bool rthread ; }; // Insert a Node in Binary Threaded Tree struct Node * insert ( struct Node * root int ikey ) { // Searching for a Node with given value Node * ptr = root ; Node * par = NULL ; // Parent of key to be inserted while ( ptr != NULL ) { // If key already exists return if ( ikey == ( ptr -> info )) { printf ( 'Duplicate Key ! n ' ); return root ; } par = ptr ; // Update parent pointer // Moving on left subtree. if ( ikey < ptr -> info ) { if ( ptr -> lthread == false ) ptr = ptr -> left ; else break ; } // Moving on right subtree. else { if ( ptr -> rthread == false ) ptr = ptr -> right ; else break ; } } // Create a new node Node * tmp = new Node ; tmp -> info = ikey ; tmp -> lthread = true ; tmp -> rthread = true ; if ( par == NULL ) { root = tmp ; tmp -> left = NULL ; tmp -> right = NULL ; } else if ( ikey < ( par -> info )) { tmp -> left = par -> left ; tmp -> right = par ; par -> lthread = false ; par -> left = tmp ; } else { tmp -> left = par ; tmp -> right = par -> right ; par -> rthread = false ; par -> right = tmp ; } return root ; } // Returns inorder successor using rthread struct Node * inorderSuccessor ( struct Node * ptr ) { // If rthread is set we can quickly find if ( ptr -> rthread == true ) return ptr -> right ; // Else return leftmost child of right subtree ptr = ptr -> right ; while ( ptr -> lthread == false ) ptr = ptr -> left ; return ptr ; } // Printing the threaded tree void inorder ( struct Node * root ) { if ( root == NULL ) printf ( 'Tree is empty' ); // Reach leftmost node struct Node * ptr = root ; while ( ptr -> lthread == false ) ptr = ptr -> left ; // One by one print successors while ( ptr != NULL ) { printf ( '%d ' ptr -> info ); ptr = inorderSuccessor ( ptr ); } } // Driver Program int main () { struct Node * root = NULL ; root = insert ( root 20 ); root = insert ( root 10 ); root = insert ( root 30 ); root = insert ( root 5 ); root = insert ( root 16 ); root = insert ( root 14 ); root = insert ( root 17 ); root = insert ( root 13 ); inorder ( root ); return 0 ; }
Java // Java program Insertion in Threaded Binary Search Tree. import java.util.* ; public class solution { static class Node { Node left right ; int info ; // False if left pointer points to predecessor // in Inorder Traversal boolean lthread ; // False if right pointer points to successor // in Inorder Traversal boolean rthread ; }; // Insert a Node in Binary Threaded Tree static Node insert ( Node root int ikey ) { // Searching for a Node with given value Node ptr = root ; Node par = null ; // Parent of key to be inserted while ( ptr != null ) { // If key already exists return if ( ikey == ( ptr . info )) { System . out . printf ( 'Duplicate Key !n' ); return root ; } par = ptr ; // Update parent pointer // Moving on left subtree. if ( ikey < ptr . info ) { if ( ptr . lthread == false ) ptr = ptr . left ; else break ; } // Moving on right subtree. else { if ( ptr . rthread == false ) ptr = ptr . right ; else break ; } } // Create a new node Node tmp = new Node (); tmp . info = ikey ; tmp . lthread = true ; tmp . rthread = true ; if ( par == null ) { root = tmp ; tmp . left = null ; tmp . right = null ; } else if ( ikey < ( par . info )) { tmp . left = par . left ; tmp . right = par ; par . lthread = false ; par . left = tmp ; } else { tmp . left = par ; tmp . right = par . right ; par . rthread = false ; par . right = tmp ; } return root ; } // Returns inorder successor using rthread static Node inorderSuccessor ( Node ptr ) { // If rthread is set we can quickly find if ( ptr . rthread == true ) return ptr . right ; // Else return leftmost child of right subtree ptr = ptr . right ; while ( ptr . lthread == false ) ptr = ptr . left ; return ptr ; } // Printing the threaded tree static void inorder ( Node root ) { if ( root == null ) System . out . printf ( 'Tree is empty' ); // Reach leftmost node Node ptr = root ; while ( ptr . lthread == false ) ptr = ptr . left ; // One by one print successors while ( ptr != null ) { System . out . printf ( '%d ' ptr . info ); ptr = inorderSuccessor ( ptr ); } } // Driver Program public static void main ( String [] args ) { Node root = null ; root = insert ( root 20 ); root = insert ( root 10 ); root = insert ( root 30 ); root = insert ( root 5 ); root = insert ( root 16 ); root = insert ( root 14 ); root = insert ( root 17 ); root = insert ( root 13 ); inorder ( root ); } } //contributed by Arnab Kundu // This code is updated By Susobhan Akhuli
Python3 # Insertion in Threaded Binary Search Tree. class newNode : def __init__ ( self key ): # False if left pointer points to # predecessor in Inorder Traversal self . info = key self . left = None self . right = None self . lthread = True # False if right pointer points to # successor in Inorder Traversal self . rthread = True # Insert a Node in Binary Threaded Tree def insert ( root ikey ): # Searching for a Node with given value ptr = root par = None # Parent of key to be inserted while ptr != None : # If key already exists return if ikey == ( ptr . info ): print ( 'Duplicate Key !' ) return root par = ptr # Update parent pointer # Moving on left subtree. if ikey < ptr . info : if ptr . lthread == False : ptr = ptr . left else : break # Moving on right subtree. else : if ptr . rthread == False : ptr = ptr . right else : break # Create a new node tmp = newNode ( ikey ) if par == None : root = tmp tmp . left = None tmp . right = None elif ikey < ( par . info ): tmp . left = par . left tmp . right = par par . lthread = False par . left = tmp else : tmp . left = par tmp . right = par . right par . rthread = False par . right = tmp return root # Returns inorder successor using rthread def inorderSuccessor ( ptr ): # If rthread is set we can quickly find if ptr . rthread == True : return ptr . right # Else return leftmost child of # right subtree ptr = ptr . right while ptr . lthread == False : ptr = ptr . left return ptr # Printing the threaded tree def inorder ( root ): if root == None : print ( 'Tree is empty' ) # Reach leftmost node ptr = root while ptr . lthread == False : ptr = ptr . left # One by one print successors while ptr != None : print ( ptr . info end = ' ' ) ptr = inorderSuccessor ( ptr ) # Driver Code if __name__ == '__main__' : root = None root = insert ( root 20 ) root = insert ( root 10 ) root = insert ( root 30 ) root = insert ( root 5 ) root = insert ( root 16 ) root = insert ( root 14 ) root = insert ( root 17 ) root = insert ( root 13 ) inorder ( root ) # This code is contributed by PranchalK
C# using System ; // C# program Insertion in Threaded Binary Search Tree. public class solution { public class Node { public Node left right ; public int info ; // False if left pointer points to predecessor // in Inorder Traversal public bool lthread ; // False if right pointer points to successor // in Inorder Traversal public bool rthread ; } // Insert a Node in Binary Threaded Tree public static Node insert ( Node root int ikey ) { // Searching for a Node with given value Node ptr = root ; Node par = null ; // Parent of key to be inserted while ( ptr != null ) { // If key already exists return if ( ikey == ( ptr . info )) { Console . Write ( 'Duplicate Key !n' ); return root ; } par = ptr ; // Update parent pointer // Moving on left subtree. if ( ikey < ptr . info ) { if ( ptr . lthread == false ) { ptr = ptr . left ; } else { break ; } } // Moving on right subtree. else { if ( ptr . rthread == false ) { ptr = ptr . right ; } else { break ; } } } // Create a new node Node tmp = new Node (); tmp . info = ikey ; tmp . lthread = true ; tmp . rthread = true ; if ( par == null ) { root = tmp ; tmp . left = null ; tmp . right = null ; } else if ( ikey < ( par . info )) { tmp . left = par . left ; tmp . right = par ; par . lthread = false ; par . left = tmp ; } else { tmp . left = par ; tmp . right = par . right ; par . rthread = false ; par . right = tmp ; } return root ; } // Returns inorder successor using rthread public static Node inorderSuccessor ( Node ptr ) { // If rthread is set we can quickly find if ( ptr . rthread == true ) { return ptr . right ; } // Else return leftmost child of right subtree ptr = ptr . right ; while ( ptr . lthread == false ) { ptr = ptr . left ; } return ptr ; } // Printing the threaded tree public static void inorder ( Node root ) { if ( root == null ) { Console . Write ( 'Tree is empty' ); } // Reach leftmost node Node ptr = root ; while ( ptr . lthread == false ) { ptr = ptr . left ; } // One by one print successors while ( ptr != null ) { Console . Write ( '{0:D} ' ptr . info ); ptr = inorderSuccessor ( ptr ); } } // Driver Program public static void Main ( string [] args ) { Node root = null ; root = insert ( root 20 ); root = insert ( root 10 ); root = insert ( root 30 ); root = insert ( root 5 ); root = insert ( root 16 ); root = insert ( root 14 ); root = insert ( root 17 ); root = insert ( root 13 ); inorder ( root ); } } // This code is contributed by Shrikant13
JavaScript < script > // javascript program Insertion in Threaded Binary Search Tree. class Node { constructor (){ this . left = null this . right = null ; this . info = 0 ; // False if left pointer points to predecessor // in Inorder Traversal this . lthread = false ; // False if right pointer points to successor // in Inorder Traversal this . rthread = false ; } } // Insert a Node in Binary Threaded Tree function insert ( root ikey ) { // Searching for a Node with given value var ptr = root ; var par = null ; // Parent of key to be inserted while ( ptr != null ) { // If key already exists return if ( ikey == ( ptr . info )) { document . write ( 'Duplicate Key !n' ); return root ; } par = ptr ; // Update parent pointer // Moving on left subtree. if ( ikey < ptr . info ) { if ( ptr . lthread == false ) ptr = ptr . left ; else break ; } // Moving on right subtree. else { if ( ptr . rthread == false ) ptr = ptr . right ; else break ; } } // Create a new node var tmp = new Node (); tmp . info = ikey ; tmp . lthread = true ; tmp . rthread = true ; if ( par == null ) { root = tmp ; tmp . left = null ; tmp . right = null ; } else if ( ikey < ( par . info )) { tmp . left = par . left ; tmp . right = par ; par . lthread = false ; par . left = tmp ; } else { tmp . left = par ; tmp . right = par . right ; par . rthread = false ; par . right = tmp ; } return root ; } // Returns inorder successor using rthread function inorderSuccessor ( ptr ) { // If rthread is set we can quickly find if ( ptr . rthread == true ) return ptr . right ; // Else return leftmost child of right subtree ptr = ptr . right ; while ( ptr . lthread == false ) ptr = ptr . left ; return ptr ; } // Printing the threaded tree function inorder ( root ) { if ( root == null ) document . write ( 'Tree is empty' ); // Reach leftmost node var ptr = root ; while ( ptr . lthread == false ) ptr = ptr . left ; // One by one print successors while ( ptr != null ) { document . write ( ptr . info + ' ' ); ptr = inorderSuccessor ( ptr ); } } // Driver Program var root = null ; root = insert ( root 20 ); root = insert ( root 10 ); root = insert ( root 30 ); root = insert ( root 5 ); root = insert ( root 16 ); root = insert ( root 14 ); root = insert ( root 17 ); root = insert ( root 13 ); inorder ( root ); // This code contributed by aashish1995 < /script>
תְפוּקָה
5 10 13 14 16 17 20 30
מורכבות זמן: O(לוג N)
מורכבות החלל: O(1) מכיוון שלא נעשה שימוש בשטח נוסף.
צור חידון
