Бинарные деревья

Поиск данных
Стандартный класс Map
Класс BSTree

Бинарный поиск
Сбалансированность дерева
Быстродействие

Поиск данных

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

var obj = {};                               // объявляем пустой объект
 
obj[ 5 ]         = 1;                       // добавляем число
obj["строка"]    = 2;                       // добавляем строку
obj[ [0,1,2] ]   = 3;                       // добавляем массив
obj[ {x:0,y:0} ] = 4;                       // добавляем структуру
 
document.write(obj[5],'<br>');              // получаем значения
document.write(obj[7],'<br><br>');
document.write(obj["строка"],'<br>');
document.write(obj["строка2"],'<br><br>');
document.write(obj[ [0,1,2] ],'<br>');
document.write(obj[ [0,1,3] ],'<br><br>');
document.write(obj[ {x:0,y:0} ],'<br>');
document.write(obj[ {x:0,y:1} ],'<br><br>');
 
if( obj[ "строка2" ] === undefined)         // проверяем было ли
   document.write('Ещё не было строка2.<br><br>');
 
for(var i in obj)                           // выводим все свойства
   document.write(obj[i],' ',typeof i,': ', i,'<br>');

1
undefined

2
undefined

3
undefined

4
4

Ещё не было строка2.

1 string: 5
2 string: строка
3 string: 0,1,2
4 string: [object Object]

Свойство (то, что находится в квадратных скобках) принято называть ключом, а значение свойства - это некоторые данные (или просто - значение). Запись obj[key]=value означает, что мы сохранили в объекте пару ключ-значение. Поиск данных происходит по ключу. Из приведенных примеров следует, что ключами в объекте могут выступать числа, строки и массивы. Однако, они при этом конвертируются в строки (значение typeof в цикле). Проверить наличие свойства можно сравнивая его значение с undefined. Объект формально можно сделать ключем, но он теряет значения своих свойств и в этом смысла нет. Впрочем, для создаваемых классов можно переопределить функцию toString и тогда всё будет нормально работать:

function Pos(x, y)                  {  this.x = x;   this.y = y;  }
Pos.prototype.toString = function() {  return "x:"+this.x+",y:"+this.y;}
 
obj[ new Pos(1,1) ]  = 5;
 
document.write(obj[new Pos(1,1)],'<br>');
document.write(obj[new Pos(1,2)],'<br><br>');
 
for(var i in obj)
   document.write(obj[i],' ',typeof i,': ', i,'<br>');

5
undefined

1 string: 5
2 string: строка
3 string: 0,1,2
4 string: [object Object]
5 string: x:1,y:1

JavaScript
key in obj

Обратим внимание на конструкцию for(var key in obj). Она пробегает по всем свойствам key объекта obj в том порядке, в котором они были вставлены. Аналогичным образом можно проходить и по элементам массива, однако это не рекомендуется делать, так как такой цикл будет существенно медленнее обычного цикла от начала к концу: for(var i=0; i < ar.length; i++) или от конца к началу: for(var i=ar.length; i--; ).

Стандартный класс Map

В JavaScript существует также встроенный класс Map, который является ассоциативным массивом. Его ключами могут быть числа, строки и ссылки на объекты. При этом числа и объекты в строки не конвертируются:

var obj = {x:2};                            // некоторый объект
var map = new Map();                        // ассоциативный массив
map.set("key", "data 1");                   // ключ -  строка
map.set(   25, "data 2");                   // ключ - число
map.set(  obj, "data 3");                   // ключ - указатель на объект
 
document.write(map.get("key"), '<br>');     // значение для строкового ключа
document.write(map.get(25),    '<br>');     // значение для числового ключа
document.write(map.get(obj), '<br>');       // значение для указателя на объект
document.write(map.get(16), '<br>');        // undefined - нет такого ключа
document.write(map.get({x:2}), '<br>');     // undefined - это другая память!
 
if( map.has("key") ) document.write("ok");  // проверка наличия ключа
 
for (var [key, value] of map)               // выводим все ключи и значения
  document.write(key + " = " + value,'<br>');
 
for (var key of map.keys())                 // выводим только ключи и их тип
  document.write(key," : ", typeof key,'<br>');

data 1
data 2
data 3
undefined
undefined
ok
key = data 1
25 = data 2
[object Object] = data 3
key : string
25 : number
[object Object] : object

