Рекурсивно получить подмножество двоичного дерева поиска - PullRequest
Новая
       28

Рекурсивно получить подмножество двоичного дерева поиска

0 голосов
/ 19 ноября 2018

Для бинарного объекта дерева я реализую с закрытыми полями 

X key;
Y value;
Tree<X,Y> left;
Tree<X,Y> right;

У меня есть метод public Tree<X,Y> subset(X startKey, X endKey), который должен возвращать дерево, включая все ключи между узлом с startKey и узлом с endKey, и их соответствующие значения. Этот метод также должен быть выполнен с использованием рекурсии.

Проблема, с которой я сталкиваюсь, заключается в том, что я не могу найти способ получить дерево (которое, вероятно, будет выглядеть как LinkedList), которое заканчивается на endKey, без учета endKey.left и endKey.right. Я решил начать с рекурсивного вызова метода в левом или правом дереве корня в зависимости от того, больше или меньше startKey корневого ключа, поэтому: 

if (this.key.compareTo(startKey) < 0) this.right.subset(startKey, endKey);
else if (this.key.compareTo(startKey > 0) this.right.subset(startKey, endKey);

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

Вот где я застрял. Я знаю, что мне придется столкнуться с проблемами, связанными с переходом на endKey, в котором я остановлюсь и не включу endKey.left или endKey.right и верну правильное подмножество, даже если метод "раскручивается" из рекурсивные вызовы. Я думаю, что если я хочу остановиться на endKey, мне придется каким-то образом сохранить ссылку на его родительский узел, чтобы я мог установить левый или правый дочерний узел родительского узла на пару ключ / значение, чтобы отрезать остальных детей endKey. Однако, поскольку у меня на самом деле нет объектов узлов, и я не могу добавить какие-либо методы или конструкторы, я не знаю, как я смогу поддерживать ссылку на родительское дерево. Я также не знаю, как попытаться осуществить это, сохранив startKey в качестве корня нового дерева.

Другими словами, я думаю, что мне удалось получить подмножество дерева, которое начинается на более низком уровне и продолжается до основания исходного дерева. Как я могу рекурсивно удалить ненужных детей в нижней части и вернуть мое новое подмножество?

1 Ответ

0 голосов
/ 20 ноября 2018

Если вы рассматриваете это как представление, которое на самом деле не вырезано, вы просто ограничиваете методы диапазоном подмножества. При использовании iterator() например у подкарты просто есть собственная реализация Iterator, которая начинается с нижней границы подкарты и просто возвращает hasNext() == false при достижении верхней границы. Пользователь не заметит, что он фактически перебирает исходное дерево, потому что оно полностью скрыто. Я надеюсь, что этот пример дает вам представление об этом. 

public interface Tree<X, Y> extends Iterable<Tree<X, Y>> {
    X getKey();
    X getValue();
    Tree<X, Y> floor(X key);
    Tree<X, Y> ceiling(X key);
    Tree<X, Y> subTree(X lo, X hi);
    // ...
}

public class TreeImpl<X, Y> implements Tree<X, Y> {
    final X key;
    Y value;
    TreeImpl<X, Y> left, right;

    public TreeImpl(X key, Y value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public Iterator<Tree<X, Y>> iterator() {
        return new TreeItr();
    }

    // Iterator starting at the most left to the most right;
    private class TreeItr implements Iterator<Tree<X, Y>> {
        // ...
    }

    @Override
    public Tree<X, Y> subTree(X lo, X hi) {
        return new SubTree<>(this, lo, hi);
    }

    private static class SubTree<X, Y> implements Tree<X, Y> {
        final Tree<X, Y> backing;
        final X lo, hi;

        public SubTree(Tree<X, Y> backing, X lo, X hi) {
            this.backing = backing;
            this.lo = lo;
            this.hi = hi;
        }

        @Override
        public Iterator<Tree<X, Y>> iterator() {
            return new SubTreeItr(backing.ceiling(lo), backing.floor(hi))
        }

        // Iterator starting at 'from' and returning 'hasNext() == false' after 'to'
        // has returned
        private class SubTreeItr implements Iterator<Tree<X, Y>> {
            final Tree<X, Y> from, to;

            public SubTreeItr(Tree<X, Y> from, Tree<X, Y> to) {
                this.from = from;
                this.to = to;
            }

            //...
        }

        @Override
        public Tree<X, Y> subTree(X lo, X hi) {
            // Check if lo > this.lo && hi < this.hi
            return new SubTree<>(backing, lo, hi);
        }
    }
}
...