Подтвердить что ты не робот

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

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

Ответ 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);
    }
}

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

Ответ 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;
    }

};

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

Для начала:

  • hasNext()? current.val <= endNode.val, чтобы проверить, полностью ли перемещено дерево.

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

  • Как только проверяется самый последний мин (name it current). Следующий мин будет 2 случая: Если current.right!= Null, мы можем продолжать искать current.right left-most child, как следующий min. Или нам нужно посмотреть назад для родителя. Используйте двоичное дерево поиска, чтобы найти текущий родительский node.

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

Потому что: Если parent.right == current, этот родитель должен был ранее. В двоичном дереве поиска, мы знаем, что parent.val < parent.right.val. Нам нужно пропустить этот частный случай, поскольку он ведет в цикл 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 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;
    }
}

Ответ 8

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

Однако сложность пространства может быть сведена к 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;
}

Фокус в том, чтобы иметь как родительскую ссылку, так и флаг посещения для каждого node. На мой взгляд, мы можем утверждать, что это не дополнительное использование пространства, это просто часть структуры 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