Gjenget binært tre | Innsetting
Vi har allerede diskutert Binært gjenget binært tre .
Innsetting i binært gjenget tre ligner på innsetting i binært tre, men vi må justere trådene etter innsetting av hvert element.
C-representasjon av binær gjenget node:
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; }; I den følgende forklaringen har vi vurdert Binært søketre (BST) for innsetting ettersom innsetting er definert av noen regler i BST-er.
La tmp være den nylig innsatte noden . Det kan være tre tilfeller under innsetting:
Tilfelle 1: Innsetting i tomt tre
Både venstre og høyre pekere for tmp vil bli satt til NULL og ny node blir roten.
root = tmp; tmp -> left = NULL; tmp -> right = NULL;
Tilfelle 2: Når ny node ble satt inn som venstre barn
Etter å ha satt inn noden på riktig sted, må vi få dens venstre og høyre tråder til å peke på henholdsvis forgjenger og etterfølger. Noden som var etterfølger i rekkefølge . Så venstre og høyre tråder til den nye noden vil være-
tmp -> left = par ->left; tmp -> right = par;
Før innsetting var venstre peker til overordnet en tråd, men etter innsetting vil det være en lenke som peker til den nye noden.
par -> lthread = false; par -> left = temp;
Følgende eksempel viser en node som settes inn som venstre underordnede av sin overordnede.
Etter innsetting av 13
Forgjengeren til 14 blir forgjengeren til 13, så venstre tråd på 13 peker til 10.
Etterfølger av 13 er 14, så høyre tråd på 13 peker til venstre barn som er 13.
Venstre peker på 14 er ikke en tråd nå den peker til venstre barn som er 13.
Case 3: Når ny node settes inn som rett barn
Forelderen til tmp er dens inorder-forgjenger. Noden som var etterfølgeren til overordnet er nå etterfølgeren til denne noden tmp. Så venstre og høyre tråder til den nye noden vil være-
tmp -> left = par; tmp -> right = par -> right;
Før innsetting var høyre peker til overordnet en tråd, men etter innsetting vil det være en lenke som peker til den nye noden.
par -> rthread = false; par -> right = tmp;
Følgende eksempel viser en node som settes inn som høyre underordnet av sin overordnede.
Etter 15 satt inn
Etterfølger av 14 blir etterfølger av 15, så høyre tråd på 15 poeng til 16
Forgjengeren på 15 er 14, så venstre tråd på 15 poeng til 14.
Høyre peker på 14 er ikke en tråd nå den peker til høyre barn som er 15.
C++-implementering for å sette inn en ny node i Threaded Binary Search Tree:
Like standard BST innsats vi søker etter nøkkelverdien i treet. Hvis nøkkelen allerede er til stede, returnerer vi ellers settes den nye nøkkelen inn på punktet der søket avsluttes. I BST avsluttes søket enten når vi finner nøkkelen eller når vi når en NULL venstre eller høyre peker. Her er alle venstre og høyre NULL-pekere erstattet av tråder bortsett fra venstre peker for første node og høyre peker for siste node. Så her vil søket mislykkes når vi når en NULL-peker eller en tråd.
Implementering:
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>
Produksjon
5 10 13 14 16 17 20 30
Tidskompleksitet: O(log N)
Romkompleksitet: O(1) siden ingen ekstra plass brukes.
Lag quiz
