Dado un recorrido de preorden de un BST. La tarea es encontrar el número de elementos menor que la raíz.
Ejemplos:
Input: preorder[] = {3, 2, 1, 0, 5, 4, 6}
Output: 3
Input: preorder[] = {5, 4, 3, 2, 1}
Output: 4
Para un árbol de búsqueda binaria, un recorrido de preorden tiene la forma:
raíz, {elementos en el subárbol izquierdo de la raíz}, {elementos en el subárbol derecho de la raíz}
Enfoque sencillo:
- Atraviesa el preorden dado.
- Compruebe si el elemento actual es mayor que la raíz.
- En caso afirmativo, devuelva indexOfCurrentElement – 1 como el no. los elementos más pequeños que la raíz serán todos los elementos que ocurren antes del elemento actual, excepto la raíz.
C++
// C++ implementation of above approach
#include <iostream>
using namespace std;
// Function to find the first index of the element
// that is greater than the root
int findLargestIndex(int arr[], int n)
{
int i, root = arr[0];
// Traverse the given preorder
for(i = 0; i < n-1; i++)
{
// Check if the number is greater than root
// If yes then return that index-1
if(arr[i] > root)
return i-1;
}
}
// Driver Code
int main()
{
int preorder[] = {3, 2, 1, 0, 5, 4, 6};
int n = sizeof(preorder) / sizeof(preorder[0]);
cout << findLargestIndex(preorder, n);
return 0;
}
Java
// Java implementation of
// above approach
class GFG
{
// Function to find the first
// index of the element that
// is greater than the root
static int findLargestIndex(int arr[],
int n)
{
int i, root = arr[0];
// Traverse the given preorder
for(i = 0; i < n - 1; i++)
{
// Check if the number is
// greater than root
// If yes then return
// that index-1
if(arr[i] > root)
return i-1;
}
return 0;
}
// Driver Code
public static void main(String ags[])
{
int preorder[] = {3, 2, 1, 0, 5, 4, 6};
int n = preorder.length;
System.out.println(findLargestIndex(preorder, n));
}
}
// This code is contributed
// by Subhadeep Gupta
Python3
# Python3 implementation of above approach # Function to find the first index of # the element that is greater than the root def findLargestIndex(arr, n): i, root = arr[0], arr[0]; # Traverse the given preorder for i in range(0, n - 1): # Check if the number is greater than # root. If yes then return that index-1 if(arr[i] > root): return i - 1; # Driver Code preorder= [3, 2, 1, 0, 5, 4, 6]; n = len(preorder) print(findLargestIndex(preorder, n)); # This code is contributed # by Akanksha Rai
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the first
// index of the element that
// is greater than the root
static int findLargestIndex(int []arr,
int n)
{
int i, root = arr[0];
// Traverse the given preorder
for(i = 0; i < n - 1; i++)
{
// Check if the number is
// greater than root. If yes
// then return that index-1
if(arr[i] > root)
return i - 1;
}
return 0;
}
// Driver Code
static public void Main()
{
int []preorder = {3, 2, 1, 0, 5, 4, 6};
int n = preorder.Length;
Console.WriteLine(findLargestIndex(preorder, n));
}
}
// This code is contributed
// by Subhadeep Gupta
PHP
<?php
// PHP implementation of above approach
// Function to find the first index of
// the element that is greater than the root
function findLargestIndex( $arr, $n)
{
$i; $root = $arr[0];
// Traverse the given preorder
for($i = 0; $i < $n - 1; $i++)
{
// Check if the number is greater than
// root. If yes, then return that index-1
if($arr[$i] > $root)
return $i - 1;
}
}
// Driver Code
$preorder = array(3, 2, 1, 0, 5, 4, 6);
$n = count($preorder);
echo findLargestIndex($preorder, $n);
// This code is contributed
// by 29AjayKumar
?>
Javascript
<script>
// JavaScript implementation of above approach
// Function to find the first index of the element
// that is greater than the root
function findLargestIndex(arr, n)
{
var i, root = arr[0];
// Traverse the given preorder
for(i = 0; i < n-1; i++)
{
// Check if the number is greater than root
// If yes then return that index-1
if(arr[i] > root)
return i-1;
}
}
// Driver Code
var preorder = [3, 2, 1, 0, 5, 4, 6];
var n = preorder.length;
document.write( findLargestIndex(preorder, n));
</script>
Producción:
3
Complejidad de tiempo: O(n)
Enfoque eficiente (usando búsqueda binaria) : aquí la idea es hacer uso de una forma extendida de búsqueda binaria. Los pasos son los siguientes:
- Ir a la mitad. Compruebe si el elemento en el medio es mayor que la raíz. En caso afirmativo, recursimos en la mitad izquierda de la array.
- De lo contrario, si el elemento en mid es menor que root y el elemento en mid+1 es mayor que root, devolvemos mid como nuestra respuesta.
- De lo contrario, recurrimos a la mitad derecha de la array para repetir los pasos anteriores.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the smaller elements
int findLargestIndex(int arr[], int n)
{
int root = arr[0], lb = 0, ub = n-1;
while(lb < ub)
{
int mid = (lb + ub)/2;
// Check if the element at mid
// is greater than root.
if(arr[mid] > root)
ub = mid - 1;
else
{
// if the element at mid is lesser
// than root and element at mid+1
// is greater
if(arr[mid + 1] > root)
return mid;
else lb = mid + 1;
}
}
return lb;
}
// Driver Code
int main()
{
int preorder[] = {3, 2, 1, 0, 5, 4, 6};
int n = sizeof(preorder) / sizeof(preorder[0]);
cout << findLargestIndex(preorder, n);
return 0;
}
Java
// Java implementation
// of above approach
import java.util.*;
class GFG
{
// Function to count the
// smaller elements
static int findLargestIndex(int arr[],
int n)
{
int root = arr[0],
lb = 0, ub = n - 1;
while(lb < ub)
{
int mid = (lb + ub) / 2;
// Check if the element at
// mid is greater than root.
if(arr[mid] > root)
ub = mid - 1;
else
{
// if the element at mid is
// lesser than root and
// element at mid+1 is greater
if(arr[mid + 1] > root)
return mid;
else lb = mid + 1;
}
}
return lb;
}
// Driver Code
public static void main(String args[])
{
int preorder[] = {3, 2, 1, 0, 5, 4, 6};
int n = preorder.length;
System.out.println(
findLargestIndex(preorder, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of above approach # Function to count the smaller elements def findLargestIndex(arr, n): root = arr[0]; lb = 0; ub = n - 1; while(lb < ub): mid = (lb + ub) // 2; # Check if the element at mid # is greater than root. if(arr[mid] > root): ub = mid - 1; else: # if the element at mid is lesser # than root and element at mid+1 # is greater if(arr[mid + 1] > root): return mid; else: lb = mid + 1; return lb; # Driver Code preorder = [3, 2, 1, 0, 5, 4, 6]; n = len(preorder); print(findLargestIndex(preorder, n)); # This code is contributed by mits
C#
// C# implementation
// of above approach
using System;
class GFG
{
// Function to count the
// smaller elements
static int findLargestIndex(int []arr,
int n)
{
int root = arr[0],
lb = 0, ub = n - 1;
while(lb < ub)
{
int mid = (lb + ub) / 2;
// Check if the element at
// mid is greater than root.
if(arr[mid] > root)
ub = mid - 1;
else
{
// if the element at mid is
// lesser than root and
// element at mid+1 is greater
if(arr[mid + 1] > root)
return mid;
else lb = mid + 1;
}
}
return lb;
}
// Driver Code
public static void Main(String []args)
{
int []preorder = {3, 2, 1, 0, 5, 4, 6};
int n = preorder.Length;
Console.WriteLine(
findLargestIndex(preorder, n));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of above approach
// Function to count the smaller elements
function findLargestIndex($arr, $n)
{
$root = $arr[0];
$lb = 0;
$ub = $n - 1;
while($lb < $ub)
{
$mid = (int)(($lb + $ub) / 2);
// Check if the element at mid
// is greater than root.
if($arr[$mid] > $root)
$ub = $mid - 1;
else
{
// if the element at mid is lesser
// than root and element at mid+1
// is greater
if($arr[$mid + 1] > $root)
return $mid;
else
$lb = $mid + 1;
}
}
return $lb;
}
// Driver Code
$preorder = array(3, 2, 1, 0, 5, 4, 6);
$n = count($preorder);
echo findLargestIndex($preorder, $n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation of above approach
// Function to count the smaller elements
function findLargestIndex(arr, n)
{
var root = arr[0], lb = 0, ub = n-1;
while(lb < ub)
{
var mid = parseInt((lb + ub)/2);
// Check if the element at mid
// is greater than root.
if(arr[mid] > root)
ub = mid - 1;
else
{
// if the element at mid is lesser
// than root and element at mid+1
// is greater
if(arr[mid + 1] > root)
return mid;
else lb = mid + 1;
}
}
return lb;
}
// Driver Code
var preorder = [3, 2, 1, 0, 5, 4, 6];
var n = preorder.length;
document.write( findLargestIndex(preorder, n));
</script>
Producción:
3
Complejidad de tiempo: O (logn)
Publicación traducida automáticamente
Artículo escrito por Yatharth Sant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA