Para un árbol binario dado encontrar el máximo de búsqueda binaria sub-árbol

https://stackoverflow.com/questions/3163366

02-10-2019
|

Pregunta

En un árbol binario dado, encontrar el subárbol más grande que es también árbol binario de búsqueda?

Ejemplo:

Entrada:

                   10
               /         \
             50           150
            /  \         /   \
          25    75     200    20
         / \   / \    /  \    / \
        15 35 65 30  120 135 155 250

Salida:

Solución

Esta respuesta previamente contenía un O (n log n) algoritmo basado en árboles enlace / corte. Aquí es un simple O (n) solución.

El núcleo es un procedimiento que acepta un nodo, el BSST máximo único arraigada en su hijo izquierdo, el BSST máximo único arraigada en su hijo derecho, y punteros a los más a la izquierda y derecha-mayoría de los elementos de estos BSSTs. Destruye sus entradas (evitables con estructuras de datos persistentes) y construye la BSST máximo único enraizado en el nodo dado, junto con sus elementos mínimo y máximo. Todos los nodos BSST se anotan con el número de descendientes. Al igual que antes, este procedimiento se llama repetidamente a partir de un recorrido posterior a la orden. Para recuperar el sub-árbol, recuerda la raíz de la mayor BSST; reconstruir sólo requiere un recorrido sencillo.

Voy a tratar a la izquierda BSST solamente; la derecha es simétrica. Si la raíz del BSST izquierda es mayor que la nueva raíz, entonces el todo el árbol secundario se retira, y la nueva raíz está más a la izquierda. De lo contrario, el extremo izquierdo de edad nodo está todavía más a la izquierda. Comenzando desde el nodo más a la derecha de la BSST izquierda y se mueve hacia arriba, encontrar el primer nodo que es menor o igual a la raíz. Su hijo derecho debe ser eliminado; nota ahora que debido a la propiedad BST, no hay otros nodos tienen que ir! Proceder a la raíz de la BSST izquierda, la actualización de las cuentas para reflejar la eliminación.

La razón de esto es O (n) es que a pesar del bucle, cada borde en el árbol original está en esencia atravesada sólo una vez.

EDIT: colectivamente, las trayectorias recorridas son los caminos máxima en línea recta en una BST, a excepción de la columna izquierda y la columna derecha. Por ejemplo, en la entrada

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / \             / \
    /   \           /   \
   /     \         /     \
  B       F       J       N
 / \     / \     / \     / \
A   C   E   G   I   K   M   O

aquí están las llamadas recursivas en la que se recorre cada borde:

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / h             h \
    /   h           h   \
   /     h         h     \
  B       F       J       N
 / d     d h     h l     l \
A   C   E   G   I   K   M   O

Otros consejos

El algoritmo anterior (ver revisiones) fue O(n^2) - que se puede generalizar a O(n log n) al notar el hecho de que:

Si b es la raíz de la mayor BST y b.left.value < b.value, entonces b.left también está en el BST (lo mismo para b.right.value ≥ b.value)
Si b es la raíz de la mayor BST y también está en el BST, entonces cada nodo entre A y B está en el BST.

Así que si c es de entre a y b, y c no está en la BST arraigado por b, ni es un (debido a (2.)) . El uso de este hecho, podemos determinar fácilmente si un nodo está en el BST arraigado por ningún ancestro dado. Vamos a hacer esto pasando un nodo en nuestra función, junto con una lista de sus antepasados, y el asociado min / maxValues ??que la corriente de nodo secundario tendría que cumplir si es que los antepasados ??eran la raíz de la mayor BST (nos' llamaremos a esta lista ancestorList). Almacenaremos toda la colección de potenciales de base en overallRootsList

Vamos a definir una estructura llamada potentialRoot de la siguiente manera:

Cada potentialRoot contiene los siguientes valores:
          * nodo : El nodo que estamos considerando para la raíz del BST
          * minValue y maxValue : la gama de otro nodo debe estar entre a formar parte de la BST arraigado por el nodo (diferente para cada nodo)
          * subnodos : Lista A del resto de los nodos en la mayor BST arraigado por el nodo

El código de pseudo es similar al siguiente (nota que todas las listas mencionadas son listas de potentialRoots)

FindLargestBST(node, ancestorList):
    leftList, rightList = empty lists
    for each potentialRoot in ancestorList:
        if potentialRoot.minValue < node.Value ≤ potentialRoot.maxValue:
            add node to potentialRoot.subNodes (due to (1.))
            (note that the following copies contain references, not copies, of subNodes)
            add copy of potentialRoot to leftList, setting maxValue = node.Value
            add copy of potentialRoot to rightList, setting minValue = node.Value

    add the potentialRoot (node, -∞, +∞) to leftList, rightList, and overallRootsList
    FindLargestBST(node.left, leftList)
    FindLargestBST(node.right, rightList)

Al overallRootsList final será una lista de potentialRoots n, cada uno con una lista de subnodos. El de la lista de subnodos más grande es su BST.

Puesto que hay ancestorList, a continuación, (suponiendo que el árbol está equilibrado), el algoritmo se ejecuta en O(n log n)

Una pregunta interesante!

Mi intento anterior fue estúpidamente mal!

Aquí es otro intento (con suerte corregir este momento).

Estoy asumiendo que el árbol está conectado.

Supongamos que para cada nodo n del árbol, que tenía un conjunto de descendientes de N, S _n con la propiedad de que

Para cada miembro x de S _n, el único camino de N a X es una búsqueda binaria árbol (que es sólo un camino, pero todavía se puede considerar que un árbol).
Para cada y descendiente de x, tal que la trayectoria de n a y es una BST, Y es en S _n.

El conjunto de nodos S _n, le da la más grande BST arraigada en el n.

Podemos construir S _n para cada nodo haciendo una primera búsqueda en profundidad en el árbol, y pasando la información de la ruta (la ruta desde la raíz hasta el nodo actual) y la actualización de los conjuntos de la los nodos en el camino por el retroceso a lo largo del camino.

Cuando se visita un nodo, caminamos por el sendero, y comprobar si la propiedad BST se cumple para ese segmento de la ruta se acercó hasta el momento. Si es así, le añadimos el nodo actual al conjunto correspondiente del nodo de la ruta que puedes ir andando a. Dejamos de caminar el camino de momento se viola la propiedad BST. Comprobación de si el segmento de ruta que entramos hasta ahora es una BST puede hacerse en O (1) el tiempo, durante un tiempo O (PATH_LENGTH) de procesamiento total de tiempo, para cada nodo.

Al final, cada nodo tendrá su correspondiente S _n pobladas. Podemos recorrer el árbol ahora y recoger el nodo con el mayor valor de S _n.

El tiempo necesario para esto es la suma de las profundidades de los nodos (en el peor de los casos), y que es O (nlogn) en el caso promedio (véase la Sección 5.2.4 de http://www.toves.org/books/data/ch05-trees/index.html ), pero O (n ^ 2) en el peor caso.

Quizás una manera más inteligente para actualizar los conjuntos garantizará una reducción en el tiempo de los casos.

El pseudo-código podría ser algo como:

static Tree void LargestBST(Tree t)
{
    LargestBST(t, new List<Pair>());
    // Walk the tree and return the largest subtree with max |S_n|.
}

static Tree LargestBST(Tree t, List<Pair> path)
{
    if (t == null) return;

    t.Set.Add(t.Value);

    int value = t.Value;
    int maxVal = value;
    int minVal = value;

    foreach (Pair p in path)
    {
        if (p.isRight)
        {
            if (minVal < p.node.Value)
            {
                break;
            }
        }

        if (!p.isRight)
        {
            if (maxVal > p.node.Value)
            {
                break;
            }
        }

        p.node.Set.Add(t.Value);

        if (p.node.Value <= minVal)
        {
            minVal = p.node.Value;
        }

        if (p.node.Value >= maxVal)
        {
            maxVal = p.node.Value;
        }
    }

    Pair pl = new Pair();
    pl.node = t;
    pl.isRight = false;

    path.Insert(0, pl);
    LargestBST(t.Left, path);

    path.RemoveAt(0);

    Pair pr = new Pair();
    pr.node = t;
    pr.isRight = true;

    path.Insert(0, pr);

    LargestBST(t.Right, path);

    path.RemoveAt(0);

}

MAYOR búsqueda binaria ÁRBOL EN un árbol binario:

Hay dos formas en que podemos abordar este problema,

i) no indujo más grande BST (Desde un nodo, todos sus niños necesitan no satisfacen la condición de BST)

ii) más grande BST inducida (Desde un nodo, todos sus hijos satisfarán la condición BST)

Vamos a discutir acerca de la BST más grande (no inducida) aquí. Vamos a seguir el enfoque arriba abajo (Agrega recorrido orden) para resolver esto.

a) alcanzar el nodo hoja

b) un nodo de árbol (de la hoja) devolverá un objeto TreeNodeHelper que tiene los siguientes campos en el mismo.

public static class TreeNodeHelper {
        TreeNode node;
        int nodes;
        Integer maxValue;
        Integer minValue;
        boolean isBST;


