스레드 이진 트리 | 삽입
우리는 이미 다음 사항에 대해 논의했습니다. 이진 스레드 이진 트리 .
이진 스레드 트리에 삽입하는 것은 이진 트리에 삽입하는 것과 유사하지만 각 요소를 삽입한 후 스레드를 조정해야 합니다.
바이너리 스레드 노드의 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) 삽입은 BST의 일부 규칙에 의해 정의되므로 삽입용입니다.
허락하다 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의 부모는 그 중위 전임자입니다. 상위 노드의 하위 후속 노드였던 노드는 이제 이 노드 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(log N)
공간 복잡도: O(1) 추가 공간을 사용하지 않기 때문입니다.
퀴즈 만들기
