Eliminar la secuencia ordenada de números de BST

Question

Tuve esta pregunta durante un examen y no pude encontrar una respuesta rápida.

Hay una matriz A que contiene algunos números ordenados A = [1,3,6,9,11] y una BST con números como clave. Tengo que proporcionar un algoritmo recursivo eficiente para eliminar los números en A de la BST.

El problema que tengo no está en eliminar los nodos, sino en cómo usar el hecho de que la matriz se ordena al eliminar los nodos.

¿Alguien me puede ayudar con algunas pistas?

Answer 1

Aquí hay un posible enfoque.

Puede recorrer simultáneamente la BST (utilizando standard recursive algorithm) y A (de izquierda a derecha). Cada uno de los recorridos arrojará elementos en orden creciente. Está buscando elementos coincidentes para eliminarlos del árbol.

Un algoritmo ingenuo tendrá O(size(BST)) complejidad de tiempo.

En algunos casos puede evitar mirar completamente el subárbol izquierdo: el valor del nodo "actual" en el árbol le da un límite superior en los valores en el subárbol izquierdo, por lo que si es menor que el valor de el elemento "actual" de A, omita el subárbol izquierdo.

También puede detener el algoritmo tan pronto como haya agotado A.

Answer 2

Deje que una BST se represente por su nodo raíz.

La función delete-array-from-bst con argumentos array y bst es:

• si el array o la bst está vacía: volver
• dividir la matriz en tres subconjuntos, los valores más pequeño, igual, y más grande que la bst 'valor de nodo raíz
• recurse en el subcampo con los valores más pequeños con la izquierda sub-BST, luego en el subcampo con los valores más grandes en la derecha sub-BST, finalmente elimine el valor igual, si se aplica cable

La división de la matriz es una búsqueda binaria, por lo que no es necesario comparar cada valor de la matriz con el nodo raíz. Los subcampos pueden compartir la estructura con la matriz original. Eliminar por última vez el valor igual garantiza que no se pulse el peor caso de eliminación para cada valor en la matriz.