Dado un árbol binario completo ordenado por niveles, la tarea es verificar si existe una clave en él o no. Un árbol binario completo tiene todos los niveles excepto posiblemente el último, completamente lleno, con todos los Nodes lo más a la izquierda posible.
Ejemplos:
7 / \ 10 15 / \ / \ 17 20 30 35 / \ / 40 41 50 Input: Node = 3 Output: No Input: Node = 7 Output: Yes Input: Node = 30 Output: Yes
Enfoque Una solución O(n) simple sería atravesar completamente el árbol y verificar el valor clave. Sin embargo, podemos aprovechar la información de que el árbol está ordenado y hacerlo mejor en términos de complejidad de tiempo.
- Averigüe el nivel donde puede existir la clave. Comience en el Node raíz, continúe hacia la izquierda hasta que se encuentre un valor mayor que el valor clave. El nivel anterior a este contendría la clave, si es que existiera en el árbol. Supongamos que este es el nivel l .
- Ahora, realice una búsqueda binaria en los Nodes de l . A diferencia de la búsqueda binaria convencional, no se puede acceder directamente a los Nodes de este nivel. Sin embargo, la ruta desde la raíz hasta cada Node en este nivel se puede codificar usando la lógica binaria. Por ejemplo, considere el tercer nivel en el árbol de muestra. Puede contener hasta 2 3 = 8 Nodes. Se puede llegar a estos Nodes desde el Node raíz yendo a la izquierda, a la izquierda, a la izquierda; o yendo a la izquierda, izquierda, derecha; y así. Si la izquierda se indica con 0 y la derecha con 1 , las posibles formas de llegar a los Nodes en este nivel se pueden codificar como arr = [000, 001, 010, 011, 100, 101, 110, 111].
- Sin embargo, no es necesario crear esta array, la búsqueda binaria se puede aplicar seleccionando recursivamente el índice central y simplemente generando el código gris de 1 bit de este índice (consulte este artículo ).
- En caso de rutas incompletas, simplemente verifique la parte izquierda de la array. Por ejemplo, la ruta codificada 011 no corresponde a ningún valor en el árbol de muestra. Dado que el árbol está completo, asegura que no habrá más elementos a la derecha.
- Si se encuentra la clave, devuelve verdadero, de lo contrario, devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; /* Class containing left and right child of current node and key value*/ class Node { public : int data; Node *left, *right; Node(int item) { data = item; left = right = NULL; } }; /* Function to locate which level to check for the existence of key. */ int findLevel(Node *root, int data) { // If the key is less than the root, // it will certainly not exist in the tree // because tree is level-order sorted if (data < root->data) return -1; // If the key is equal to the root then // simply return 0 (zero'th level) if (data == root->data) return 0; int cur_level = 0; while (true) { cur_level++; root = root->left; // If the key is found in any leftmost element // then simply return true // No need for any extra searching if (root->data == data) return -2; // If key lies between the root data and // the left child's data OR if key is greater // than root data and there is no level // underneath it, return the current level if (root->data < data && (root->left == NULL || root->left->data > data)) { break; } } return cur_level; } /* Function to traverse a binary encoded path and return the value encountered after traversal. */ int traversePath(Node *root,vector<int> path) { for (int i = 0; i < path.size(); i++) { int direction = path[i]; // Go left if (direction == 0) { // Incomplete path if (root->left == NULL) return -1; root = root->left; } // Go right else { // Incomplete path if (root->right == NULL) return -1; root = root->right; } } // Return the data at the node return root->data; } /* Function to generate gray code of corresponding binary number of integer i */ vector<int> generateGray(int n, int x) { // Create new arraylist to store // the gray code vector<int> gray ; int i = 0; while (x > 0) { gray.push_back(x % 2); x = x / 2; i++; } // Reverse the encoding till here reverse(gray.begin(),gray.end()); // Leftmost digits are filled with 0 for (int j = 0; j < n - i; j++) gray.insert(gray.begin(), 0); return gray; } /* Function to search the key in a particular level of the tree. */ bool binarySearch(Node *root, int start, int end, int data, int level) { if (end >= start) { // Find the middle index int mid = (start + end) / 2; // Encode path from root to this index // in the form of 0s and 1s where // 0 means LEFT and 1 means RIGHT vector<int> encoding = generateGray(level, mid); // Traverse the path in the tree // and check if the key is found int element_found = traversePath(root, encoding); // If path is incomplete if (element_found == -1) // Check the left part of the level return binarySearch(root, start, mid - 1, data, level); if (element_found == data) return true; // Check the right part of the level if (element_found < data) return binarySearch(root, mid + 1, end, data, level); // Check the left part of the level else return binarySearch(root, start, mid - 1, data, level); } // Key not found in that level return false; } // Function that returns true if the // key is found in the tree bool findKey(Node *root, int data) { // Find the level where the key may lie int level = findLevel(root, data); // If level is -1 then return false if (level == -1) return false; // If level is -2 i.e. key was found in any // leftmost element then simply return true if (level == -2) return true; // Apply binary search on the elements // of that level return binarySearch(root, 0, (int)pow(2, level) - 1, data, level); } // Driver code int main() { /* Consider the following level-order sorted tree 5 / \ 8 10 / \ / \ 13 23 25 30 / \ / 32 40 50 */ Node* root = new Node(5); root->left = new Node(8); root->right = new Node(10); root->left->left = new Node(13); root->left->right = new Node(23); root->right->left = new Node(25); root->right->right = new Node(30); root->left->left->left = new Node(32); root->left->left->right = new Node(40); root->left->right->left = new Node(50); // Keys to be searched int arr[] = { 5, 8, 9 }; int n = sizeof(arr)/sizeof(int); for (int i = 0; i < n; i++) { if (findKey(root, arr[i])) cout << ("Yes") << endl; else cout << ("No") << endl; } } // This code is contributed by Arnab Kundu
Java
// Java implementation of the approach import java.util.*; import java.io.*; /* Class containing left and right child of current node and key value*/ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } class GFG { /* Function to locate which level to check for the existence of key. */ public static int findLevel(Node root, int data) { // If the key is less than the root, // it will certainly not exist in the tree // because tree is level-order sorted if (data < root.data) return -1; // If the key is equal to the root then // simply return 0 (zero'th level) if (data == root.data) return 0; int cur_level = 0; while (true) { cur_level++; root = root.left; // If the key is found in any leftmost element // then simply return true // No need for any extra searching if (root.data == data) return -2; // If key lies between the root data and // the left child's data OR if key is greater // than root data and there is no level // underneath it, return the current level if (root.data < data && (root.left == null || root.left.data > data)) { break; } } return cur_level; } /* Function to traverse a binary encoded path and return the value encountered after traversal. */ public static int traversePath(Node root, ArrayList<Integer> path) { for (int i = 0; i < path.size(); i++) { int direction = path.get(i); // Go left if (direction == 0) { // Incomplete path if (root.left == null) return -1; root = root.left; } // Go right else { // Incomplete path if (root.right == null) return -1; root = root.right; } } // Return the data at the node return root.data; } /* Function to generate gray code of corresponding binary number of integer i */ static ArrayList<Integer> generateGray(int n, int x) { // Create new arraylist to store // the gray code ArrayList<Integer> gray = new ArrayList<Integer>(); int i = 0; while (x > 0) { gray.add(x % 2); x = x / 2; i++; } // Reverse the encoding till here Collections.reverse(gray); // Leftmost digits are filled with 0 for (int j = 0; j < n - i; j++) gray.add(0, 0); return gray; } /* Function to search the key in a particular level of the tree. */ public static boolean binarySearch(Node root, int start, int end, int data, int level) { if (end >= start) { // Find the middle index int mid = (start + end) / 2; // Encode path from root to this index // in the form of 0s and 1s where // 0 means LEFT and 1 means RIGHT ArrayList<Integer> encoding = generateGray(level, mid); // Traverse the path in the tree // and check if the key is found int element_found = traversePath(root, encoding); // If path is incomplete if (element_found == -1) // Check the left part of the level return binarySearch(root, start, mid - 1, data, level); if (element_found == data) return true; // Check the right part of the level if (element_found < data) return binarySearch(root, mid + 1, end, data, level); // Check the left part of the level else return binarySearch(root, start, mid - 1, data, level); } // Key not found in that level return false; } // Function that returns true if the // key is found in the tree public static boolean findKey(Node root, int data) { // Find the level where the key may lie int level = findLevel(root, data); // If level is -1 then return false if (level == -1) return false; // If level is -2 i.e. key was found in any // leftmost element then simply return true if (level == -2) return true; // Apply binary search on the elements // of that level return binarySearch(root, 0, (int)Math.pow(2, level) - 1, data, level); } // Driver code public static void main(String[] args) { /* Consider the following level-order sorted tree 5 / \ 8 10 / \ / \ 13 23 25 30 / \ / 32 40 50 */ Node root = new Node(5); root.left = new Node(8); root.right = new Node(10); root.left.left = new Node(13); root.left.right = new Node(23); root.right.left = new Node(25); root.right.right = new Node(30); root.left.left.left = new Node(32); root.left.left.right = new Node(40); root.left.right.left = new Node(50); // Keys to be searched int arr[] = { 5, 8, 9 }; int n = arr.length; for (int i = 0; i < n; i++) { if (findKey(root, arr[i])) System.out.println("Yes"); else System.out.println("No"); } } }
Python3
# Python3 implementation of the approach from sys import maxsize from collections import deque INT_MIN = -maxsize # Class containing left and right # child of current node and key value class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to locate which level to check # for the existence of key. def findLevel(root: Node, data: int) -> int: # If the key is less than the root, # it will certainly not exist in the tree # because tree is level-order sorted if (data < root.data): return -1 # If the key is equal to the root then # simply return 0 (zero'th level) if (data == root.data): return 0 cur_level = 0 while True: cur_level += 1 root = root.left # If the key is found in any leftmost # element then simply return true # No need for any extra searching if (root.data == data): return -2 # If key lies between the root data and # the left child's data OR if key is greater # than root data and there is no level # underneath it, return the current level if (root.data < data and (root.left == None or root.left.data > data)): break return cur_level # Function to traverse a binary # encoded path and return the value # encountered after traversal. def traversePath(root: Node, path: list) -> int: for i in range(len(path)): direction = path[i] # Go left if (direction == 0): # Incomplete path if (root.left == None): return -1 root = root.left # Go right else: # Incomplete path if (root.right == None): return -1 root = root.right # Return the data at the node return root.data # Function to generate gray code of # corresponding binary number of integer i def generateGray(n: int, x: int) -> list: # Create new arraylist to store # the gray code gray = [] i = 0 while (x > 0): gray.append(x % 2) x = x / 2 i += 1 # Reverse the encoding till here gray.reverse() # Leftmost digits are filled with 0 for j in range(n - i): gray.insert(0, gray[0]) return gray # Function to search the key in a # particular level of the tree. def binarySearch(root: Node, start: int, end: int, data: int, level: int) -> bool: if (end >= start): # Find the middle index mid = (start + end) / 2 # Encode path from root to this index # in the form of 0s and 1s where # 0 means LEFT and 1 means RIGHT encoding = generateGray(level, mid) # Traverse the path in the tree # and check if the key is found element_found = traversePath(root, encoding) # If path is incomplete if (element_found == -1): # Check the left part of the level return binarySearch(root, start, mid - 1, data, level) if (element_found == data): return True # Check the right part of the level if (element_found < data): return binarySearch(root, mid + 1, end, data, level) # Check the left part of the level else: return binarySearch(root, start, mid - 1, data, level) # Key not found in that level return False # Function that returns true if the # key is found in the tree def findKey(root: Node, data: int) -> bool: # Find the level where the key may lie level = findLevel(root, data) # If level is -1 then return false if (level == -1): return False # If level is -2 i.e. key was found in any # leftmost element then simply return true if (level == -2): return True # Apply binary search on the elements # of that level return binarySearch(root, 0, int(pow(2, level) - 1), data, level) # Driver code if __name__ == "__main__": # Consider the following level # order sorted tree ''' 5 / \ 8 10 / \ / \ 13 23 25 30 / \ / 32 40 50 ''' root = Node(5) root.left = Node(8) root.right = Node(10) root.left.left = Node(13) root.left.right = Node(23) root.right.left = Node(25) root.right.right = Node(30) root.left.left.left = Node(32) root.left.left.right = Node(40) root.left.right.left = Node(50) # Keys to be searched arr = [ 5, 8, 9 ] n = len(arr) for i in range(n): if (findKey(root, arr[i])): print("Yes") else: print("No") # This code is contributed by sanjeev2552
C#
// C# implementation of the approach using System; using System.Collections; using System.Collections.Generic; /* Class containing left and right child of current node and key value*/ class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; } } class GFG{ /* Function to locate which level to check for the existence of key. */ public static int findLevel(Node root, int data) { // If the key is less than the root, // it will certainly not exist in the tree // because tree is level-order sorted if (data < root.data) return -1; // If the key is equal to the root then // simply return 0 (zero'th level) if (data == root.data) return 0; int cur_level = 0; while (true) { cur_level++; root = root.left; // If the key is found in any leftmost element // then simply return true // No need for any extra searching if (root.data == data) return -2; // If key lies between the root data and // the left child's data OR if key is greater // than root data and there is no level // underneath it, return the current level if (root.data < data && (root.left == null || root.left.data > data)) { break; } } return cur_level; } /* Function to traverse a binary encoded path and return the value encountered after traversal. */ public static int traversePath(Node root, List<int> path) { for(int i = 0; i < path.Count; i++) { int direction = path[i]; // Go left if (direction == 0) { // Incomplete path if (root.left == null) return -1; root = root.left; } // Go right else { // Incomplete path if (root.right == null) return -1; root = root.right; } } // Return the data at the node return root.data; } /* Function to generate gray code of corresponding binary number of integer i */ static List<int> generateGray(int n, int x) { // Create new arraylist to store // the gray code List<int> gray = new List<int>(); int i = 0; while (x > 0) { gray.Add(x % 2); x = x / 2; i++; } // Reverse the encoding till here gray.Reverse(); // Leftmost digits are filled with 0 for(int j = 0; j < n - i; j++) gray.Insert(0, 0); return gray; } /* Function to search the key in a particular level of the tree. */ public static bool binarySearch(Node root, int start, int end, int data, int level) { if (end >= start) { // Find the middle index int mid = (start + end) / 2; // Encode path from root to this index // in the form of 0s and 1s where // 0 means LEFT and 1 means RIGHT List<int> encoding = generateGray(level, mid); // Traverse the path in the tree // and check if the key is found int element_found = traversePath(root, encoding); // If path is incomplete if (element_found == -1) // Check the left part of the level return binarySearch(root, start, mid - 1, data, level); if (element_found == data) return true; // Check the right part of the level if (element_found < data) return binarySearch(root, mid + 1, end, data, level); // Check the left part of the level else return binarySearch(root, start, mid - 1, data, level); } // Key not found in that level return false; } // Function that returns true if the // key is found in the tree public static bool findKey(Node root, int data) { // Find the level where the key may lie int level = findLevel(root, data); // If level is -1 then return false if (level == -1) return false; // If level is -2 i.e. key was found in any // leftmost element then simply return true if (level == -2) return true; // Apply binary search on the elements // of that level return binarySearch(root, 0, (int)Math.Pow(2, level) - 1, data, level); } // Driver code static void Main() { /* Consider the following level-order sorted tree 5 / \ 8 10 / \ / \ 13 23 25 30 / \ / 32 40 50 */ Node root = new Node(5); root.left = new Node(8); root.right = new Node(10); root.left.left = new Node(13); root.left.right = new Node(23); root.right.left = new Node(25); root.right.right = new Node(30); root.left.left.left = new Node(32); root.left.left.right = new Node(40); root.left.right.left = new Node(50); // Keys to be searched int []arr = { 5, 8, 9 }; int n = arr.Length; for(int i = 0; i < n; i++) { if (findKey(root, arr[i])) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } } // This code is contributed by SoumikMondal
Javascript
<script> // JavaScript implementation of the approach /* Class containing left and right child of current node and key value*/ class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } /* Function to locate which level to check for the existence of key. */ function findLevel(root, data) { // If the key is less than the root, // it will certainly not exist in the tree // because tree is level-order sorted if (data < root.data) return -1; // If the key is equal to the root then // simply return 0 (zero'th level) if (data == root.data) return 0; let cur_level = 0; while (true) { cur_level++; root = root.left; // If the key is found in any leftmost element // then simply return true // No need for any extra searching if (root.data == data) return -2; // If key lies between the root data and // the left child's data OR if key is greater // than root data and there is no level // underneath it, return the current level if (root.data < data && (root.left == null || root.left.data > data)) { break; } } return cur_level; } /* Function to traverse a binary encoded path and return the value encountered after traversal. */ function traversePath(root, path) { for (let i = 0; i < path.length; i++) { let direction = path[i]; // Go left if (direction == 0) { // Incomplete path if (root.left == null) return -1; root = root.left; } // Go right else { // Incomplete path if (root.right == null) return -1; root = root.right; } } // Return the data at the node return root.data; } /* Function to generate gray code of corresponding binary number of integer i */ function generateGray(n, x) { // Create new arraylist to store // the gray code let gray = []; let i = 0; while (x > 0) { gray.push(x % 2); x = parseInt(x / 2, 10); i++; } // Reverse the encoding till here gray.reverse(); // Leftmost digits are filled with 0 for (let j = 0; j < n - i; j++) gray.push(0, 0); return gray; } /* Function to search the key in a particular level of the tree. */ function binarySearch(root, start, end, data, level) { if (end >= start) { // Find the middle index let mid = parseInt((start + end) / 2, 10); // Encode path from root to this index // in the form of 0s and 1s where // 0 means LEFT and 1 means RIGHT let encoding = generateGray(level, mid); // Traverse the path in the tree // and check if the key is found let element_found = traversePath(root, encoding); // If path is incomplete if (element_found == -1) // Check the left part of the level return binarySearch(root, start, mid - 1, data, level); if (element_found == data) return true; // Check the right part of the level if (element_found < data) return binarySearch(root, mid + 1, end, data, level); // Check the left part of the level else return binarySearch(root, start, mid - 1, data, level); } // Key not found in that level return false; } // Function that returns true if the // key is found in the tree function findKey(root, data) { // Find the level where the key may lie let level = findLevel(root, data); // If level is -1 then return false if (level == -1) return false; // If level is -2 i.e. key was found in any // leftmost element then simply return true if (level == -2) return true; // Apply binary search on the elements // of that level return binarySearch(root, 0, Math.pow(2, level) - 1, data, level); } /* Consider the following level-order sorted tree 5 / \ 8 10 / \ / \ 13 23 25 30 / \ / 32 40 50 */ let root = new Node(5); root.left = new Node(8); root.right = new Node(10); root.left.left = new Node(13); root.left.right = new Node(23); root.right.left = new Node(25); root.right.right = new Node(30); root.left.left.left = new Node(32); root.left.left.right = new Node(40); root.left.right.left = new Node(50); // Keys to be searched let arr = [ 5, 8, 9 ]; let n = arr.length; for (let i = 0; i < n; i++) { if (findKey(root, arr[i])) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); } </script>
Yes Yes No
Complejidad del tiempo : el nivel se puede encontrar en el tiempo O (logn). El tiempo para recorrer cualquier camino para realizar una búsqueda binaria es O (logn). Además, en el peor de los casos, el nivel puede tener como máximo n/2 Nodes.
Por lo tanto, la complejidad temporal de realizar la búsqueda se convierte en O(logn)*O(log(n/2)) = O(logn)^2 .
Espacio Auxiliar : O(1).
Publicación traducida automáticamente
Artículo escrito por Anannya Uberoi 1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA