Реализация на Java хешированного бинарного дерева

Один мой друг любит говорить (не знаю, его это слова или он их где-то взял), что в программисты идут по двум причинам: если ты хочешь стать хакером или если ты хочешь писать игры. Мой случай второй. Всегда интересовался разработкой игр, причём той частью, которая отвечает за искусственный интеллект в играх. Очень много времени я потратил на изучение алгоритмов поиска пути. Реализуя очередную версию алгоритма A* на Java, столкнулся с интересной ситуацией, связанной с коллекциями TreeSet и TreeMap.

Сразу хочу ввести два понятия, которые буду использовать на протяжении всей статьи: поиск по равенству и поиск по сравнению. Поиском по равенству я буду называть поиск в коллекции, где для сравнения элементов используются методы equals и hashCode. Поиском по сравнению или поиском на основании сравнения я буду называть поиск элемента в коллекции, где для сравнения элементов используются методы compare и compareTo.

В алгоритме A* используется две коллекции для хранения точек пути: открытый список и закрытый список. Точка пути, грубо говоря, имеет для нас три важных атрибута: координату X, координату Y и значение метрической функции – F. Для закрытого списка необходимо выполнять только две операции добавление и поиск. С открытым списком всё несколько сложней. С открытым списком помимо операций добавления и поиска элемента необходимо также находить наименьшую точку по значению метрической функции.

Для закрытого списка выбираем HashSet тут всё очевидно, для операций добавления и поиска отлично подходит, если конечно вы написали хорошую хэш-функцию. С выбором коллекции для открытого списка возникают затруднения. Если выбрать HashSet, как и для закрытого списка, то мы получим наилучшую асимптотику для операций вставки, поиска и удаления – O(1), однако поиск минимального будет выполняться за O(n). При выборе TreeSet или TreeMap мы будем иметь O(log(n)) для вставки и поиска, но для поиска и удаления минимального будем иметь всё те же O(log(n)). Посмотреть асимптотики различных коллекций можно тут.

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

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

Я решил обобщить задачу. Пусть определена некоторая структура данных, в которой имеется набор полей. Пусть также некоторые поля определяют отношение эквивалентности двух элементов данной структуры, в то время как другие поля определяют отношения порядка (проще говоря, методы equals и hashCode используют одни поля объекта, а методы compare и compareTo другие).
Задача: реализовать структуру данных, в которой операция поиска элемента на основании равенства выполняется с асимптотикой O(1), а операции вставки и удаления работали с учётом операций и сравнения и равенства, и строили бинарное дерево таким образом, что наименьший элемент был бы корнем дерева.

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

image

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

private static class Node<V extends Comparable<V>> {

        private Node parent;
        private Node left;
        private Node right;
        private int k = 0;
        private final V data;

        public Node(V data) {
            this.data = data;
            this.parent = null;
            this.left = null;
            this.right = null;
        }

    }

Тип V определяет элемент коллекции, он должен расширять класс Comparable, чтобы можно было выполнять сравнение для построения дерева.

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

Внутри коллекции должен быть указатель на корень дерева и массив элементов коллекции, где в пустых ячейках хранится null, а в заполненных экземпляры класса Node, где в поле data будет храниться значение добавленного элемента (а точнее значение указателя на экземпляр объекта):

public abstract class HashTree<E extends Comparable<E>> {

    private Node root = null;
    private Node[] nodes;

    public HashTree(int capacity) {
        this.nodes = new Node[capacity];
    }

    public abstract int getElementHash(E element);
…
}

Как и тип V, тип E определяет элемент коллекции. По умолчанию коллекция пуста, поэтому указатель на корневой элемент – null и массив также заполнен значениями null. Класс абстрактный с абстрактным методом getElementHash, позволяющим переопределить вычисление хэш-кода.

Теперь к методам. Метод addElement:
public void addElement(E element) {
        	    int index = getElementHash(element);
        	    if (nodes[index] != null) {
            	        return;
        	    }
       	    Node<E> node = new Node<>(element);
        	    nodes[index] = node;
        	    this.root = connectNodes(this.root, node);
    	}

