Wednesday 30 June 2010

Обход бинарного дерева с константным количеством памяти.

Как-то раз, будучи на собеседование, меня гоняли по структурам данных, в частности по бинарным деревьям. Как любитель функциональщины, я всё рассказывал на рекурсивных алгоритмах, что, в конце концов, вызвало вопрос, как обойти дерево без рекурсии. После описания простейшего кода со стеком, спросили, а можно ли без стека, без динамической памяти, и я, после минуты раздумья, ответил нет. Точную реакцию интервьюера я не помню, но кажется он согласился. Спустя где-то пол года наткнулся где-то в жж на замечание о том, что это возможно, и как итог, придумал решение.

Задача:
Есть произвольное бинарное дерево описание которого содержит ссылку на левый, правый потомок и значение в вершине. Необходимо обойти все вершины дерева используя фиксированное количество памяти.

Рассуждения:
Для того, что бы обойти бинарное дерево, необходимо где-то хранить данные о тех ветвлениях, по которым мы ходили только в одну сторону. Реализовать это хранение в фиксированном количестве памяти для произвольного дерева невозможно, следовательно необходимо где-то найти память.
На самом деле, если присмотреться, к нашему дереву более внимательно, то можно найти огромное количество памяти, которое хранится в ветках с одним потомком и листьях (речь идёт о нулевых ссылках). В принципе, ничего нам не мешает редактировать дерево, если мы сможем вернуть всё на место. Это можно сделать следующим образом:

  • Создаём указатель на голову нашего импровизированного списка вершин в которых мы не были. 
  • В случае, если мы попадаем на развилку, то добавляем в этот список ещё один элемент, в котором отмечаем текущую вершину. Память для нового элемента списка находим в правой ветке, а сами переходим в левую.
  • В случае, если мы попадаем в листок, то смотрим не пуст ли наш список, если это так, то откусываем первый элемент (последняя развилка), и останавливаем нулевые указатели. Переходим конечно в правую ветку относительно последней развилки.
Вот два варианта реализации на языке salltalk и java (если кто-то может попинать меня за стиль кодирования, прошу это сделать, так как сейчас учу этот язык). Проверка корректности производится при помощи использования свёрток, в данном случае свёртка суммы.


Код на Java для узла:


public class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left, right;
    public Node(T value) {
        this.value = value;
    }
    public void add(T value) {
        if (left == null) {
            left = new Node<T>(value);
            return;
        }
        if (right == null) {
            right = new Node<T>(value);
            return;
        }
        if (left.getSize() < right.getSize()) {
            left.add(value);
        } else {
            right.add(value);
        }
    }
    public void addSort(T value) {
        if (this.value.compareTo(value) == -1) {
            if (left == null) {
                left = new Node<T>(value);
            } else {
                left.addSort(value);
            }
        } else {
            if (right == null) {
                right = new Node<T>(value);
            } else {
                right.addSort(value);
            }
        }
    }
    public int getSize() {
        return 1 + (left == null ? 0 : left.getSize())
                + (right == null ? 0 : right.getSize());
    }
    public Node<T> getNext() {
        if (!(right == null)) return right;
        if (!(left == null)) return left;
        return null;
    }
    public boolean isNormalBranch() {
        if (left == null && right != null) return true;
        if (left != null && right == null) return true;
        return false;
    }
    public boolean isLeaf(){
        return left == null && right == null;
    }
    public Node<T> getLeft() {
        return left;
    }
    public void setLeft(Node<T> left) {
        this.left = left;
    }
    public Node<T> getRight() {
        return right;
    }
    public void setRight(Node<T> right) {
        this.right = right;
    }
    public T getValue() {
        return value;
    }
}

Код на Java для корня, в котором и реализован алгоритм:


import java.util.*;
interface Callable<T1, T2> {
        public T1 call(T1 acc, T2 e);
        }
