Dado un árbol binario completo con valores indexados de 1 a N y una clave K . La tarea es comprobar si existe una clave en el árbol o no. Escriba «verdadero» si la clave existe, de lo contrario, escriba «falso».
Árbol Binario Completo: Un Árbol Binario es un Árbol Binario completo si todos los niveles están completamente llenos excepto posiblemente el último nivel y el último nivel tiene todas las claves tan a la izquierda como sea posible
Ejemplos:
Entrada: K = 2
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10Salida: verdadero
Entrada: K = 11
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10Salida: falso
Enfoque ingenuo: el enfoque más simple sería simplemente recorrer todo el árbol y verificar si la clave existe en el árbol o no.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque se basa en la idea de que el árbol es un árbol binario completo y los Nodes están indexados de 1 a N comenzando desde arriba. Entonces podemos rastrear la ruta que va desde la raíz hasta la clave, si es que existió la clave. A continuación se muestran los pasos:
- Para un árbol binario completo dado el Node i , sus hijos serán 2*i y 2*i + 1 . Por lo tanto, dado el Node i , su Node padre será i/2 .
- Encuentre iterativamente el padre de la clave hasta que se encuentre el Node raíz del árbol, y almacene los pasos en una array pasos[] como -1 para la izquierda y 1 para la derecha (Izquierda significa que el Node actual es el hijo izquierdo de su padre y derecho significa que el Node actual es el hijo derecho de su padre).
- Ahora atraviesa el árbol de acuerdo con los movimientos almacenados en la array steps[] . Si toda la array se cruza con éxito, significa que la clave existe en el árbol, así que imprima «Verdadero», de lo contrario imprima «Falso».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above 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;
Node* right;
Node(int item)
{
data = item;
left = NULL;
right = NULL;
}
};
// Function to store the
// list of the directions
vector<int> findSteps(Node* root, int data)
{
vector<int> steps;
// While the root is not found
while (data != 1) {
// If it is the right
// child of its parent
if (data / 2.0 > data / 2) {
// Add right step (1)
steps.push_back(1);
}
else {
// Add left step (-1)
steps.push_back(-1);
}
int parent = data / 2;
// Repeat the same
// for its parent
data = parent;
}
// Reverse the steps list
reverse(steps.begin(), steps.end());
// Return the steps
return steps;
}
// Function to find
// if the key is present or not
bool findKey(Node* root, int data)
{
// Get the steps to be followed
vector<int> steps = findSteps(root, data);
// Taking one step at a time
for (auto cur_step : steps)
{
// Go left
if (cur_step == -1) {
// If left child does
// not exist return false
if (root->left == NULL)
return false;
root = root->left;
}
// Go right
else {
// If right child does
// not exist return false
if (root->right == NULL)
return false;
root = root->right;
}
}
// If the entire array of steps
// has been successfully
// traversed
return true;
}
int main()
{
/* Consider the following complete binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
*/
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
root->left->right->left = new Node(10);
// Function Call
cout<<boolalpha<<findKey(root, 7)<<endl;
}
// This code is contributed by Pushpesh Raj.
Java
// Java program for the above 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 = null;
right = null;
}
}
class Solution {
// Function to store the
// list of the directions
public static ArrayList<Integer>
findSteps(Node root, int data)
{
ArrayList<Integer> steps
= new ArrayList<Integer>();
// While the root is not found
while (data != 1) {
// If it is the right
// child of its parent
if (data / 2.0 > data / 2) {
// Add right step (1)
steps.add(1);
}
else {
// Add left step (-1)
steps.add(-1);
}
int parent = data / 2;
// Repeat the same
// for its parent
data = parent;
}
// Reverse the steps list
Collections.reverse(steps);
// Return the steps
return steps;
}
// Function to find
// if the key is present or not
public static boolean
findKey(Node root, int data)
{
// Get the steps to be followed
ArrayList<Integer> steps
= findSteps(root, data);
// Taking one step at a time
for (Integer cur_step : steps) {
// Go left
if (cur_step == -1) {
// If left child does
// not exist return false
if (root.left == null)
return false;
root = root.left;
}
// Go right
else {
// If right child does
// not exist return false
if (root.right == null)
return false;
root = root.right;
}
}
// If the entire array of steps
// has been successfully
// traversed
return true;
}
public static void main(String[] args)
{
/* Consider the following complete binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
// Function Call
System.out.println(findKey(root, 7));
}
}
Python3
# Python program to implement above approach # Class containing left # and right child of current node # and key value class Node: def __init__(self,item): self.data = item self.left = None self.right = None # Function to store the # list of the directions def findSteps(root,data): steps = [] # While the root is not found while (data != 1): # If it is the right # child of its parent if (data / 2 > data // 2): # Add right step (1) steps.append(1) else: # Add left step (-1) steps.append(-1) parent = data // 2 # Repeat the same # for its parent data = parent # Reverse the steps list steps = steps[::-1] # Return the steps return steps # Function to find # if the key is present or not def findKey(root,data): # Get the steps to be followed steps = findSteps(root, data) # Taking one step at a time for cur_step in steps: # Go left if (cur_step == -1): # If left child does # not exist return False if (root.left == None): return False root = root.left # Go right else: # If right child does # not exist return False if (root.right == None): return False root = root.right # If the entire array of steps # has been successfully # traversed return True # driver code # Consider the following complete binary tree # 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # / \ / # 8 9 10 # root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) # Function Call print(findKey(root, 7)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
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 Solution {
// Function to store the
// list of the directions
public static List<int>
findSteps(Node root, int data)
{
List<int> steps
= new List<int>();
// While the root is not found
while (data != 1) {
// If it is the right
// child of its parent
if (data / 2.0 > data / 2) {
// Add right step (1)
steps.Add(1);
}
else {
// Add left step (-1)
steps.Add(-1);
}
int parent = data / 2;
// Repeat the same
// for its parent
data = parent;
}
// Reverse the steps list
steps.Reverse();
// Return the steps
return steps;
}
// Function to find
// if the key is present or not
public static bool
findKey(Node root, int data)
{
// Get the steps to be followed
List<int> steps
= findSteps(root, data);
// Taking one step at a time
foreach (int cur_step in steps) {
// Go left
if (cur_step == -1) {
// If left child does
// not exist return false
if (root.left == null)
return false;
root = root.left;
}
// Go right
else {
// If right child does
// not exist return false
if (root.right == null)
return false;
root = root.right;
}
}
// If the entire array of steps
// has been successfully
// traversed
return true;
}
public static void Main()
{
/* Consider the following complete binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
// Function Call
Console.Write(findKey(root, 7));
}
}
Javascript
<script>
// JavaScript program to implement above approach
// Class containing left
// and right child of current node
// and key value
class Node {
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
// Function to store the
// list of the directions
function findSteps(root,data)
{
let steps = [];
// While the root is not found
while (data != 1)
{
// If it is the right
// child of its parent
if (data / 2 > Math.floor(data / 2)) {
// Add right step (1)
steps.push(1);
}
else {
// Add left step (-1)
steps.push(-1);
}
let parent = Math.floor(data / 2);
// Repeat the same
// for its parent
data = parent;
}
// Reverse the steps list
steps.reverse();
// Return the steps
return steps;
}
// Function to find
// if the key is present or not
function findKey(root,data)
{
// Get the steps to be followed
let steps = findSteps(root, data);
// Taking one step at a time
for (let cur_step of steps) {
// Go left
if (cur_step == -1) {
// If left child does
// not exist return false
if (root.left == null)
return false;
root = root.left;
}
// Go right
else {
// If right child does
// not exist return false
if (root.right == null)
return false;
root = root.right;
}
}
// If the entire array of steps
// has been successfully
// traversed
return true;
}
// driver code
/* Consider the following complete binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
*/
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
// Function Call
document.write(findKey(root, 7),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
true
Complejidad temporal: O(logN)
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