Dado un árbol de búsqueda binario y un Node de destino K. La tarea es encontrar el Node con la diferencia absoluta mínima con el valor de destino dado K.
NOTA: El enfoque utilizado debe consumir espacio extra constante O(1). No se deben usar contenedores recursivos o apilados/en cola.
Ejemplos:
Input: k = 4 Output: 4 Input: k = 18 Output: 17
Una solución simple mencionada en esta publicación utiliza la recursividad para obtener el elemento más cercano a una clave en el árbol de búsqueda binario. El método utilizado en la publicación mencionada anteriormente consume O (n) espacio adicional debido a la recursividad.
Ahora podemos modificar fácilmente el enfoque mencionado anteriormente utilizando el recorrido de Morris , que es un enfoque eficiente en el espacio para realizar el recorrido del árbol en orden sin usar la recursividad o la pila/cola en el espacio constante O (1).
El recorrido de Morris se basa en árboles binarios subprocesos que utilizan punteros NULL en un árbol para que apunten a algunos Nodes sucesores o predecesores. Como en un árbol binario con n Nodes, n+1 punteros NULL desperdician memoria.
En el algoritmo que se menciona a continuación, simplemente hacemos un recorrido de árbol en orden y mientras lo hacemos usando Morris Traversal verificamos las diferencias entre los datos del Node y la clave y mantenemos dos variables ‘diff’ y ‘closest’ que se actualizan cuando encontramos un más cercano Node a la clave. Cuando terminamos con el recorrido completo del árbol en orden, tenemos el Node más cercano.
Algoritmo :
1) Initialize Current as root.
2) Initialize a variable diff as INT_MAX.
3)initialize a variable closest(pointer to node) which
will be returned.
4) While current is not NULL:
4.1) If the current has no left child:
a) If the absolute difference between current's data
and the key is smaller than diff:
1) Set diff as the absolute difference between the
current node and the key.
2) Set closest as the current node.
b)Otherwise, Move to the right child of current.
4.2) Else, here we have 2 cases:
a) Find the inorder predecessor of the current node.
Inorder predecessor is the rightmost node
in the left subtree or left child itself.
b) If the right child of the inorder predecessor is NULL:
1) Set current as the right child of its inorder
predecessor(Making threads between nodes).
2) Move current node to its left child.
c) Else, if the threaded link between the current node
and it's inorder predecessor already exists :
1) Set right pointer of the inorder predecessor node as NULL.
2) If the absolute difference between current's data and
the key is smaller than diff:
a) Set diff variable as the absolute difference between
the current node and the key.
b) Set closest as the current node.
3) Move current to its right child.
5)By the time we have traversed the whole tree, we have the
closest node, so we simply return closest.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find closest value in
// a Binary Search Tree.
#include <iostream>
#include <limits.h>
using namespace std;
// Tree Node
struct Node {
int data;
Node *left, *right;
};
// Utility function to create a new Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to find the Node closest to the
// given key in BST using Morris Traversal
Node* closestNodeUsingMorrisTraversal(Node* root,
int key)
{
int diff = INT_MAX;
Node* curr = root;
Node* closest;
while (curr) {
if (curr->left == NULL) {
// updating diff if the current diff is
// smaller than prev difference
if (diff > abs(curr->data - key)) {
diff = abs(curr->data - key);
closest = curr;
}
curr = curr->right;
}
else {
// finding the inorder predecessor
Node* pre = curr->left;
while (pre->right != NULL &&
pre->right != curr)
pre = pre->right;
if (pre->right == NULL) {
pre->right = curr;
curr = curr->left;
}
// threaded link between curr and
// its predecessor already exists
else {
pre->right = NULL;
// if a closer Node found, then update
// the diff and set closest to current
if (diff > abs(curr->data - key)) {
diff = abs(curr->data - key);
closest = curr;
}
// moving to the right child
curr = curr->right;
}
}
}
return closest;
}
// Driver Code
int main()
{
/* Constructed binary tree is
5
/ \
3 9
/ \ / \
1 2 8 12 */
Node* root = newNode(5);
root->left = newNode(3);
root->right = newNode(9);
root->left->left = newNode(1);
root->left->right = newNode(2);
root->right->left = newNode(8);
root->right->right = newNode(12);
cout << closestNodeUsingMorrisTraversal(root, 10)->data;
return 0;
}
Java
// Java program to find closest value in
// a Binary Search Tree.
class GFG
{
// Tree Node
static class Node
{
int data;
Node left, right;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to find the Node closest to the
// given key in BST using Morris Traversal
static Node closestNodeUsingMorrisTraversal(Node root,
int key)
{
int diff = Integer.MAX_VALUE;
Node curr = root;
Node closest = null;
while (curr != null)
{
if (curr.left == null)
{
// updating diff if the current diff is
// smaller than prev difference
if (diff > Math.abs(curr.data - key))
{
diff = Math.abs(curr.data - key);
closest = curr;
}
curr = curr.right;
}
else
{
// finding the inorder predecessor
Node pre = curr.left;
while (pre.right != null &&
pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
// threaded link between curr and
// its predecessor already exists
else
{
pre.right = null;
// if a closer Node found, then update
// the diff and set closest to current
if (diff > Math.abs(curr.data - key))
{
diff = Math.abs(curr.data - key);
closest = curr;
}
// moving to the right child
curr = curr.right;
}
}
}
return closest;
}
// Driver Code
public static void main(String[] args)
{
/* Constructed binary tree is
5
/ \
3 9
/ \ / \
1 2 8 12 */
Node root = newNode(5);
root.left = newNode(3);
root.right = newNode(9);
root.left.left = newNode(1);
root.left.right = newNode(2);
root.right.left = newNode(8);
root.right.right = newNode(12);
System.out.println(closestNodeUsingMorrisTraversal(root, 10).data);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to find closest value in # Binary search Tree _MIN = -2147483648 _MAX = 2147483648 # Helper function that allocates a new # node with the given data and None left # and right pointers. class newNode: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Function to find the Node closest to the # given key in BST using Morris Traversal def closestNodeUsingMorrisTraversal(root,key): diff = _MAX curr = root closest=0 while (curr) : if (curr.left == None) : # updating diff if the current diff is # smaller than prev difference if (diff > abs(curr.data - key)) : diff = abs(curr.data - key) closest = curr curr = curr.right else : # finding the inorder predecessor pre = curr.left while (pre.right != None and pre.right != curr): pre = pre.right if (pre.right == None): pre.right = curr curr = curr.left # threaded link between curr and # its predecessor already exists else : pre.right = None # if a closer Node found, then update # the diff and set closest to current if (diff > abs(curr.data - key)) : diff = abs(curr.data - key) closest = curr # moving to the right child curr = curr.right return closest # Driver Code if __name__ == '__main__': """ /* Constructed binary tree is 5 / \ 3 9 / \ / \ 1 2 8 12 */ """ root = newNode(5) root.left = newNode(3) root.right = newNode(9) root.left.right = newNode(2) root.left.left = newNode(1) root.right.right = newNode(12) root.right.left = newNode(8) print(closestNodeUsingMorrisTraversal(root, 10).data) # This code is contributed # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find closest value in
// a Binary Search Tree.
using System;
class GFG
{
// Tree Node
public class Node
{
public int data;
public Node left, right;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to find the Node closest to the
// given key in BST using Morris Traversal
static Node closestNodeUsingMorrisTraversal(Node root,
int key)
{
int diff = int.MaxValue;
Node curr = root;
Node closest = null;
while (curr != null)
{
if (curr.left == null)
{
// updating diff if the current diff is
// smaller than prev difference
if (diff > Math.Abs(curr.data - key))
{
diff = Math.Abs(curr.data - key);
closest = curr;
}
curr = curr.right;
}
else
{
// finding the inorder predecessor
Node pre = curr.left;
while (pre.right != null &&
pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
// threaded link between curr and
// its predecessor already exists
else
{
pre.right = null;
// if a closer Node found, then update
// the diff and set closest to current
if (diff > Math.Abs(curr.data - key))
{
diff = Math.Abs(curr.data - key);
closest = curr;
}
// moving to the right child
curr = curr.right;
}
}
}
return closest;
}
// Driver Code
public static void Main(String[] args)
{
/* Constructed binary tree is
5
/ \
3 9
/ \ / \
1 2 8 12 */
Node root = newNode(5);
root.left = newNode(3);
root.right = newNode(9);
root.left.left = newNode(1);
root.left.right = newNode(2);
root.right.left = newNode(8);
root.right.right = newNode(12);
Console.WriteLine(closestNodeUsingMorrisTraversal(root, 10).data);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find closest value in
// a Binary Search Tree.
// Tree Node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Utility function to create a new Node
function newNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to find the Node closest to the
// given key in BST using Morris Traversal
function closestNodeUsingMorrisTraversal(root, key)
{
var diff = 1000000000;
var curr = root;
var closest = null;
while (curr != null)
{
if (curr.left == null)
{
// updating diff if the current diff is
// smaller than prev difference
if (diff > Math.abs(curr.data - key))
{
diff = Math.abs(curr.data - key);
closest = curr;
}
curr = curr.right;
}
else
{
// finding the inorder predecessor
var pre = curr.left;
while (pre.right != null &&
pre.right != curr)
pre = pre.right;
if (pre.right == null)
{
pre.right = curr;
curr = curr.left;
}
// threaded link between curr and
// its predecessor already exists
else
{
pre.right = null;
// if a closer Node found, then update
// the diff and set closest to current
if (diff > Math.abs(curr.data - key))
{
diff = Math.abs(curr.data - key);
closest = curr;
}
// moving to the right child
curr = curr.right;
}
}
}
return closest;
}
// Driver Code
/* Constructed binary tree is
5
/ \
3 9
/ \ / \
1 2 8 12 */
var root = newNode(5);
root.left = newNode(3);
root.right = newNode(9);
root.left.left = newNode(1);
root.left.right = newNode(2);
root.right.left = newNode(8);
root.right.right = newNode(12);
document.write(closestNodeUsingMorrisTraversal(root, 10).data);
// This code is contributed by itsok.
</script>
Producción:
9
Tiempo Complejidad : 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