algorithm - programar - arboles binarios de busqueda

Implementando un iterador sobre un árbol de búsqueda binario

Question

Recientemente he estado codificando un conjunto de diferentes implementaciones de árbol de búsqueda binaria (AVL, splay, treap) y tengo curiosidad por saber si hay una forma particularmente "buena" de escribir un iterador para recorrer estas estructuras. La solución que he usado ahora es tener cada nodo en los punteros de la tienda BST a los elementos siguientes y anteriores en el árbol, lo que reduce la iteración a una iteración de la lista enlazada estándar. Sin embargo, no estoy realmente satisfecho con esta respuesta. Aumenta el uso del espacio de cada nodo mediante dos punteros (siguiente y anterior), y en cierto sentido es solo hacer trampa.

Conozco una forma de construir un iterador binario de árbol de búsqueda que usa O (h) espacio de almacenamiento auxiliar (donde h es la altura del árbol) utilizando una pila para realizar un seguimiento de los nodos fronterizos para explorar más adelante, pero I '' Me he resistido a codificar esto debido al uso de la memoria. Esperaba que hubiera alguna forma de construir un iterador que usara solo espacio constante.

Mi pregunta es esta: ¿hay alguna manera de diseñar un iterador sobre un árbol de búsqueda binario con las siguientes propiedades?

1. Los elementos se visitan en orden ascendente (es decir, un recorrido transversal del orden)
2. next() y hasNext() ejecutan en O (1) hora.
3. El uso de la memoria es O (1)

Para hacerlo más fácil, está bien si asumes que la estructura del árbol no está cambiando de forma durante la iteración (es decir, sin inserciones, eliminaciones o rotaciones), pero sería genial si hubiera una solución que realmente pudiera manejar esto.

Answer 1

¿Qué hay de usar una primera técnica de búsqueda de profundidad? El objeto iterador solo debe tener una pila de nodos ya visitados.

Answer 2

Como mencionó TokenMacGuy, puede usar una pila almacenada en el iterador. Aquí hay una implementación probada rápida de esto en Java:

/**
 * An iterator that iterates through a tree using in-order tree traversal
 * allowing a sorted sequence.
 *
 */
public class Iterator {

    private Stack<Node> stack = new Stack<>();
    private Node current;

    private Iterator(Node argRoot) {
        current = argRoot;
    }

    public Node next() {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        Node node = current;
        current = current.right;

        return node;
    }

    public boolean hasNext() {
        return (!stack.isEmpty() || current != null);
    }

    public static Iterator iterator(Node root) {
        return new Iterator(root);
    }
}

Otra variación sería atravesar el árbol en el momento de la construcción y guardar el recorrido en una lista. Puede usar el iterador de lista luego.

Answer 3

El iterador más simple posible almacena la última clave vista, y luego en la siguiente iteración, busca en el árbol el límite superior mínimo para esa clave. La iteración es O (log n). Esto tiene la ventaja de ser muy simple. Si las teclas son pequeñas, los iteradores también son pequeños. Por supuesto, tiene la desventaja de ser una forma relativamente lenta de iterar a través del árbol. Tampoco funcionará para secuencias no únicas.

Algunos árboles usan exactamente la implementación que ya usa, porque para su uso específico es importante que el escaneo sea muy rápido. Si el número de claves en cada nodo es grande, entonces la penalización de almacenar punteros hermanos no es demasiado onerosa. La mayoría de los B-Trees usan este método.

muchas implementaciones de árbol de búsqueda mantienen un puntero principal en cada nodo para simplificar otras operaciones. Si tiene eso, entonces puede usar un puntero simple al último nodo visto como el estado de su iterador. en cada iteración, busca el siguiente elemento secundario en el padre del último nodo visto. si no hay más hermanos, entonces subes un nivel más.

Si ninguna de estas técnicas le conviene, puede usar una pila de nodos, almacenados en el iterador. Esto cumple la misma función que la pila de llamadas a funciones cuando se itera a través del árbol de búsqueda de forma normal, pero en lugar de pasar a través de los hermanos y recurrir a los niños, empuja a los niños a la pila y devuelve cada uno de los hermanos sucesivos.

Answer 4

Ok, sé que esto es viejo, pero me preguntaron esto en una entrevista con Microsoft hace un tiempo y decidí trabajar en ello un poco. Lo he probado y funciona bastante bien.

template <typename E>
class BSTIterator
{  
  BSTNode<E> * m_curNode;
  std::stack<BSTNode<E>*> m_recurseIter;

public:
    BSTIterator( BSTNode<E> * binTree )
    {       
        BSTNode<E>* root = binTree;

        while(root != NULL)
        {
            m_recurseIter.push(root);
            root = root->GetLeft();
        }

        if(m_recurseIter.size() > 0)
        {
            m_curNode = m_recurseIter.top();
            m_recurseIter.pop();
        }
        else
            m_curNode = NULL;
    }

