Структуры даных. Бинарное дерево поиска

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

Что такое дерево? Дерево является связным графом ( да-да, про графы я еще напишу ) , который не содержит циклы, ребра графа не ориентированны и не взвешенны.

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

Допустим у нас есть следующее дерево:

Обычное бинарное дерево

Поиск минимального значения невероятно прост — это всегда самый левый узел, то есть мы пробегаем по всем потомкам, если у потомка есть левый лист, значит бежим по его потомкам. Как только мы видим, что потомков нет — вуаля, у нас самое маленькое значение:

Поиск минимального значения

Тоже самое с самым большим значением — оно всегда самое правое:

Поиск наибольшего значения

Поиск элемента тоже очень прост:

1. Как обычно начинаем с корневого элемента.
2. Проверяем или даный элемент — тот который нам нужен. Если да — возвращаем
3. Если нет: смотрим или он больше даного, или меньше. Идем к соответствующему листу
4. Если листов нет — элемента нет. Если есть — повторяем пункт 2.

Так же, Сейджвик в своем курсе на Coursera приводит пример поиска наименьшего / наибольшего элемента для заданого ключа, которые:

Наибольший <= заданому ключу

Наименьшей >= заданому ключу.

К примеру, в нашем дереве, наибольший ключ для 5 будет равен 4, а наименьший 6. Эти операции Сейджвик называет floor и ceil.

Итак, давайте приступим к написанию кода! Для начала, создадим сам объект узла:

Node = function(key, value){
  this.key = key;
  this.value = value;
  this.left = null;
  this.right = null;
  this.count = 0;
}

Теперь забивка на самое дерево и корневой узел:

BinaryTree = function(){}
BinaryTree.prototype.root = null;

Добавим метод, который будем использовать для добавление узла в дерево:

BinaryTree.prototype.addNode = function(key, value){
  this.root = putNode( this.root, key, value );
}
function putNode(node, key, value){
  if ( !node ) return new Node(key, value);
  if (node.key > key ){
    node.left = putNode( node.left, key, value);
  } else if (node.key < key) {
    node.right = putNode(node.right, key, value);
  } else if (node.key == key){
    node.value = value;
  }
  node.count = 1 + getSize(node.left) + getSize(node.right);
  return node;
}

Как видим в функции добавления, мы смотрим в куда нам добавить новый узел, в зависимости от величины нашей ноды. Метод count нужен для того чтобы определить ранг узла ( рангом называют высоту дерева или поддерева☺ ). Метод достаточно прост:

function getSize(node){
  if (!node) return 0;
  return node.count;
}

Теперь стоит реализовать метод поиска необходимого узла:

BinaryTree.prototype.getNode = function(key){
  var currentNode = this.root;
  while (currentNode != null){
   if (currentNode.key > key) currentNode = currentNode.left; 
   else if (currentNode.key < key) currentNode = currentNode.right;
   else if (currentNode.key == key ) return currentNode;
  }
  return null;
}

Метод реализован полностью по шагам, которые были описаны выше.

Методы получения минимального и максимального значения совершенно тривиальны:

BinaryTree.prototype.getMinNode = function(){
  return getMin(this.root);
}
function getMin(node){ 
  if (!node.left) return node;
  return getMin(node.left); 
}
BinaryTree.prototype.getMaxNode = function(){
  return getMax(this.root);
}
function getMax(node){ 
  if (!node.right) return node;
  return getMax(node.left); 
}

Реализации floor и ceil методов:

BinaryTree.prototype.floor = function(key){
  var n = getFloor(this.root, key);
  return n;
}
BinaryTree.prototype.ceil = function(key){
  var n = getCeil(this.root, key);
  return n;
}
function getFloor(node, key){
  if ( node == null ) return null;
  if (node.key == key ) return node;
  if (node.key > key) return getFloor(node.left, key);
  var x = getFloor(node.right, key);
  if (x) return x;
  return node;
}
function getCeil(node, key){
  if ( node == null ) return null;
  if (node.key == key ) return node;
  if (node.key < key) return getCeil(node.right, key);
  var x = getCeil(node.left, key);
  if (x) return x;
  return node;
}

Как видим в обоих этих методах — одинаковый подход. Как только мы находим элемент который больше/меньше нашего элемента — начинаем бегать по наследникам в противоположную сторону. Если элемент найден — возвращаем, если нет — то возвращаем данный узел.

Удаление же узла — не такая простая операция как кажется. Если подумать, у нас может быть целых три случая:

1. Если мы удаляем узел у которого нет потомков, мы просто ссылку на него возвращаем как null.
2. Если мы удаляем узел у которого всего лишь один наследник — то мы просто возвращаем ссылку на наследника, вместо того чтоб возвращать ссылку на себя
3. Если у узла двое детей — то все становиться интереснее — какой наследник вернуть, чтоб наше бинарное дерево не перестало быть бинарным. В даном случае нам на помощь приходить Hibbard Delition ( не знаю как перевести ☺ ). Оно указывает, что если мы удаляем узел у которого больше одного ребенка, то его стоит просто заменить на минимальный узел справа, и удалить этот минимальный узел с предыдущего места. К примеру если мы в нашем дереве удалим допустим элемент 8, то по правилам удаления у нас должно получиться:

Что совсем не нарушает наше дерево☺Итак, для начала реализуем метод удаления минимального элемента:

BinaryTree.prototype.deleteMin = function(){
  deleteMin(this.root);
}
function deleteMin(node){
  if (node.left == null) return node.right;
  node.left = deleteMin(node.left);
  node.count = 1 + getSize(node.left) + getSize(node.right);
  return node;
}

По коду видно, что мы рекурсивно бегаем по всем левым листам, и как только находим самый левый лист у которого нет левого потомка, возвращаем правого потомка ( если нет — вернется null, что нам тоже подходит )

А теперь само удаление:

BinaryTree.prototype.deleteNode = function(key){
  this.root = deleteNode(this.root, key);
}

function deleteNode(node, key){
  if (!node) return null;
  if (node.key > key) node.left = deleteNode(node.left, key); 
  else if (node.key < key) node.right = deleteNode(node.right, key);
  else {
    if (!node.right) return node.left;
    if (!node.left) return node.right;
    var t = node;
    node = getMin(t.right);
    node.right = deleteMin(t.right);
    node.left = t.left;
 }
  node.count = 1 + getSize(node.left) + getSize(node.right);
  return node;
}

В следующих постах мы поговорим про трансформацию дерева в массив, балансировку и методы обхода.

Немного чисел:

Поиск элемента в худшем случае O(n)

Удаление элемента O(n)

Вставка O(n)

Как обычно: исходники примеров вы можете найти тут.