        public TreeNodeHelper() {}

        public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {
            this.node = node;
            this.nodes = nodes;
            this.maxValue = maxValue;
            this.minValue = minValue;
            this.isBST = isBST;
        }      
    }

c) inicialmente desde el nodo de hoja, los nodos = 1, isBST = true, minValue = maxValue = node.data. Y aún más, los nodos de cómputo de tiempo se incrementaron si satisface la condición de BST.

d) Con la ayuda de esto, vamos a comprobar la condición BST con el nodo actual. Y vamos a repetir el mismo hasta la raíz.

e) de cada nodo se devolverán dos objetos. uno para la última BST máximo y otro para los nodos actuales BST satisfacer. Así que, desde cada nodo (por encima de la hoja) (2 + 2) = 4 (2 para subárbol izquierdo y 2 para sub árbol derecha) objetos serán comparados y serán devueltos dos.

f) el objeto final de nodo máximo de la raíz será la más grande BST

PROBLEMA:

Hay un problema en este enfoque. Mientras que sigue este enfoque, si un subárbol no se satisface la condición BST con el nodo actual, no podemos simplemente ignorar el subárbol (incluso tiene menos número de nodos). Por ejemplo

A partir de los nodos hoja (20.110) los objetos serán probados con el nodo (105), satisface la condición. Pero cuando se alcanza el nodo (95) el nodo de hoja (20) no satisface la condición de BST. Dado que esta solución es que BST (no inducido) no debemos ignorar nodo (105) y el nodo (110) que satisface la condición. Así desde el nodo (95) tenemos que dar marcha atrás de nuevo el ensayo del estado BST y atrapar a los nodos (105, 110).

El código completo para esta implementación está disponible en este enlace

https://github.com/dineshappavoo/Implementation/tree/master/ LARGEST_BST_IN_BT_NOT_INDUCED_VER1.0

Un árbol binario de búsqueda le dará un resultado ordenada si lo hace A en orden de recorrido. Por lo tanto, hacer un recorrido en orden para todo el árbol binario. La secuencia ordenada más larga es más grande que su árbol de búsqueda binaria sub.

Haga un recorrido en orden de elementos (visita dejó, VISITA raíz, VISITA derecha)
Al hacerlo, obtener los datos del nodo, comparar si los datos nodo anterior es menor que los próximos datos. Si es así, el contador se incrementan en 1. Depositar el nodo de inicio.
Cuando la comparación falla, almacenar el nodo final y el contador de reposición a 0
Guarde esta información (contador, inicio, fin) nodo en una estructura de matriz para después encontrar que está teniendo el valor máximo y que le dará la más larga de búsqueda binaria sub árbol

GetLargestSortedBinarySubtree(thisNode, ref OverallBestTree)
    if thisNode == null
        Return null
    LeftLargest = GetLargestSortedBinarySubtree(thisNode.LeftNode, ref OverallBestTree)
    RightLargest = GetLargestSortedBinarySubtree(thisNode.RightNode, ref OverallBestTree)
    if LeftLargest.Max < thisNode.Value & RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, RightLargest)
    else if LeftLargest.Max < thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, null)
    else if RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(null, thisNode.Value, RightLargest)
    else
        currentBestTree = new BinaryTree(null, thisNode.Value, null)
    if (currentBestTree.Size > OverallBestTree.Size)
        OverallBestTree = currentBestTree
    return currentBestTree

Como BlueRaja señaló, este algoritmo no es correcta.

Debe realmente ser llamado GetLargestSortedBinarySubtreeThatCanBeRecursivelyConstructedFromMaximalSortedSubtrees.

root(Tree L A R) = A

MaxBST(NULL) = (true, 0, NULL)
MaxBST(Tree L A R as T) = 
  let
    # Look at both children
    (L_is_BST, L_size, L_sub) = MaxBST(L)
    (R_is_BST, R_size, R_sub) = MaxBST(R)
  in
  # If they're both good, then this node might be good too
  if L_is_BST and R_is_BST and (L == NULL or root(L) < A) and (R == NULL or A < root(R))
  then (true, 1 + L_size + R_size, T)
  else
       # This node is no good, so give back the best our children had to offer
       (false, max(L_size, R_size), if L_size > R_size then L_sub else R_sub)

mira a cada nodo del árbol exactamente una vez, por lo que se ejecuta en O (N).

Editar: Crud, esto no tiene en cuenta que puede dejar de lado algunas partes de un sub-árbol. Cuando leí subárbol, asumí "todo el árbol con raíces en algún nodo". Si vuelvo a arreglar esto más adelante.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow