Implementazione di un iteratore su un albero di ricerca binario

Question

Ho iniziato a codificare un sacco di diverse implementazioni di binari di ricerca di recente (AVL, splay, treap) e sono curioso di sapere se c'è un modo particolarmente "buono" di scrivere un iteratore per attraversare queste strutture. La soluzione che ho usato in questo momento è quella di fare in modo che ogni nodo nel BST memorizzi i puntatori agli elementi successivi e precedenti nella struttura, riducendo l'iterazione a un'iterazione di elenchi concatenati standard. Tuttavia, non sono davvero soddisfatto di questa risposta. Aumenta l'utilizzo dello spazio di ogni nodo di due puntatori (successivo e precedente), e in un certo senso è solo imbroglio.

Conosco un modo di costruire un iteratore di un albero di ricerca binario che utilizza lo spazio di memoria ausiliaria O (h) (dove h è l'altezza dell'albero) usando una pila per tenere traccia dei nodi di frontiera da esplorare in seguito , ma ho resistito alla codifica di questo a causa dell'uso della memoria. Speravo ci fosse un modo per costruire un iteratore che utilizza solo lo spazio costante.

La mia domanda è questa: c'è un modo per progettare un iteratore su un albero di ricerca binario con le seguenti proprietà?

1. elementi sono visitati in ordine ascendente (cioè un attraversamento in ordine simmetrico)
2. next() e hasNext() query eseguite in O (1) tempo.
3. utilizzo della memoria è O (1)

Per rendere più facile, va bene se si assume che la struttura ad albero non cambia forma durante l'iterazione (cioè senza inserzioni, delezioni o rotazioni), ma sarebbe davvero bello se esistesse una soluzione che potesse davvero gestirlo.

Answer 1

L'iteratore più semplice possibile memorizza l'ultima chiave visualizzata e quindi alla successiva iterazione, cerca nell'albero il limite superiore minimo per quella chiave. Iterazione è O (log n). Questo ha il vantaggio di essere molto semplice. Se le chiavi sono piccole, anche gli iteratori sono piccoli. ovviamente ha lo svantaggio di essere un modo relativamente lento di iterare attraverso l'albero. Inoltre non funzionerà per sequenze non univoche.

Alcuni alberi usano esattamente l'implementazione che già usi, perché è importante per il loro uso specifico che la scansione sia molto veloce. Se il numero di chiavi in ​​ogni nodo è grande, la penalità di memorizzazione dei puntatori di pari livello non è troppo onerosa. La maggior parte degli alberi B usa questo metodo.

molte implementazioni di albero di ricerca mantengono un puntatore padre su ciascun nodo per semplificare altre operazioni. In tal caso, puoi utilizzare un semplice puntatore all'ultimo nodo visto come stato del tuo iteratore. ad ogni iterazione, si cerca il prossimo figlio nel genitore dell'ultimo nodo visto. se non ci sono più fratelli, salirai su un altro livello.

Se nessuna di queste tecniche è adatta a voi, è possibile utilizzare una pila di nodi, memorizzati nell'iteratore. Questa funzione ha la stessa funzione dello stack di chiamate di funzioni quando si esegue iterazione normale attraverso l'albero di ricerca, ma invece di eseguire il ciclo tra fratelli e ricorsivi sui bambini, si spinge i bambini nello stack e si restituiscono ogni fratello successivo.

Answer 2

Tree traversal, da Wikipedia:

Tutte le implementazioni di esempio richiederanno chiamata spazio di stack proporzionale all'altezza dell'albero. In un albero scarsamente bilanciato, questo può essere abbastanza considerevole.

Siamo in grado di rimuovere il requisito dello stack mantenendo i puntatori padre in ciascun nodo o eseguendo il threading dell'albero. Nel caso dell'utilizzo di thread, ciò consentirà un traversal inorder notevolmente migliorato, sebbene il recupero del nodo genitore richiesto per l'attraversamento preorder e postorder sarà più lento di un semplice algoritmo basato su stack.

Nell'articolo è presente uno pseudocodice per l'iterazione con stato O (1), che può essere facilmente adattato a un iteratore.

Answer 3

Ok, so che questo è vecchio, ma mi è stato chiesto questo in un'intervista con Microsoft qualche tempo fa e ho deciso di lavorarci un po '. Ho provato questo e funziona abbastanza bene.

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 4

Come menzionato da TokenMacGuy, è possibile utilizzare uno stack memorizzato nell'iteratore. Ecco un'implementazione rapida testato di questo in 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); 
    } 
} 

Altro variante potrebbe essere quella di attraversare l'albero in fase di costruzione e salvare l'attraversamento in una lista. È possibile utilizzare l'elenco iteratore in seguito.

Answer 5

Informazioni sull'utilizzo di una tecnica di ricerca di prima profondità. L'oggetto iteratore deve semplicemente avere uno stack dei nodi già visitati.

Answer 6

Se si utilizza lo stack, si ottiene solo "Utilizzo memoria extra O (h), h è l'altezza dell'albero". Tuttavia, se si desidera utilizzare solo la memoria aggiuntiva O (1), è necessario registrare lo . Ecco l'analisi: - Se il nodo corrente ha il figlio destro: trova il min dell'albero secondario destro - Il nodo corrente non ha diritto bambino, è necessario guardare per esso dalla radice, e mantenere l'aggiornamento è antenato più basso, che è il suo nodo più basso accanto

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

usa O (1) spazio, il che significa che non useremo O (h) dello stack .

Per iniziare:

1. hasNext()? current.val < = endNode.val per verificare se l'albero è completamente attraversato.

2. Trova min via più a sinistra: possiamo sempre cercare il più a sinistra per trovare il prossimo valore minimo.

3. Una volta lasciato il più-min è selezionato (denominarlo current). Il prossimo minuto sarà di 2 casi: Se current.right! = Null, possiamo continuare a cercare il figlio più a sinistra di current.right, come il prossimo minuto. Oppure, dobbiamo guardare indietro per genitore. Usa la struttura di ricerca binaria per trovare il nodo genitore corrente.

Nota: quando si fa ricerca binaria per il genitore, assicurarsi che soddisfi parent.left = corrente.

Perché: se parent.right == corrente, quel genitore deve essere stato visitato prima. Nell'albero di ricerca binario, , sappiamo che parent.val < parent.right.val. Dobbiamo saltare questo caso speciale, poiché porta al ciclo 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

Per definizione, non è possibile per il prossimo() e hasNext() per l'esecuzione in O (1) tempo.Quando si guarda un particolare nodo in un BST, non si ha idea dell'altezza e della struttura degli altri nodi, quindi non si può semplicemente "saltare" al nodo successivo corretto.

Tuttavia, la complessità dello spazio può essere ridotta a O (1) (tranne che per la memoria per il BST stesso). Qui è il modo in cui lo farei in 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; 
} 

Il trucco è quello di avere sia un legame genitore, e una bandiera visitato per ogni nodo. A mio parere, possiamo sostenere che non si tratta di un utilizzo dello spazio aggiuntivo, è semplicemente parte della struttura del nodo. E ovviamente, iter_next() deve essere chiamato senza che lo stato della struttura ad albero cambi (ovviamente), ma anche che i flag "visitati" non cambino i valori.

Ecco la funzione di tester che iter_next() chiama e stampa il valore ogni volta per questo albero:

    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; 
} 

che stamperà i valori in modo ordinato:

15 16 20 21 25 27 40 62 71