В методе получаем хэш-код добавляемого элемента. Создаём новый узел дерева с новым элементом в качестве данных и добавляем его в дерево и в массив, где хэш-код определяет индекс в массиве. Вставка элемента в массив имеет асимптотику O(1), вставка в дерево — O(log(n)), суммарная асимптотика – O(log(n)).

Метод removeElement:
public E removeElement(E element) {
        int index = getElementHash(element);
        Node node = nodes[index];
        if (node == null) {
            return null;
        }
        nodes[index] = null;
        E data = (E) node.data;
        Node l = getElemInArray(node.left);
        Node r = getElemInArray(node.right);
        if (l != null) {
            l.parent = null;
        }
        if (r != null) {
            r.parent = null;
        }
        l = connectNodes(l, r);
        if (node.parent == null) {
            this.root = l;
            if (this.root != null) {
                this.root.parent = null;
            }
            return data;
        }
        int p = getElementHash((E) node.parent.data);
        if (nodes[p] != null) {//здесь сравниваются ИМЕННО значение указателей, 
                               //интересует равенство адресов памяти, а не значений
            if (nodes[p].left == node) {
                nodes[p].left = null;
            }
            if (nodes[p].right == node) {
                nodes[p].right = null;
            }
        }
        connectNodes(nodes[p], l);
        return data;

    }

Здесь, используя хэш-код удаляемого элемента, извлекается из массива узел дерева, который нужно удалить. Используя предка удаляемого узла, выполняем удаление элемента, в процессе которого приходится 2 раза вызывать связывание поддеревьев, каждая из операций в худшем случае обладают асимптотикой – O(log(n)). В итоге метод имеет асимптотику O(log(n)).

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

Метод connectNodes:
private Node connectNodes(Node parent, Node node) {
        if (node == null) {
            return parent;
        }
        if (parent == null) {
            return node;
        } else {
            if (compare(node, parent) < 0) {
                return connectNodes(node, parent);
            }
            Node cur = parent;
            Node n = node;
            while (cur != null) {
                if (cur.left == null) {
                    cur.left = n;
                    n.parent = cur;
                    cur.k++;
                    break;
                }
                if (cur.right == null) {
                    if (compare(n, cur.left) <= 0) {
                        cur.right = cur.left;
                        cur.left = n;
                        n.parent = cur;
                        cur.k++;
                        break;
                    } else {
                        cur.right = n;
                        n.parent = cur;
                        cur.k++;
                        break;
                    }
                }
                if (compare(n, cur.left) <= 0) {
                    Node tmp = cur.left;
                    cur.left = n;
                    n.parent = cur;
                    cur.k++;
                    cur = n;
                    n = tmp;
                    continue;
                }
                if (compare(n, cur.right) < 0
                        && compare(n, cur.left) > 0) {
                    cur.k++;
                    if (cur.right.k < cur.left.k) {
                        Node tmp = cur.right;
                        cur.right = n;
                        n.parent = cur;
                        cur = n;
                        n = tmp;
                    } else {
                        cur = cur.left;
                    }
                    continue;
                }
                if (compare(n, cur.left) > 0) {
                    cur.k++;
                    cur = cur.left.k < cur.right.k ? cur.left : cur.right;
                }
            }
            return parent;
        }

Методу connectNodes стоит уделить особое внимание. Добавление нового элемента выполняется с использованием этого метода применительно к корню и новому элементу. Считаем, что дерево не пусто:
image

Возможно 4 случая:
  1. новый элемент меньше корня;
  2. новый элемент меньше левого потомка;
  3. новый элемент больше левого потомка, но меньше правого;
  4. новый элемент больше правого потомка.


Случай 1.
В данной ситуации левым потомком нового элемента становится parent, если parent — корень дерева, то соответственно новым корнем будет новый, добавленный элемент.
image

Случай 2.
Тут возможно два варианта: правый потомок определён и правый потомок не определен. Если левый потомок не определён, то мы считаем что левый потомок имеет большее значение новый узел. В обоих ситуациях новый элемент становится левым потомком parent, а left (который был левым потомком до добавления) становится правым потомком. Однако во втором случае нужно выполнить присоединение старого правого потомка right к новому правому потомку left. Присоединение left к right будет происходить по тем же правилам, что и в описываемых случаях.
image

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

Случай 4.
В этом случае выполняется переход по тому поддереву, в котором меньше всего узлов. Число узлов накапливается в поле k.
image

Теперь оценим асимптотику метода connectNodes. В лучшем случае, когда в дерево добавляются узлы без потомков в порядке уменьшения, асимптотика будет равна O(1), так как в этом случае поместить новый элемент на место прародителя. Если речь идёт о связывании узла с потомками и меньшим чем прародитель, то нужно будет пройти по поддереву узла. Для случая 2 в пункте а) асимптотика — O(1), а в пункте б) нужно вновь пройти по поддереву вставляемого узла.
Заметим, что поле k у узлов увеличивается для всех случаев, кроме 1-го, это сделано, чтобы дерево заполнялось симметрично, но не нарушая увеличивающегося порядка по левому поддереву если таковой встретится.

