Já discutimos o Árvore binária encadeada binária .
A inserção na árvore binária encadeada é semelhante à inserção na árvore binária, mas teremos que ajustar os threads após a inserção de cada elemento.
Representação C do nó encadeado binário:
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; }; Na explicação a seguir consideramos Árvore de pesquisa binária (BST) para inserção como inserção é definida por algumas regras em BSTs.
Deixar tmp seja o nó recém-inserido . Pode haver três casos durante a inserção:
Caso 1: Inserção em árvore vazia
Os ponteiros esquerdo e direito de tmp serão definidos como NULL e o novo nó se tornará a raiz.
listas css
root = tmp; tmp -> left = NULL; tmp -> right = NULL;
Caso 2: Quando um novo nó é inserido como filho esquerdo
Depois de inserir o nó em seu devido lugar, temos que fazer com que seus threads esquerdo e direito apontem para o antecessor e o sucessor da ordem, respectivamente. O nó que foi sucessor em ordem . Portanto, os threads esquerdo e direito do novo nó serão-
10 de 100
tmp -> left = par ->left; tmp -> right = par;
Antes da inserção, o ponteiro esquerdo do pai era um thread, mas após a inserção será um link apontando para o novo nó.
par -> lthread = false; par -> left = temp;
O exemplo a seguir mostra um nó sendo inserido como filho esquerdo de seu pai.
Após inserção de 13
O antecessor de 14 se torna o antecessor de 13, então o fio esquerdo de 13 pontos para 10.
O sucessor de 13 é 14, então o fio direito de 13 aponta para o filho esquerdo, que é 13.
O ponteiro esquerdo de 14 não é um thread, agora aponta para o filho esquerdo, que é 13.
c# data e hora
Caso 3: Quando um novo nó é inserido como filho certo
O pai de tmp é seu antecessor inorder. O nó que era o sucessor em ordem do pai agora é o sucessor em ordem deste nó tmp. Portanto, os threads esquerdo e direito do novo nó serão-
tmp -> left = par; tmp -> right = par -> right;
Antes da inserção, o ponteiro direito do pai era um thread, mas após a inserção será um link apontando para o novo nó.
par -> rthread = false; par -> right = tmp;
O exemplo a seguir mostra um nó sendo inserido como filho direito de seu pai.
Depois dos 15 inseridos
exemplos de programas python
O sucessor de 14 se torna o sucessor de 15, então o fio direito de 15 pontos para 16
O antecessor de 15 é 14, então o fio esquerdo de 15 pontos para 14.
O ponteiro direito de 14 não é um thread agora, ele aponta para o filho certo, que é 15.
Implementação C++ para inserir um novo nó na árvore de pesquisa binária threaded:
Como inserto BST padrão procuramos o valor-chave na árvore. Se a chave já estiver presente, retornaremos, caso contrário, a nova chave será inserida no ponto onde a pesquisa termina. No BST, a pesquisa termina quando encontramos a chave ou quando alcançamos um ponteiro NULL para a esquerda ou para a direita. Aqui todos os ponteiros NULL esquerdo e direito são substituídos por threads, exceto o ponteiro esquerdo do primeiro nó e o ponteiro direito do último nó. Portanto, aqui a pesquisa não terá êxito quando alcançarmos um ponteiro NULL ou um thread.
site como coomeet
Implementação:
C++// 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>
Saída
5 10 13 14 16 17 20 30
Complexidade de tempo: O (log N)
Complexidade Espacial: O(1) já que nenhum espaço extra é usado.
Criar questionário