    BSTNode<E> & operator*() { return *m_curNode; }

    bool operator==(const BSTIterator<E>& other)
    {
        return m_curNode == other.m_curNode;
    }

    bool operator!=(const BSTIterator<E>& other)
    {
        return !(*this == other);
    }

    BSTIterator<E> & operator++() 
    { 
        if(m_curNode->GetRight())
        {
            m_recurseIter.push(m_curNode->GetRight());

            if(m_curNode->GetRight()->GetLeft())
                m_recurseIter.push(m_curNode->GetRight()->GetLeft());
        }

        if( m_recurseIter.size() == 0)
        {
            m_curNode = NULL;
            return *this;
        }       

        m_curNode = m_recurseIter.top();
        m_recurseIter.pop();

        return *this;       
    }

    BSTIterator<E> operator++ ( int )
    {
        BSTIterator<E> cpy = *this;     

        if(m_curNode->GetRight())
        {
            m_recurseIter.push(m_curNode->GetRight());

            if(m_curNode->GetRight()->GetLeft())
                m_recurseIter.push(m_curNode->GetRight()->GetLeft());
        }

        if( m_recurseIter.size() == 0)
        {
            m_curNode = NULL;
            return *this;
        }       

        m_curNode = m_recurseIter.top();
        m_recurseIter.pop();

        return cpy;
    }

};

Answer 5

Por definición, no es posible que next () y hasNext () se ejecuten en O (1) tiempo. Cuando mira un nodo particular en una BST, no tiene idea de la altura y la estructura de los otros nodos, por lo tanto, no puede simplemente "saltar" al siguiente nodo correcto.

Sin embargo, la complejidad del espacio puede reducirse a O (1) (a excepción de la memoria para el BST mismo). Esta es la manera en que lo haría en C:

struct node{
    int value;
    struct node *left, *right, *parent;
    int visited;
};

struct node* iter_next(struct node* node){
    struct node* rightResult = NULL;

    if(node==NULL)
        return NULL;

    while(node->left && !(node->left->visited))
        node = node->left;

    if(!(node->visited))
        return node;

    //move right
    rightResult = iter_next(node->right);

    if(rightResult)
        return rightResult;

    while(node && node->visited)
        node = node->parent;

    return node;
}

El truco es tener un enlace padre y un indicador visitado para cada nodo. En mi opinión, podemos argumentar que esto no es un uso de espacio adicional, simplemente es parte de la estructura del nodo. Y obviamente, iter_next () debe invocarse sin cambiar el estado de la estructura de árbol (por supuesto), pero también que los indicadores "visitados" no cambian los valores.

Aquí está la función del probador que llama a iter_next () e imprime el valor cada vez para este árbol:

                  27
               /      /
              20      62
             /  /    /  /
            15  25  40  71
             /  /
             16 21

int main(){

    //right root subtree
    struct node node40 = {40, NULL, NULL, NULL, 0};
    struct node node71 = {71, NULL, NULL, NULL, 0};
    struct node node62 = {62, &node40, &node71, NULL, 0};

    //left root subtree
    struct node node16 = {16, NULL, NULL, NULL, 0};
    struct node node21 = {21, NULL, NULL, NULL, 0};
    struct node node15 = {15, NULL, &node16, NULL, 0};
    struct node node25 = {25, &node21, NULL, NULL, 0};
    struct node node20 = {20, &node15, &node25, NULL, 0};

    //root
    struct node node27 = {27, &node20, &node62, NULL, 0};

    //set parents
    node16.parent = &node15;
    node21.parent = &node25;
    node15.parent = &node20;
    node25.parent = &node20;
    node20.parent = &node27;
    node40.parent = &node62;
    node71.parent = &node62;
    node62.parent = &node27;

    struct node *iter_node = &node27;

    while((iter_node = iter_next(iter_node)) != NULL){
        printf("%d ", iter_node->value);
        iter_node->visited = 1;
    }
    printf("/n");
    return 1;
}

Que imprimirá los valores en orden ordenado:

15 16 20 21 25 27 40 62 71 

Answer 6

Si usa la pila, solo logrará "Uso de memoria extra O (h), h es la altura del árbol". Sin embargo, si solo desea utilizar O (1) memoria adicional, debe registrar el siguiente: Aquí está el análisis: - Si el nodo actual tiene el hijo derecho: encuentre el mínimo del subárbol derecho - El nodo actual no tiene el hijo correcto, necesita buscarlo desde la raíz, y seguir actualizando su ancestro más bajo, que es el siguiente nodo más bajo