Чтобы оценить сложность прохода по дереву достаточно оценить его высоту. Высота дерева и будет искомой асимптотикой. Отдельным вопросом стоит наличие длиной последовательности по левому поддереву. Если учесть наличие таких поддеревьев, то в худшем случае асимптотику выполнения связывания можно считать как асимптотику связывания с поддеревом, которое мы хотим привязать, а в лучшем случае как O(1) (2 случай).
image

Так как при связывании узлов мы имеем дело с узлами внутри дерева значит высоту любого поддерева можно считать не превосходящей высоту самого дерева. Таким образом оценив высоту всего бинарного дерева получим асимптотику метода connectNodes. Из за того, что выбор поддерева для вставки выбирается на основании поля k узла (в котором хранится размер поддерева за исключением подряд идущих увеличивающихся узлов они считаются как один узел), дерево стремится заполнить следующий свой уровень только после заполнения предыдущего (исключая, конечно же описанный выше случай 1). Таким образом древо будет иметь вид:
image

Таким образом, если n — количество узлов в дереве, то $n = \sum_{i=0}^h 2^i$. Из чего вытекает, что высота дерева $h = \log_{2}(n+1) - 1$. Отсюда следует, что асимптотика метода connectNodes — O(log(n)).

Поиск элемента можно осуществлять не в дереве, а в массиве на основании хэш-кода, поэтому операция поиска имеет асимптотику O(1). А так как дерево организовано как бинарное, то в корне всегда находится минимальный элемент по сравнению и асимптотика поиска минимального — O(1). Замечу, что удаление минимального элемента имеет асимптотику O(log(n)), так как при удалении требуется реорганизовать дерево, начиная с корня применяя метод connectNodes.

На первый взгляд операция удаления минимального элемента в реализованной коллекции имеет худшую асимптотику, чем у коллекции HashSet, но не стоит забывать, что прежде чем удалить минимальный элемент его сначала нужно найти, а для этого требуется выполнить операции с асимптотикой O(n). Таким образом, итоговая асимптотика операции удаления минимального элемента в коллекции HashSet будет иметь вид – O(n).

Проверка наличия элемента в коллекции, как уже говорилось выше, выполняется на основании проверки на null элемента массива по индексу, определяемому хэш-кодом элемента. Проверка выполняется методом contains и имеет асимптотику O(1):

public boolean contains(E element) {
        int index = getElementHash(element);
        return nodes[index] != null;
 } 

Также на основании хэш-кода выполняется поиск по равенству при чём с той же асимптотикой при помощи метода getElement:

public E getElement(E element) {
        return (E) nodes[getElementHash(element)].data;
 }

Реализованная коллекция не лишена недостатков. Она требует больше памяти, ей нужна хэш-функция без коллизий и для реализации перебора элементов придётся реализовывать обход дерева, что также не доставляет удовольствия, но данная коллекция предназначена для других целей. Главное преимущество – это возможность поиска элементов одного типа по разным критериям с наилучшей асимптотикой. В применении к моей задаче, это был поиск по равенству на основании координат и поиск минимального элемента на основании сравнения значений метрической функции.