К сожалению, некоторые мобильные браузеры не поддерживают класс Map. Отстаёт в реализации ряда методов этого класса также Internet Explorer.

Использование объектов или класса Map для быстрого доступа к данным в JavaScript достаточно эффективный способ. Чтобы было с чем сравнивать, создадим собственную структуру хранения упорядоченных данных - бинарное дерево. Дополнительно мы получим возможность хранить данные с повторяющимся ключом (свойством).

Класс BSTree

Узел бинарного дерева - это объект { k, v, lf, rt }, хранящий ключ k, данные v и указатели на левую lf и правую rt ветки потомков узла. При этом, ниже, на левой ветке всегда находятся узлы со значением ключа k меньшим или равным, чем у данного, а на правой ветке - с большим. На рисунке приведен пример бинарного дерева с 7 узлами (в узлах - ключ k):

Числа 1,2,3 меньшие 4, находятся слева от него, а 5,6,7 - большие и расположены справа. Это свойство выполняется не только для корня, но и для любого узла дерева (1 слева, а 3 - справа от 2 и т.д.). Упорядоченность бинарного дерева ускоряет функции поиска, т.к. спуск сверху-вниз происходит дихотомией (делением) - в каждом узле мы поворачиваем налево или направо, в зависимости от значения ключа k в этом узле.

Напишем конструктор класса BSTree (Binary Search Tree = дерево двоичного поиска):

function BSTree()
{
   this.root = null;                              // кореневой узел дерева
   this.length  = 0;                              // число узлов в дереве
}

Указатель null похож на undefined, но, в отличии от последнего, определён и указывает в "нулевой" адрес памяти. Т.е. свойство root класса BSTree мы объявили, но его значение равно "нулевому указателю" (см. null vs. undefined).

Функцию вставки нового узла в дерево с сохранением его бинарных свойств назовём addDown. В ней, начиная от корня, мы опускаемся вниз по дереву, "поворачивая" к тому или иному потомку, в зависимости от значения ключей. Если новый ключ совпал с уже существующим - он вставляется после существующего. В противном случае, мы добираемся до самого низа дерева, где и вставляем новый узел:

BSTree.prototype.addDown = function(k, v)
{
   this.length++;                                 // увеличиваем число узлов
   var n = this.root;                             // начинаем с корня дерева
   while(n){
      if(k < n.k){                                // ключ k меньше - идём налево,
         if(n.lf) n = n.lf;                       // если есть левая ветка, идём дальше
         else{                                    // иначе создаём новый узел
            n.lf = { k:k, v:v, lf:null, rt:null };
            return;
         }
      }
      else if(k > n.k){                           // ключ k больше - идём направо,
         if(n.rt) n = n.rt;                       // если есть правая ветка, идём дальше
         else{                                    // иначе создаём новый узел
            n.rt = { k:k, v:v, lf:null, rt:null };
            return;
         }
      }
      else{                                       // ключи совпадают,
         n.lf = { k:k, v:v, lf:n.lf, rt:null };   // вставляем после n
         return;
      }
   }
   this.root = { k:k, v:v, lf:null, rt:null };    // в дереве не было узлов - это корень
}

Добавим, например, в дерево последовательно числа 5,3,3,7,6,8,4,2,1,7,9:

Обратим внимание, что при таком способе вставки, корнем дерева является первое вставляемое значение, а последний ключ всегда находится в самом низу (если он появился впервые).

Бинарный поиск

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

BSTree.prototype.min = function(n)
{
   if(!n) n = this.root;
   return n.lf? this.min(n.lf): n.k;
}

BSTree.prototype.max = function(n)
{
   if(!n) n = this.root;
   return n.rt? this.max(n.rt): n.k;
}

Их вызов для последнего дерева выше даёт 1 для min и 9 - для max.

Функция, проверяющая наличие узла на дереве с ключом k, осуществляет каждый раз выбор правильной ветки:

BSTree.prototype.has = function(k)
{
   var n = this.root;
   while(n){
      if(k < n.k)                                 // если он меньше, идём налево
         n = n.lf;
      else if(k > n.k)                            // если больше - направо
         n = n.rt;
      else                                        // иначе ключи совпадают
         return true;
   }
   return false;                                  // совпадения не нашли
}

Вызов bst.has(5) для дерева выше даст true, а для bst.has(10) - false.

Скрипт, создающий дерево из начала документа и ищущий на нём ключ 5 выглядит следующим образом:

var bst = new BSTree();                           // создаём экземпляр класса
bst.addDown(4);                                   // окажется корнем
bst.addDown(2); bst.addDown(6);                   // левой и правой веткой
bst.addDown(1); bst.addDown(3);
bst.addDown(5); bst.addDown(7);
document.write(bst.min(), bst.max(), bst.has(5));  // минимальное, максимальное значение и есть ли 5

Сбалансированность дерева

Дерево может быть сбалансированным, не очень сбалансированным и совсем не сбалансированным:

Критерием сбалансированности дерева будем считать суммарное число рёбер на пути к каждому узлу:

BSTree.prototype.len = function(n, depth)
{
   if(!n) n = this.root;
   if(depth === undefined) depth = 0;
 
   return depth + (n.lf? this.len(n.lf, depth+1):0)
                + (n.rt? this.len(n.rt, depth+1):0);
}

У деревьев приведенных выше, соответственно len = 10, 11, 15, 21. Для полностью несбалансированного дерева с n узлами суммарная длина равна 0+1+2+...+(n-1) = n(n-1)/2. Для сбалансированного дерева с числом узлов n = 2^k-1 суммарная длина равна 0+1·2¹+...+(k-1)·2^(k-1) = 2 + (k-2) · 2^k = (n+1)·log₂(n+1) - 2·n.

Если дерево сбалансировано, поиск нужного узла дихотомией (налево-направо) при больших n, делается в среднем за log₂(n) шагов (средняя длина пути к ключу равна суммарной длине дерева, делённой на n). В худшем случае (для полностью несбалансированного дерева), поиск в среднем линеен по числу узлов n.

n 100 1000 1000000 1000000000

log₂(n) 7 10 20 30

Можно ввести меру сбалансированности дерева, которая всегда будет находиться в интервале от 0 (несбалансированное дерево) до 1 (сбалансированное), независимо от числа узлов (для деревьев выше, она даёт 1.00, 0.91, 0.67, 0.48):

BSTree.prototype.balance = function()
{
   return ((this.length+1)*Math.log2(this.length+1)-2*this.length)/this.len();
}

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

Быстродействие

Сравним быстродействие вставки ключа в бинарное дерево методом класса BSTree и при помощи класса Map или обычных объектов JavaScript. В последнем случае объект сначала объявляется как пустой: var obj = {}, а затем, происходит вставки следующим образом: obj[key]=1. Будем вставлять упорядоченные целые числа i, случайные числа rnd=Math.random() и случайные числа, преобразованные в строку rndStr = ""+rnd. Естественно, эти величины генерятся перед тестом и время на их получение не учитывается. Приоритетная очередь Queue и список List решают несколько другие задачи, однако также добавлены для сравнения.

добавлений раз: (ms) ( цикл: )

	i	rnd	rndStr
Object[]	4	88	38
Map.set	22	35	24
BSTree.addDown	4919	29	55
Queue.unshift	3	9	12
List.unshift	2	2	2

for(var it = 0; it < iters; it++){
   var bst = new BSTree();
   for(var k=0; k < num; k++) bst.add(arr[k]);
}
 
for(var it = 0; it < iters; it++){
   var lst = new List();
   for(var k=0; k < num; k++) lst.add(arr[k]);
}

Объекты JavaScript (в таблице - первая строка) достаточно шустро работают с целочисленными данными (они дают короткие строки). Для случайных вещественных чисел (rnd) им уже приходится тяжелее (так как числа каждый раз надо преобразовывать к длинным строкам). В этом случае вставка вниз BST.addDown оказывается вполне конкурентной. Если случайные числа поступают в строковом формате (rndStr), преимущество BSTree теряется. Во первых, ему при вставке в каждом узле необходимо в среднем 1.5 сравнений (больше, а затем меньше) строк (в JS нет встроенной C-подобой функции strcmp(a,b) делающий сравнение -1,0,1 за один проход). Ну и конечно, у BSTree большие проблемы с вставкой упорядоченных данных.

Таким образом, для упорядоченного запоминания данных, в дальнейшем мы будем использовать класс Map, который для мобильных браузеров можно эмулировать при помощи объектов. JavaScript.

Списки <

> Приоритетная очередь