Dado un árbol de búsqueda binario y un número x, encuentre el piso de x en el BST dado.
Input : x = 14 and root of below tree
10
/ \
5 15
/ \
12 30
Output : 12
Input : x = 15 and root of below tree
10
/ \
5 15
/ \
12 30
Output : 15
Una solución simple es atravesar el árbol usando (En orden o Preorden o Postorden) y realizar un seguimiento del elemento más pequeño o igual más cercano. La complejidad temporal de esta solución es O(n), donde n es el número total de Nodes en BST.
Podemos encontrar eficientemente el elemento más pequeño o el mismo más cercano en el tiempo O (h) donde h es la altura de BST. Algoritmo para encontrar el piso de una clave en un árbol de búsqueda binaria (BST):
1 Start at the root Node.
2 If root->data == key,
floor of the key is equal
to the root.
3 Else if root->data > key, then
the floor of the key must lie in the
left subtree.
4 Else floor may lie in the right subtree
but only if there is a value lesser than
or equal to the key. If not, then the root is
the key.
Para encontrar el techo de BST, puede consultar este artículo.
C++
// C++ code to find floor of a key in BST
#include <bits/stdc++.h>
using namespace std;
/*Structure of each Node in the tree*/
struct Node {
int data;
Node *left, *right;
};
/*This function is used to create and
initializes new Nodes*/
Node* newNode(int key)
{
Node* temp = new Node;
temp->left = temp->right = NULL;
temp->data = key;
return temp;
}
/* This function is used to insert
new values in BST*/
Node* insert(Node* root, int key)
{
if (!root)
return newNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
/*This function is used to find floor of a key*/
int floor(Node* root, int key)
{
if (!root)
return INT_MAX;
/* If root->data is equal to key */
if (root->data == key)
return root->data;
/* If root->data is greater than the key */
if (root->data > key)
return floor(root->left, key);
/* Else, the floor may lie in right subtree
or may be equal to the root*/
int floorValue = floor(root->right, key);
return (floorValue <= key) ? floorValue : root->data;
}
int main()
{
/* Let us create following BST
7
/ \
5 10
/ \ / \
3 6 8 12 */
Node* root = NULL;
root = insert(root, 7);
insert(root, 10);
insert(root, 5);
insert(root, 3);
insert(root, 6);
insert(root, 8);
insert(root, 12);
cout << floor(root, 9) << endl;
return 0;
}
Java
// Java code to find floor of a key in BST
class GfG {
/*Structure of each Node in the tree*/
static class Node {
int data;
Node left, right;
}
/*This function is used to create and
initializes new Nodes*/
static Node newNode(int key)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.data = key;
return temp;
}
/* This function is used to insert
new values in BST*/
static Node insert(Node root, int key)
{
if (root == null)
return newNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
/*This function is used to find floor of a key*/
static int floor(Node root, int key)
{
if (root == null)
return Integer.MAX_VALUE;
/* If root->data is equal to key */
if (root.data == key)
return root.data;
/* If root->data is greater than the key */
if (root.data > key)
return floor(root.left, key);
/* Else, the floor may lie in right subtree
or may be equal to the root*/
int floorValue = floor(root.right, key);
return (floorValue <= key) ? floorValue : root.data;
}
public static void main(String[] args)
{
/* Let us create following BST
7
/ \
5 10
/ \ / \
3 6 8 12 */
Node root = null;
root = insert(root, 7);
insert(root, 10);
insert(root, 5);
insert(root, 3);
insert(root, 6);
insert(root, 8);
insert(root, 12);
System.out.println(floor(root, 9));
}
}
Python3
# Python3 code to find floor of a key in BST INT_MAX = 2147483647 # Binary Tree Node """ A utility function to create a new BST node """ class newNode: # Construct to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None """ This function is used to insert new values in BST""" def insert(root, key): if (not root): return newNode(key) if (key < root.data): root.left = insert(root.left, key) else: root.right = insert(root.right, key) return root """This function is used to find floor of a key""" def floor(root, key) : if (not root): return INT_MAX """ If root.data is equal to key """ if (root.data == key) : return root.data """ If root.data is greater than the key """ if (root.data > key) : return floor(root.left, key) """ Else, the floor may lie in right subtree or may be equal to the root""" floorValue = floor(root.right, key) return floorValue if (floorValue <= key) else root.data # Driver Code if __name__ == '__main__': """ Let us create following BST 7 / \ 5 10 / \ / \ 3 6 8 12 """ root = None root = insert(root, 7) insert(root, 10) insert(root, 5) insert(root, 3) insert(root, 6) insert(root, 8) insert(root, 12) print(floor(root, 9)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# code to find floor of a key in BST
using System;
class GfG {
/*Structure of each Node in the tree*/
public class Node {
public int data;
public Node left, right;
}
/*This function is used to create and
initializes new Nodes*/
static Node newNode(int key)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.data = key;
return temp;
}
/* This function is used to insert
new values in BST*/
static Node insert(Node root, int key)
{
if (root == null)
return newNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
/*This function is used to find floor of a key*/
static int floor(Node root, int key)
{
if (root == null)
return int.MaxValue;
/* If root->data is equal to key */
if (root.data == key)
return root.data;
/* If root->data is greater than the key */
if (root.data > key)
return floor(root.left, key);
/* Else, the floor may lie in right subtree
or may be equal to the root*/
int floorValue = floor(root.right, key);
return (floorValue <= key) ? floorValue : root.data;
}
// Driver code
public static void Main(String[] args)
{
/* Let us create following BST
7
/ \
5 10
/ \ / \
3 6 8 12 */
Node root = null;
root = insert(root, 7);
insert(root, 10);
insert(root, 5);
insert(root, 3);
insert(root, 6);
insert(root, 8);
insert(root, 12);
Console.WriteLine(floor(root, 9));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript code to find floor of a key in BST
class Node
{
constructor()
{
this.data=0;
this.left=this.right=null;
}
}
/*This function is used to create and
initializes new Nodes*/
function newNode(key)
{
let temp = new Node();
temp.left = null;
temp.right = null;
temp.data = key;
return temp;
}
/* This function is used to insert
new values in BST*/
function insert(root,key)
{
if (root == null)
return newNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
/*This function is used to find floor of a key*/
function floor(root,key)
{
if (root == null)
return Number.MAX_VALUE;
/* If root->data is equal to key */
if (root.data == key)
return root.data;
/* If root->data is greater than the key */
if (root.data > key)
return floor(root.left, key);
/* Else, the floor may lie in right subtree
or may be equal to the root*/
let floorValue = floor(root.right, key);
return (floorValue <= key) ? floorValue : root.data;
}
/* Let us create following BST
7
/ \
5 10
/ \ / \
3 6 8 12 */
let root = null;
root = insert(root, 7);
insert(root, 10);
insert(root, 5);
insert(root, 3);
insert(root, 6);
insert(root, 8);
insert(root, 12);
document.write(floor(root, 9));
// This code is contributed by rag2127
</script>
Producción:
8