public class Solution {
           //@param root: The root of binary tree.

           TreeNode current;
           TreeNode root;
           TreeNode rightMost;
           public Solution(TreeNode root) {

               if(root==null) return;
                this.root = root;
                current = findMin(root);
                rightMost = findMax(root);
           }

           //@return: True if there has next node, or false
           public boolean hasNext() {

           if(current!=null && rightMost!=null && current.val<=rightMost.val)    return true; 
        else return false;
           }
           //O(1) memory.
           public TreeNode next() {
                //1. if current has right child: find min of right sub tree
                TreeNode tep = current;
                current = updateNext();
                return tep;
            }
            public TreeNode updateNext(){
                if(!hasNext()) return null;
                 if(current.right!=null) return findMin(current.right);
                //2. current has no right child
                //if cur < root , go left; otherwise, go right

                    int curVal = current.val;
                    TreeNode post = null;
                    TreeNode tepRoot = root;
                    while(tepRoot!=null){
                      if(curVal<tepRoot.val){
                          post = tepRoot;
                          tepRoot = tepRoot.left;
                      }else if(curVal>tepRoot.val){
                          tepRoot = tepRoot.right;
                      }else {
                          current = post;
                          break;
                      }
                    }
                    return post;

            }

           public TreeNode findMin(TreeNode node){
               while(node.left!=null){
                   node = node.left;
               }
               return node;
           }

            public TreeNode findMax(TreeNode node){
               while(node.right!=null){
                   node = node.right;
               }
               return node;
           }
       }

Answer 7

Use O (1) espacio, lo que significa que no usaremos O (h) pila.

Empezar:

1. hasNext ()? current.val <= endNode.val para verificar si el árbol está completamente atravesado.

2. Encuentre el mínimo a través del extremo izquierdo: siempre podemos buscar el extremo izquierdo para encontrar el siguiente valor mínimo.

3. Una vez que se marque el mínimo a la izquierda, nómbrelo como current . El próximo mínimo será de 2 casos: si current.right! = Null, podemos seguir buscando el hijo más a la izquierda de current.right, como el siguiente mínimo. O bien, tenemos que mirar hacia atrás para ver a los padres. Utilice el árbol de búsqueda binaria para encontrar el nodo primario de la corriente.

Nota : al hacer una búsqueda binaria para el elemento primario, asegúrese de que satisface parent.left = current.

Porque: si parent.right == current, ese padre debe haber sido visitado anteriormente. En el árbol de búsqueda binaria, sabemos que parent.val <parent.right.val. Necesitamos saltear este caso especial, ya que conduce al bucle ifinite.

public class BSTIterator {
    public TreeNode root;
    public TreeNode current;
    public TreeNode endNode;
    //@param root: The root of binary tree.
    public BSTIterator(TreeNode root) {
        if (root == null) {
            return;
        }
        this.root = root;
        this.current = root;
        this.endNode = root;

        while (endNode != null && endNode.right != null) {
            endNode = endNode.right;
        }
        while (current != null && current.left != null) {
            current = current.left;
        }
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return current != null && current.val <= endNode.val;
    }

    //@return: return next node
    public TreeNode next() {
        TreeNode rst = current;
        //current node has right child
        if (current.right != null) {
            current = current.right;
            while (current.left != null) {
                current = current.left;
            }
        } else {//Current node does not have right child.
            current = findParent();
        }
        return rst;
    }

    //Find current''s parent, where parent.left == current.
    public TreeNode findParent(){
        TreeNode node = root;
        TreeNode parent = null;
        int val = current.val;
        if (val == endNode.val) {
            return null;
        }
        while (node != null) {
            if (val < node.val) {
                parent = node;
                node = node.left;
            } else if (val > node.val) {
                node = node.right;
            } else {//node.val == current.val
                break;
            }
        }
        return parent;
    }
}

Answer 8

Travesía de árboles , de Wikipedia:

Todas las implementaciones de muestra requerirán un espacio de pila de llamadas proporcional a la altura del árbol. En un árbol pobremente equilibrado, esto puede ser bastante considerable.

Podemos eliminar el requisito de pila manteniendo los punteros principales en cada nodo, o enlazando el árbol. En el caso de utilizar subprocesos, esto permitirá una mejora en el recorrido inorden, aunque la recuperación del nodo principal requerido para el recorrido de preorden y postorder será más lento que un algoritmo simple basado en la pila.

En el artículo hay algún pseudocódigo para iteración con estado O (1), que se puede adaptar fácilmente a un iterador.