public class Root<T extends Comparable<T>> {
    private Node<T> root;
    public Root() {
    }
    public int getSize() {
        return root.getSize();
    }
    public void add(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.add(value);
        }
    }
    public void addSort(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.addSort(value);
        }
    }
    public Node getRoot() {
        return root;
    }
    private Node<T> store(Node<T> branch, Node<T> edit) {
        Node<T> node = branch;
        while (!node.isLeaf()) {
            node = node.getNext();
        }
        node.setLeft(branch);
        node.setRight(edit);
        return node;
    }
    private Node<T> fetch(Node<T> node){
        Node<T> tmp = node.getRight();
        node.setLeft(null);
        node.setRight(null);
        return tmp;
    }
    public <TAcc> TAcc inject(TAcc state, Callable<TAcc, T> fun){
        if (root == null) return null;
        Node<T> current = root;
        Node<T> edit = null;
        while (!(edit == null && current.isLeaf())) {
            state = fun.call(state, current.getValue());
            if (current.isNormalBranch()) {
                current = current.getNext();
            } else {
                if (current.isLeaf()) {
                    current = edit.getLeft().getRight();
                    edit = fetch(edit);
                } else {
                    edit = store(current, edit);
                    current = current.getLeft();
                }
            }
        }
        state = fun.call(state, current.getValue());
        return state;
    }
    public static void main(String[] args) {
        Root<Integer> root = new Root<Integer>();
        Random rand = new Random();
        long state = 0;
        int tmp;
        for (int i = 0; i < 10000; i++){
            tmp = rand.nextInt(100000);
            root.add(tmp);
            root.addSort(tmp + 1);
            state += 2*tmp + 1;
        }
        System.out.println(state ==
                root.inject(0, new Callable<Integer, Integer>(){
                    public Integer call(Integer a, Integer b){
                        return a + b;
                    }
                }));
    }
}


Код на Smalltalk, реализован в Pharo, почти стандартный экспорт в файл.


Object subclass: #Node
instanceVariableNames: 'left rigth value'
classVariableNames: ''
poolDictionaries: ''
category: 'my'!
add: v
left ifNil: [ ^ left := Node new value: v ].
rigth ifNil: [ ^ rigth := Node new value: v ].
^ (left size) < (rigth size) ifTrue: [ left add: v ] ifFalse: [ rigth add: v ]
addSort: v
^ v < value
ifTrue: [ left isNil ifTrue: [ left := Node new value: v ] ifFalse: [ left addSort: v ] ]
ifFalse: [ rigth isNil ifTrue: [ rigth := Node new value: v ] ifFalse: [ rigth addSort: v ] ] .
fetch
| tmp |
tmp := rigth.
left := nil.
rigth := nil.
^ tmp
isBranch
(left isNil) & (rigth isNil not) ifTrue: [ ^ true ].
(left isNil not) & (rigth isNil) ifTrue: [ ^ true ].
^ false
isLeaf
^ left isNil & rigth isNil
left
^ left
left: anObject
left := anObject
next
rigth isNil not ifTrue: [ ^ rigth ].
left isNil not ifTrue: [ ^ left ].
^ nil
printOn: aStream
aStream nextPutAll: 'aNode: '.
aStream print: value.
rigth
^ rigth
rigth: anObject
rigth := anObject
size
| lsize rsize |
lsize := left isNil ifTrue: [ 0 ] ifFalse: [ left size ].
rsize := rigth isNil ifTrue: [ 0 ] ifFalse: [ rigth size ].
^ lsize + rsize + 1
store: branch lastEdit: edit
^ self isLeaf
ifTrue: [
left := branch.
rigth := edit.
self ]
ifFalse: [ self next store: branch lastEdit: edit ].
value
^ value
value: anObject
value := anObject
Object subclass: #Root
instanceVariableNames: 'root'
classVariableNames: ''
poolDictionaries: ''
category: 'my'!
add: value
^ root isNil ifTrue: [ root := Node new value: value ] ifFalse: [ root add: value ]
addSort: v
^ root isNil ifTrue: [ root := Node new value: v ] ifFalse: [ root addSort: v ]
inject: init into: aBlock
| cur edit state |
cur := root.
state := init.
edit := nil.
[ edit isNil & cur isLeaf ] whileFalse: [
state := aBlock value: state value: cur value.
cur isBranch
ifTrue: [ cur := cur next ]
ifFalse: [ cur isLeaf
ifTrue: [
cur := edit left rigth.
edit := edit fetch ]
ifFalse: [
edit := cur store: cur lastEdit: edit.
cur := cur left ] ] ].
^ aBlock value: state value: cur value.
root
^ root
size
^ root size


Тестовый workspace:


root := Root new.
rand := Random new.
state := 0.
1000 timesRepeat: [ | t |
t := rand nextInt: 1000000.
state := state + 1 + (t * 2).
root addSort: t.
root add: (t + 1) ].
(root inject: 0 into: [ :a :b | a + b ]) = state.

Файлы с исходниками
smalltalk: http://dl.dropbox.com/u/1619524/src/binary_tree.st
java node class: http://dl.dropbox.com/u/1619524/src/Node.java
java root class: http://dl.dropbox.com/u/1619524/src/Root.java

PS Буду рад любым замечаниям.

