Pregunta BST, encontrando el siguiente nodo más alto


En BST, según Programación Entrevistas Expuestas.

"Dado un nodo, incluso puede encontrar el siguiente nodo más alto en el tiempo O (log (n))" Pg 65

Un nodo en BST tiene el elemento secundario derecho como el siguiente nodo más alto, entonces ¿por qué O (log (n))? Por favor corrige

Primero responde la pregunta, luego niega


5
2018-01-08 08:50


origen


Respuestas:


"Un nodo en BST tiene a la derecha como el siguiente nodo más alto" (suponiendo que aquí "más arriba" significa el siguiente valor más grande), no, no lo tiene. Ese poder sea ​​el caso si no tiene un nodo izquierdo, pero no siempre es así (consulte el punto 1 a continuación).

El siguiente valor más grande (usando ese término en lugar de "más alto", ya que este último podría confundirse con la altura del árbol) proviene de uno de dos lugares:

Primero, si el nodo actual tiene un hijo derecho, muévase hacia ese niño derecho y luego, siempre que pueda ver a un niño izquierdo, muévase hacia él.

En otras palabras (S y D son la fuente y el destino):

   S
  / \
 x   x <- This is the node your simple explanation chose,
    / \    but it's the wrong one in this case.
   x   x
  / \
 D   x
  \
   x

De lo contrario (el nodo actual tiene no right child) necesitas moverte hacia el padre continuamente (para que los nodos necesiten un puntero a la derecha, a la izquierda y al padre) hasta que el nodo que moviste de era un niño de la izquierda Si llegas a la raíz y te todavía no se ha movido desde un hijo izquierdo, su nodo original ya era el más alto en el árbol. Gráficamente eso sería:

x
 \
  D
 / \
x   x
 \
  x
 / \
x   S
   /
  x

El pseudocódigo para tal función sería:

def getNextNode (node):
    if node.right != NULL:
        node = node.right
        while node.left != NULL:
            node = node.left
        return node

    while node.parent != NULL:
        if node.parent.left == node:
            return node.parent
        node = node.parent

    return NULL

Como el esfuerzo es proporcional a la altura del árbol, equilibrado El árbol (como rojo-negro, 2-3-4 y AVL) tendrá una complejidad de tiempo de O (registro N) ya que la altura tiene una relación de registro con el número de elementos. El libro habla de árboles equilibrados aquí, porque incluye fragmentos de ellos como:

  • Esta búsqueda es una operación rápida porque elimina la mitad de los nodos de su búsqueda en cada iteración.
  • La búsqueda es una operación O (log (n)) en un árbol de búsqueda binario.
  • La búsqueda es solo O (log (n)) si puede garantizar que la cantidad de nodos que quedan por buscar se reduzca a la mitad o casi a la mitad en cada iteración.

Entonces, aunque admite en esa última cita que un BST puede no equilibrada, la propiedad O (log N) es solo para aquellas variantes que son.

Para árboles no balanceados, la complejidad (peor caso) sería O (n) ya que podrías terminar con árboles degenerados como:

S             D
 \           /
  x         x
   \         \
    x         x
     \         \
      x         x
       \         \
        x         x
       /           \
      D             S

12
2018-01-08 08:58



Aquí está mi pseudo implementación en Java. Espero eso ayude.

Estructura del nodo

public Class Node{

int value {get, set};
Node leftChild {get,set};
Node rightChild{get, set};
Node parent{get,set};
}

Función para encontrar el siguiente nodo más alto

public Node findNextBiggest(Node n){
    Node temp=n;
    if(n.getRightChild()==null)
    {
        while(n.getParent()!=null && temp.getValue()>n.getParent().getValue())
        {
            n=n.getParent():
        }
        return n.getParent();
    }
    else
    {
        n=n.getRightChild();
        while (n.getLeftChild()!=null && n.getLeftChild().getValue()>temp.getValue())
        {
            n=n.getLeftChild();
        }
    return n;
    }
}

1
2018-04-11 16:20



Creo que, podemos encontrar el siguiente nodo más alto simplemente encontrando el sucesor inorder del nodo.

Pasos -

  • Primero, ve al hijo correcto del nodo.
  • Luego muévete lo más a la izquierda posible. Cuando llegue al nodo hoja, imprima ese nodo hoja ya que ese nodo es su siguiente nodo más alto en comparación con el nodo dado.

0
2018-06-06 14:56