В конце приведу результаты тестирования коллекции на быстродействие по сравнению с коллекциями LinkedHashMap, TreeSet и HashSet. Все коллекции заполнялись 1000 значений типа Integer и, с заполненными коллекциями, проводился следующий набор операций:
  1. помещение нового элемента в коллекцию;
  2. проверка на наличие в коллекции элемента с заданным значением (проверка выполнялась дважды для элемента, который был в коллекции и для элемента, которого в коллекции не было);
  3. поиск и удаление минимально по сравнения элемента;
  4. удаление, добавленного в пункте 1, элемента.

Результаты тестов приведены в таблице:
Коллекция Количество повторений Затраченное время
LinkedHashMap 10 000 000 1985±90 мс
TreeSet 10 000 000 1190±25 мс
HashSet 1 000 000 4350±100 мс
HashTree 10 000 000 935±25 мс

В итоге имеем более чем в 2 раза большую скорость коллекции HashTree по сравнению с LinkedHashMap и в 1.27 раза большую по сравнению с TreeSet (рассматривать HashSet не имеет смысла вообще). Проверки выполнялись на машине с 4Гб оперативной памяти и процессором AMD Phenom(tm)II X4 940, ОС – 32-разрядная Windows7 Профессиональная.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 22

    +5
    P.S.: Коллекцию можно ещё больше ускорить за счёт использования красно-чёрного дерева вместо бинарного.


    Красно-черное дерево — это реализация сбалансированного бинарного дерева поиска.

    . При выборе TreeSet или TreeMap мы будем иметь O(log(n)) для вставки и поиска, но для поиска и удаления минимального будем иметь всего лишь O(1).


    В стандартнах классах java.util.TreeMap#getFirstEntry работает за O(log n)

    Вам на самом деле нужно не дерево, а min-heap. И прикрутить к нему HashMap который будет запоминать индекс в Heap для возможности работы с произвольным элементом.
      0

      Я думал насчет использования min-heap вместо бинарного дерева, но мне показалось, что использование обычного дерева позволит использовать для сравнения любые наборы данных. К тому же, что и min-heap и бинарное дерево имеют одинаковую асимптотику. Использование стандартной коллекции же не даст высокой производительности так как они реализованы для наиболее общих случаев и не используют дополнительные знания о структуре элементов. Что касаемо TreeMap, getFirstEntry наверное и имеет асимптотику O(log n), а вот getFirstKey должен иметь асимптотику как и у TreeSet, т.е. O(1), хотя я могу и ошибаться(чего очень хотелось бы ведь тогда я имею выигрыш в производительности и по этому методу).

        +1
        1. min-heap тоже может работать с любыми данными, проблема стандартных реализаций min-heap заключается в том, что обычно они не поддерживают эффективное удаление произвольного элемента из кучи, даже если известна позиция элемента в куче;
        2. Чтобы асиптотика операций над вашим деревом была логарифмической, высота дерева должна быть логарифмический, что из вашего кода не очевидно, в то время как TreeMap/TreeSet гарантируют логарифмическую сложность.

        Кроме того

        3. Если вы используете хеш, то не должны ли вы предусмотреть возможность коллизий? Или просто использовать HashSet, который уже умеет это делать.
        4. Ваша функция connectNodes выглядит как-то странно, допустим вы хотите объединить два узла, у которых есть дети (в зависимости от реализации getElemeInArray, которую вы нигде не упоминаете, это может произойти при удалении элемента по значению), тогда посмотрим на этот код в самом начале функции:
        if (compare(node, parent) < 0) {
            node.left = parent;
            parent.parent = node;
            parent = node;
            return parent;
        }
        

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

        Перед тем как заниматься сравнением производительности, не могли бы вы показать более или менее формально, что:
        1. ваша структура данных вообще кооректно работает
        2. что ваша асимптотика такая, как вы заявляете?
          0
          По поводу 1го пункта именно неэффективное удаление произвольного элемента меня и не устраивает. С пунктом 2 соглашусь. По поводу 3-го я указал, что нужно описать хэш-функцию без коллизий для заданного размера коллекции. Напомню, что в начале статьи я указал для чего писал коллекцию, думаю для матрицы m на n не трудно написать хэш-функцию без коллизий, для элемента хранящего целочисленные координаты точки. За 4-й пункт огромное спасибо, исправлюсь.
            –1

            Для матрицы m на n такая функция без коллизий выглядит как i*n + j и хеш-функцией не является.

              0
              А чем же?
                0

                Просто функцией, вычисляющей индекс.

                  +1
                  Ну а почему бы ей и не побыть хэш-фукцией? Одно другому не мешает.
                    0

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


                    "Я написал хеш-таблицу… без коллизий" звучит так же как и "я сам построил дом… для кошки".

                      –2
                      Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
                      Я реализовал дерево, в котором каждый узел может быть получен из массива на основании ключа — в моём случае хэш-кода элемента.
                      Ну и вконце-концов я не хэш-таблицу написал.
                        +1

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

              0

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


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

                0
                Да, дельное замечание, просто структуру писал как раз под этот самый конкретный случай и мне понадобится и нормальный хэш от элемента.
                В будущем возможно доведу до ума, а так пока хочу протестировать под свою задачу.
            +1
            Я бы на вашем месте сначала посмотрел в исходники. В самом деле, может показаться, что firstKey() работает за единицу, но в исходниках он выглядит ровно так:
            public K firstKey() {
                return key(getFirstEntry());
            }
            

            Здесь вызов key(entry) действительно работает за единицу, а вот getFirstEntry() работает за logN:
            final Entry<K,V> getFirstEntry() {
                Entry<K,V> p = root;
                if (p != null)
                    while (p.left != null)
                        p = p.left;
                return p;
            }
            
              0
              Спасибо за замечание, посмотрел исходники, действительно асимптотика O(log(n)), исправлю.
              0

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


              Просто за счет простоты алгоритма и локальности обращений к памяти.


              PS а чтобы getFirstEntry работало за константное время, дерево должно быть прошитым

                0

                Не обязательно, можно просто после каждой изменяющей дерево операции за высоту дерева найти минимум — асимптотика никак не пострадает.

                0
                Del
              –1

              "Хэш-функция без коллизий" это примерно то же, что и первичный ключ сущности. Строил так дерево категорий по записям из базы. Сначала делаем массив объектов, индексированный по category.id, затем обращаемся по индексу category.parent_id и добавляем текущий объект в свойство children.

                0
                Спасибо за замечания. Исправил ошибки с методом, connectNodes, после исправления ошибок коллекция стала работать немного быстрее, но результаты в таблице решил не трогать, проверил асимптотику и добавил её оценку. Над тестированием коллекции ещё работаю.
                  +1
                  Кажется, что ваш анализ неправильный. Представим, что мы добавляем в ваше дерево элементы в таком порядке:
                  — 1, 10, 2 (тут мы получаем дерево высоты 2, в корне 1 в левом поддереве 2, в правом 10)
                  — 9 (9 станет левым ребенком 2, потому что 9 больше 1 и 2 в левом поддереве, но меньше 10, значит по коду идем в левое поддерево, где вставка уже делается очевидным образом)
                  — 3 (3 станет левым ребенком 2 как раньше было с 9, а 9 станет правым ребенком 2)
                  — 8 (8 станет левым ребенком 3)
                  — 4 (4 станет левым ребенком 3, а 8 станет правым)
                  — 7 (7 станет левым ребенком 4)
                  — 5 (5 станет левывм ребенком 4, а 7 станет правым)

                  Если я правильно понял, тот такой паттерн вырождает ваше дерево практически в бамбук, и при этих вставках
                  поле k вообще не проверяется. Мне серьезно кажется, что гораздо проще просто использовать TreeSet/TreeMap и после каждого обновления переискивать минимальный элемент.
                    –1
                    Вы правильно всё поняли. Действительно вырождает, тогда добавлю весовую оценку и для этого случая. Не хочу использовать TreeSet из-за того, что наличие цепочек в моём дереве улучшает асимптотику операций, а в TreeSet используются операции с гарантированными сложностями методов. Хотя вашу идею с использованием TreeSet/TreeMap и переискиванием минимального элемента стоит попробовать и сравнить с тем, что у меня получится.

                Only users with full accounts can post comments. Log in, please.