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 Буду рад любым замечаниям.