7 comments:

  1. Ну во-первых не помешали бы комментарии непосредственно к коду. Возникли следующие вопросы:
    1. Есть метод add, а есть addSort. В чём между ними разница и когда какой следует вызывать?
    2. Что вообще делает метод inject? Я так понимаю, в нём и происходит обход, но откуда такое интересное имя?
    3. Предположим, есть конкретная задача (не просто же так мы писали абстрактный обход, а для чего-то), вывести все элементы дерева на экран. Как мне это сделать, используя твой класс?

    И ещё вопрос по именованию. Что это за класс Root, в котором ещё и хранится какой-то root? Может всё-таки имелось в виду само дерево, что-нибудь типа Tree?

    ReplyDelete
  2. Данный код писал в качестве пруфофконцепт, по этому комментов не было. Да и код не такой уж и большой.
    1. add - Добавление в дерево основываясь на его сбалансированности.
    addSort - Добавление в дерево основываясь на том, что его элементы были упорядочены.
    В данном случае оба нужны для того, что бы дерево забивалось довольно странным образом, так как это позволит лучше протестить алгоритм.
    2. Метод inject - стандартный метод свёртка. В других языках называется когда как: reduce (Ruby), fold (Haskell). Данное название было взято из колекций smalltalk (сперва писалось именно на нём), а откуда оно там такое - если бы я знал... Могу найти ссылку на хорошую статью на тему.
    3. Вот пример:

    root inject: null into: [ :a :b | Transcript show: b ]

    root.inject(null, new Callable() {
    public Object call(Object a, Integer b){
    System.out.println(b);
    return null;
    }
    });

    Может быть где-то опечатался. Хотя для данной задачи лучше подошёл бы аналог foreach или do (в терминах Smalltalk), так как они не проихводят лишних операций.

    Исходя из идеи, что дерево это фрактальная структура, было бы корректно оставить только тип Node, и назвать его Tree, но в данном случае, по скольку для корня есть дополнительные операции, он был вынесен в отдельный класс. А если просто переименовать Root в Tree, то было бы неплохо и переименовать Node в Branch.

    ReplyDelete
  3. 1. Просто смущает тот факт, что если я напишу
    root.add(1);
    root.add(2);
    , то элементы уже не будут упорядочены. И вызывать дальше addSort нет никакого смысла.
    Кстати, со сбалансированностью ты тоже погорячился, там всё намнооого сложнее.
    3. Ну, как ты сам видишь, не лучший вариант. Для свёртки наверное годится, но не для реального использования. Лишний параметр, необходимость возвращать значение... То есть это как раз к вопросу о стиле. Применяем ООП, написали один раз, используем везде.

    ReplyDelete
  4. 1. Если их мешать между собой - то результат получится очень странный - факт. Но если использовать только add, то дерево получится сбалансированным.
    3. Не могу согласиться. Использование таких вот функционалов (по сути - они, по факту в ооп как называются, увы, не знаю, наверное есть такой патерн), очень хорошо структурирует и упрощает код, в том числе и ООП. Другое дело, что среди С++-ников и Java-вистов это не очень принято в виду некоторых недостатков языка.

    ReplyDelete
  5. 1. Так мы говорим о дереве поиска или просто рандомном? Ведь смысл балансировки как раз в том и заключается, чтобы был быстрый поиск.
    3. А вот тут у меня для тебя хорошие новости :)
    В шарпе есть делегаты, примерно то же, что и ты написал (например стандартный Action). И даже их высшая форма эволюции лямбда-выражения.
    Action<int> printAction = (x => Console.WriteLine(x));
    printAction.Invoke(5);
    А джава пока безнадёжно отстаёт, да.

    Я бы принимал в методе именно такой делегат (с одним параметром и типом void).

    ReplyDelete
  6. 1. В данном случае речь шла именно о простом бинарном дереве. Балансировка была только по весам веток (собственно задача балансировки дерева поиска - отдельная, и большая задача).
    2. В данном вопросе, если не ошибаюсь (с шарпом знаком на уровне вики листал), единственное чем шарп лучше - это наличием синтаксического сахара, а по факту, это примерно тоже самое. В частности это можно увидеть в MPS, их обёртки для безымянных функций. Есть и другие реализации. Да и с выходом новой джавы, скорей всего появится аналог.
    У .net, на сколько мне известно, есть значительные преимущества на уровне виртуальной машины, в частности: честные генерики, хвостовая рекурсия и что-то для динамических языков. Вот этого java лишена в виду более старшего возраста.
    Лично мне .net не нравится только от того, что он, не смотря на mono, очень сильно завязан на винде. Но тут мы уже попадаем в религиозные войны.

    ReplyDelete
  7. Да, завязка на винду его конечно не красит.

    ReplyDelete