Реализация итератора над бинарным деревом поиска

Question

Недавно я кодировал кучу различных реализаций бинарного дерева поиска (AVL, splay, treap), и мне любопытно, есть ли особенно «хороший» способ написать итератор для обхода этих структур.Решение, которое я использовал прямо сейчас, состоит в том, чтобы каждый узел в BST сохранял указатели на следующий и предыдущий элементы в дереве, что сводит итерацию к стандартной итерации связанного списка.Однако я не очень доволен этим ответом.Это увеличивает использование пространства каждого узла на два указателя (следующий и предыдущий), и в некотором смысле это просто обман.

Я знаю способ создания итератора бинарного дерева поиска, который использует O (h) вспомогательныйпространство для хранения (где h - высота дерева) с помощью стека для отслеживания пограничных узлов для дальнейшего изучения, но я не стал кодировать это из-за использования памяти.Я надеялся, что есть какой-то способ построить итератор, который использует только постоянное пространство.

Мой вопрос такой: есть ли способ создать итератор для двоичного дерева поиска со следующими свойствами?

1. Элементы посещаются в порядке возрастания (т. Е. Обход по порядку)
2. next() и hasNext() запросы выполняются за O (1) раз.
3. Использование памяти равно O (1)

Чтобы было проще, хорошо, если вы предполагаете, что древовидная структура не меняет форму во время итерации (т.е. нет вставок, удалений или поворотов), но это было бы действительно здоровоесли бы было решение, которое действительно могло бы справиться с этим.

Answer 1

Простейший из возможных итераторов сохраняет последний увиденный ключ, а затем на следующей итерации ищет в дереве наименее верхнюю границу для этого ключа.Итерация O (log n).Это имеет преимущество в простоте.Если ключи маленькие, итераторы тоже маленькие.Конечно, его недостатком является относительно медленный способ итерации по дереву.Это также не будет работать для неуникальных последовательностей.

Некоторые деревья используют именно ту реализацию, которую вы уже используете, потому что для их конкретного использования важно, чтобы сканирование было очень быстрым.Если количество ключей в каждом узле велико, то наказание за хранение указателей на одноуровневый элемент не слишком обременительно.Большинство B-деревьев используют этот метод.

Многие реализации дерева поиска сохраняют родительский указатель на каждом узле, чтобы упростить другие операции.Если у вас есть это, то вы можете использовать простой указатель на последний увиденный узел в качестве состояния вашего итератора.на каждой итерации вы ищите следующего потомка в родительском узле последнего увиденного.если братьев и сестер больше нет, вы переходите на еще один уровень.

Если ни один из этих методов вам не подходит, вы можете использовать стек узлов, сохраненный в итераторе.Это выполняет ту же функцию, что и стек вызовов функций, когда выполняется итерация по дереву поиска в обычном режиме, но вместо того, чтобы циклически проходить по дочерним элементам и рекурсировать дочерние элементы, вы помещаете дочерние элементы в стек и возвращаете каждого последующего одноуровневого элемента.

Answer 2

Как упомянул TokenMacGuy, вы можете использовать стек, хранящийся в итераторе. Вот быстрая проверенная реализация этого в 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);
    }
}

Другим вариантом может быть обход дерева во время строительства и сохранение обхода в списке. После этого вы можете использовать итератор списка.

Answer 3

Хорошо, я знаю, что это старый, но меня спросили об этом в интервью с Microsoft некоторое время назад, и я решил немного поработать над этим.Я проверил это, и это работает довольно хорошо.

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

Обход дерева , из Википедии:

Для всех примеров реализации потребуется пространство стека вызовов, пропорциональное высоте дерева. В плохо сбалансированном дереве это может быть довольно значительным.

Мы можем отменить требование стека, поддерживая родительские указатели в каждом узле или создавая потоки в дереве. В случае использования потоков это позволит значительно улучшить обход по порядку, хотя получение родительского узла, необходимого для обхода по предварительному заказу и после заказа, будет медленнее, чем простой алгоритм на основе стека.

В статье есть некоторый псевдокод для итерации с состоянием O (1), который можно легко адаптировать к итератору.

Answer 5

По определению, next () и hasNext () не могут быть запущены за O (1) раз.Когда вы смотрите на конкретный узел в BST, вы не имеете представления о высоте и структуре других узлов, поэтому вы не можете просто «перейти» к правильному следующему узлу.

Однако пространствосложность может быть уменьшена до O (1) (за исключением памяти для самого BST).Вот способ, которым я бы сделал это в 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;
}

Хитрость заключается в том, чтобы иметь и родительскую ссылку, и флаг посещения для каждого узла.По моему мнению, мы можем утверждать, что это не дополнительное использование пространства, это просто часть структуры узла.И очевидно, что iter_next () должен вызываться без изменения состояния древовидной структуры (конечно), но также и то, что флаги «посещения» не меняют значений.

Вот функция тестера, которая вызывает iter_next) и печатает значение каждый раз для этого дерева:

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

, которое будет печатать значения в отсортированном порядке:

15 16 20 21 25 27 40 62 71 

Answer 6

Используйте пробел O (1), что означает, что мы не будем использовать стек O (h).

Для начала:

1. hasNext ()?current.val <= endNode.val, чтобы проверить, является ли дерево полностью пройденным. </p>

2. Найти мин по крайнему левому краю: мы можем всегда искать крайний левый, чтобы найти следующее минимальное значение.

3. Как только проверяется крайний левый мин (назовите его current).Следующая минута будет в 2 случаях: Если current.right! = Null, мы можем продолжить поиск самого левого потомка current.right, как в следующую минуту.Или нам нужно оглянуться назад на родителя.Используйте двоичное дерево поиска, чтобы найти текущий родительский узел.

Примечание : при выполнении двоичного поиска для родителя убедитесь, что он удовлетворяет parent.left = current.

Потому что: если parent.right == текущий, этот родитель должен был быть ранее.В бинарном дереве поиска мы знаем, что parent.val

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 7

Если вы используете стек, вы получаете только «Использование дополнительной памяти O (h), h - высота дерева»).Однако, если вы хотите использовать только O (1) дополнительной памяти, вам необходимо записать следующий анализ: - Если у текущего узла есть правильный дочерний элемент: найдите минимум правого поддерева - Если у текущего узла нет правого дочернего элемента, вам нужноискать его из корня и постоянно обновлять его самого нижнего предка, который является его самым низким следующим узлом

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 8

А как насчет использования техники поиска в глубину?Объект итератора просто должен иметь стек уже посещенных узлов.