Dado un árbol de búsqueda binaria y un número N, la tarea es encontrar el número más pequeño en el árbol de búsqueda binaria que sea mayor o igual que N.
Ejemplos:
Input: N = 5
8
/ \
7 10
/ / \
2 9 13
Output: 7
As 7 is the smallest number in BST which is greater than N = 5.
Input: N = 10
8
/ \
5 11
/ \
2 7
\
3
Output: 11
As 11 is the smallest number in BST which is greater than N = 10.
Ya se ha discutido una solución recursiva para este problema en esta publicación . A continuación se muestra un enfoque iterativo para el problema:
Usando Morris Traversal , el problema anterior se puede resolver en espacio constante. Encuentre el sucesor en orden del objetivo. Mantenga dos punteros, uno que apunta al Node actual y otro para almacenar la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to find the smallest value greater
// than or equal to N
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
// To create new BST Node
Node* newNode(int item)
{
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// To insert a new node in BST
Node* insert(Node* node, int key)
{
// if tree is empty return new node
if (node == NULL)
return newNode(key);
// if key is less than or greater than
// node value then recur down the tree
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
// return the (unchanged) node pointer
return node;
}
// Returns smallest value greater than or
// equal to key.
int findFloor(Node* root, int key)
{
Node *curr = root, *ans = NULL;
// traverse in the tree
while (curr) {
// if the node is smaller than N,
// move right.
if (curr->key > key) {
ans = curr;
curr = curr->left;
}
// if it is equal to N, then it will be
// the answer
else if (curr->key == key) {
ans = curr;
break;
}
else // move to the right of the tree
curr = curr->right;
}
if (ans != NULL)
return ans->key;
return -1;
}
// Driver code
int main()
{
int N = 13;
Node* root = insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 25);
printf("%d", findFloor(root, 15));
return 0;
}
Java
// Java code to find the smallest value greater
// than or equal to N
class GFG
{
static class Node
{
int key;
Node left, right;
};
// To create new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// To insert a new node in BST
static Node insert(Node node, int key)
{
// if tree is empty return new node
if (node == null)
{
return newNode(key);
}
// if key is less than or greater than
// node value then recur down the tree
if (key < node.key)
{
node.left = insert(node.left, key);
}
else if (key > node.key)
{
node.right = insert(node.right, key);
}
// return the (unchanged) node pointer
return node;
}
// Returns smallest value greater than or
// equal to key.
static int findFloor(Node root, int key)
{
Node curr = root, ans = null;
// traverse in the tree
while (curr != null)
{
// if the node is smaller than N,
// move right.
if (curr.key > key)
{
ans = curr;
curr = curr.left;
}
// if it is equal to N, then it will be
// the answer
else if (curr.key == key)
{
ans = curr;
break;
}
else // move to the right of the tree
{
curr = curr.right;
}
}
if (ans != null)
{
return ans.key;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int N = 13;
Node root = new Node();
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 25);
System.out.printf("%d", findFloor(root, 15));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 code to find the smallest # value greater than or equal to N class Node: def __init__(self, key): self.key = key self.left = None self.right = None # To insert a new node in BST def insert(node: Node, key: int) -> Node: # If tree is empty return new node if (node is None): return Node(key) # If key is less than or greater than # node value then recur down the tree if (key < node.key): node.left = insert(node.left, key) elif (key > node.key): node.right = insert(node.right, key) # Return the (unchanged) node pointer return node # Returns smallest value greater than or # equal to key. def findFloor(root: Node, key: int) -> int: curr = root ans = None # Traverse in the tree while (curr): # If the node is smaller than N, # move right. if (curr.key > key): ans = curr curr = curr.left # If it is equal to N, then # it will be the answer elif (curr.key == key): ans = curr break else: # Move to the right of the tree curr = curr.right if (ans != None): return ans.key return -1 # Driver code if __name__ == "__main__": N = 13 root = None root = insert(root, 19) insert(root, 2) insert(root, 1) insert(root, 3) insert(root, 12) insert(root, 9) insert(root, 21) insert(root, 25) print(findFloor(root, 15)) # This code is contributed by sanjeev2552
C#
// C# code to find the smallest value greater
// than or equal to N
using System;
using System.Collections.Generic;
class GFG
{
class Node
{
public int key;
public Node left, right;
};
// To create new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// To insert a new node in BST
static Node insert(Node node, int key)
{
// if tree is empty return new node
if (node == null)
{
return newNode(key);
}
// if key is less than or greater than
// node value then recur down the tree
if (key < node.key)
{
node.left = insert(node.left, key);
}
else if (key > node.key)
{
node.right = insert(node.right, key);
}
// return the (unchanged) node pointer
return node;
}
// Returns smallest value greater than or
// equal to key.
static int findFloor(Node root, int key)
{
Node curr = root, ans = null;
// traverse in the tree
while (curr != null)
{
// if the node is smaller than N,
// move right.
if (curr.key > key)
{
ans = curr;
curr = curr.left;
}
// if it is equal to N, then it will be
// the answer
else if (curr.key == key)
{
ans = curr;
break;
}
else // move to the right of the tree
{
curr = curr.right;
}
}
if (ans != null)
{
return ans.key;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node();
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 25);
Console.Write("{0}", findFloor(root, 15));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript code to find the smallest
// value greater than or equal to N
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
// To create new BST Node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// To insert a new node in BST
function insert(node, key)
{
// If tree is empty return new node
if (node == null)
{
return newNode(key);
}
// If key is less than or greater than
// node value then recur down the tree
if (key < node.key)
{
node.left = insert(node.left, key);
}
else if (key > node.key)
{
node.right = insert(node.right, key);
}
// Return the (unchanged) node pointer
return node;
}
// Returns smallest value greater than or
// equal to key.
function findFloor(root, key)
{
var curr = root, ans = null;
// Traverse in the tree
while (curr != null)
{
// If the node is smaller than N,
// move right.
if (curr.key > key)
{
ans = curr;
curr = curr.left;
}
// If it is equal to N, then it will be
// the answer
else if (curr.key == key)
{
ans = curr;
break;
}
// Move to the right of the tree
else
{
curr = curr.right;
}
}
if (ans != null)
{
return ans.key;
}
return -1;
}
// Driver code
var root = new Node();
insert(root, 19);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 25);
document.write(findFloor(root, 15));
// This code is contributed by rutvik_56
</script>
Producción:
19
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AnishSinghWalia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA