Už sme diskutovali o Binárny závitový binárny strom .
Vkladanie do binárneho stromu je podobné ako vkladanie do binárneho stromu, ale po vložení každého prvku budeme musieť vlákna upraviť.
C reprezentácia binárneho závitového uzla:
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; }; V nasledujúcom vysvetlení sme zvážili Binárny vyhľadávací strom (BST) pre vkladanie, keďže vkladanie je definované niektorými pravidlami v BST.
Nechaj tmp je novo vložený uzol . Počas vkladania môžu nastať tri prípady:
Prípad 1: Vloženie do prázdneho stromu
Ľavý aj pravý ukazovateľ tmp budú nastavené na NULL a nový uzol sa stane koreňom.
bajtové pole na reťazec
root = tmp; tmp -> left = NULL; tmp -> right = NULL;
Prípad 2: Keď sa nový uzol vloží ako ľavé dieťa
Po vložení uzla na jeho správne miesto musíme urobiť jeho ľavé a pravé vlákno tak, aby ukazovalo na predchodcu a nasledovníka. Uzol, ktorý bol nástupca rádu . Takže ľavé a pravé vlákno nového uzla bude-
polymorfizmus v jave
tmp -> left = par ->left; tmp -> right = par;
Pred vložením bol ľavý ukazovateľ rodiča vlákno, ale po vložení to bude odkaz smerujúci na nový uzol.
par -> lthread = false; par -> left = temp;
Nasledujúci príklad ukazuje, že uzol je vložený ako ľavý potomok svojho rodiča.
Po vložení 13
Predchodca 14 sa stáva predchodcom 13, takže vľavo vlákno z 13 bodov na 10.
Následník 13 je 14, takže pravé vlákno 13 ukazuje ľavému dieťaťu, ktoré má 13.
Ľavý ukazovateľ 14 nie je vlákno, teraz ukazuje na ľavé dieťa, ktoré má 13 rokov.
Prípad 3: Keď je nový uzol vložený ako správny potomok
atoi c
Rodič tmp je jeho riadnym predchodcom. Uzol, ktorý bol následníkom rodiča v poradí, je teraz následníkom v poradí tohto uzla tmp. Takže ľavé a pravé vlákno nového uzla bude-
tmp -> left = par; tmp -> right = par -> right;
Pred vložením bol pravý ukazovateľ rodiča vlákno, ale po vložení to bude odkaz smerujúci na nový uzol.
par -> rthread = false; par -> right = tmp;
Nasledujúci príklad ukazuje, že uzol je vložený ako pravý potomok svojho rodiča.
otázky na pohovor v jazyku java
Po vložení 15
Následník 14 sa stáva nástupcom 15, takže pravá niť 15 bodov na 16
Predchodca 15 je 14, takže ľavé vlákno z 15 bodov na 14.
Pravý ukazovateľ 14 nie je vlákno, teraz ukazuje na pravé dieťa, ktoré má 15.
Implementácia C++ na vloženie nového uzla do stromu Threaded Binary Search Tree:
Ako štandardná vložka BST hľadáme hodnotu kľúča v strome. Ak je kľúč už prítomný, vrátime sa, inak sa nový kľúč vloží do bodu, kde vyhľadávanie skončí. V BST sa vyhľadávanie ukončí buď vtedy, keď nájdeme kľúč, alebo keď dosiahneme NULL ľavý alebo pravý ukazovateľ. Tu sú všetky ľavé a pravé NULL ukazovatele nahradené vláknami okrem ľavého ukazovateľa prvého uzla a pravého ukazovateľa posledného uzla. Takže tu bude vyhľadávanie neúspešné, keď dosiahneme NULL ukazovateľ alebo vlákno.
Implementácia:
vek rihannyC++
// Insertion in Threaded Binary Search Tree. #include
// 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
# 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.infoend=' ') 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
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
<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>
Výstup
5 10 13 14 16 17 20 30
Časová zložitosť: O (log N)
Priestorová zložitosť: O(1) pretože sa nepoužíva žiadny ďalší priestor.
Vytvoriť kvíz