Структуры данных 101: Двоичное дерево поиска

struktury dannyh 101 dvoichnoe derevo poiska?v=1656521893

от Кевина Терни

Как объединить эффективность вставки соответствующего списка и быстрого поиска упорядоченного массива.

4k66O-44Ze-2G1D19GB4by1CUYiTnQbEzmpo
«Безлистое дерево на холме» Фабриса Уилларда на Unsplash

Что такое бинарное дерево поиска?

Давайте начнем с базовой терминологии, чтобы мы могли использовать один язык и изучить связанные понятия. Во-первых, какие принципы определяют двоичное дерево поиска?

* С этого момента я буду использовать «BST» для краткости

BST считается структурой данных, состоящей из узлылюблю Связанные списки. Эти узлы либо нулевые, либо имеют ссылки (ссылки) на другие узлы. Эти «другие» узлы представляют собой дочерние узлы, которые называются левым и правым узлом. Узлы имеют ценности. Эти значения определяют, где они размещаются в BST.

Подобно связанному списку, на каждый узел ссылается только один другой узел, его родительский (кроме корневого узла). Итак, мы можем сказать, что каждый узел в BST сам по себе является BST. Потому что ниже по дереву мы достигаем другого узла, и этот узел имеет левый и правый. Затем, в зависимости от того, по какому пути мы идем, этот узел имеет левый и правый и так далее.

1. Левый узел всегда меньше родительского.

2. Правый узел всегда больше родительского.

3. BST считается сбалансированным, если каждый уровень дерева полностью заполнен, за исключением последнего уровня. На последнем уровне дерево заполняется слева направо.

4. Идеальный BST — это тот, в котором он как полный, так и полный (все дочерние узлы находятся на одном уровне, и каждый узел имеет левый и правый дочерние узлы).

2rTqYlcrnWtICedt131tDft0CmkzZaViExJX

Зачем нам это использовать?

Какие реальные примеры BST? Деревья часто используются в поиске, игровой логике, задачах автозаполнения и графиках.

Быстрота. Как упоминалось ранее, BST является упорядоченной структурой данных. После ввода узлы размещаются в порядке. Этот характерный порядок делает поиск быстрым. Подобно двоичному поиску (с отсортированным массивом) мы сокращаем количество данных для сортировки вдвое при каждом проходе. К примеру, предположим, что мы ищем небольшое значение узла. На каждом проходе мы продолжаем двигаться вдоль крайнего левого узла. Это автоматически устраняет половину больших значений!

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

Короче говоря, вставка, удаление и поиск – это главная задача для BST

Теперь, когда мы поняли принципы, преимущества и основные компоненты BST, давайте реализуем его в JavaScript.

API для BST состоит из следующего: Insert, Contains, Get Min, Get Max, Remove Node, Check иf Full, Is Balancedа также типы поиска Сначала в глубину (preOrder, inOrder, postOrder), поиск в ширинуи наконец Получить высоту. Это большой API, просто берите его по одному разделу.

Реализация

Конструктор

BST состоит из узлов и каждый узел имеет значение.

function Node(value){  this.value = value;  this.left = null;  this.right = null;}

Конструктор BST состоит из корневого узла.

function BinarySearchTree() { this.root = null;}
let bst = new BST();let node = new Node();
console.log(node, bst); // Node { value: undefined, left: null, right: null } BST { root: null }

… все идет нормально.

Вставка

BinarySearchTree.prototype.insert = function(value){ let node = new Node(value); if(!this.root) this.root = node; else{    let current = this.root;    while(!!current){       if(node.value < current.value){       if(!current.left){           current.left = node;           break;         }         current = current.left;         }        else if(node.value > current.value){         if(!current.right){            current.right = node;            break;           }          current = current.right;          }         else {          break;           }         }        }    return this; };
let bst = new BST();bst.insert(25); // BST { root: Node { value: 25, left: null, right: null } }

Давайте прибавим еще несколько значений.

bst.insert(40).insert(20).insert(9).insert(32).insert(15).insert(8).insert(27);
BST { root:  Node { value: 25, left: Node { value: 20, left: [Object], right: null }, right: Node { value: 40, left: [Object], right: null } } }

Для классной визуализации Иди сюда!!

Давайте распакуем это.

  1. Сначала мы передаем значение и создаем новый узел
  2. Проверьте, есть ли корневой узел, если нет, установите этот только что созданный узел на корневой узел
  3. Если есть корневой узел, мы создаем переменную, объявленную «current», и устанавливаем ее значение на корневой узел
  4. Если только созданный node.value меньше корневого узла, мы переместимся налево
  5. Мы продолжаем сравнивать это node.value с левыми узлами.
  6. Если значение достаточно мало и мы достигаем точки, где больше нет левых узлов, мы размещаем этот элемент здесь.
  7. Если node.value больше, мы повторяем те же шаги, что и выше, за исключением того, что двигаемся вправо.
  8. Нам нужны операторы break, поскольку нет шага подсчета для завершения цикла while.

Содержит

Это достаточно простой подход.

BinarySearchTree.prototype.contains = function(value){ let current = this.root; while(current){ if(value === current.value) return true; if(value < current.value) current = current.left; if(value > current.value) current = current.right; } return false;};

Получите мин и макс.

Продолжайте двигаться влево до наименьшего значения или вправо к наибольшему.

BinarySearchTree.prototype.getMin = function(node){ if(!node) node = this.root; while(node.left) { node = node.left; } return node.value};
BinarySearchTree.prototype.getMax = function(node){ if(!node) node = this.root; while(node.right) { node = node.right; } return node.value;};

Удаление

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

BinarySearchTree.prototype.removeNode = function(node, value){ if(!node){   return null; } if(value === node.value){ // no children if(!node.left && !node.right) return null; // one child and it’s the right if(!node.left) node.right;// one child and it’s the left if(!node.right) node.left;  // two kids const temp = this.getMin(node.right); node.value = temp; node.right = this.removeNode(node.right, temp); return node; } else if(value < node.value) {     node.left = this.removeNode(node.left, value);     return node; } else  {     node.right = this.removeNode(node.right, value);     return node;   }};
BinarySearchTree.prototype.remove = function(value){ this.root = this.removeNode(this.root, value);};

Это работает так…

В отличие от deleteMin и deleteMax, где мы можем просто пройти весь путь влево или полностью и выбрать последнее значение, нам нужно удалить узел, а затем заменить его чем-нибудь. Это решение было разработано в 1962 году Т. Хиббардом. Мы учитываем случай, когда мы можем удалить узел только с одним дочерним или без всякого, это незначительно. Если нет детей, не беда. Если ребенок присутствует, он просто перемещается на одну вверх.

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

  1. Создайте значение temp и сохраните наименьший узел вправо. Это удовлетворяет свойство, что значение слева все еще меньше, а значение справа еще больше.
  2. Сбросьте значение узла к этой временной переменной
  3. Удалите правый узел.
  4. Затем мы сравниваем значение влево и вправо и определяем присвоенное значение.

Это лучше всего объяснить с помощью рисунка:

cEcyXZpZvRln6p7jzJq08lOJsORH6yA7Rd0T

Поиск

Существует два типа поиска: в глубину и ширину. Breadth First – это просто остановка на каждом уровне по пути вниз. Выглядит это так: начинаем с корня, потом левого ребенка, потом правого ребенка. Перейдите на следующий уровень, левый ребенок затем прав. Думайте об этом, как горизонтальное перемещение. Мы используем, я бы сказал, имитируем, очередь, чтобы помочь упорядочить процесс. Мы передаем функцию, потому что многократно мы хотим оперировать значением.

BinarySearchTree.prototype.traverseBreadthFirst = function(fn) { let queue = []; queue.push(this.root); while(!!queue.length) {   let node = queue.shift();   fn(node);   node.left && queue.push(node.left);   node.right && queue.push(node.right);  }}

Поиск в глубину подразумевает перемещение вниз по BST определенным способом: предварительно, inOrder или postOrder. Вскоре объясню отличия.

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

Теперь чем каждый отличается? Сначала отправим по заказу. Это должно быть само собой разумеющимся, но это не так. Мы имеем в виду в порядке вставки, от самого высокого до самого низкого или от самого низкого до самого высокого? Я просто хотел, чтобы вы подумали об этих вещах заранее. В этом случае, да, это означает от самого низкого к самому высокому.

предварительный заказ можно рассматривать как Отец, левый ребенок, потом правый ребенок.

послезаказ как Левый ребенок, правый ребенок, отец.

BinarySearchTree.prototype.traverseDFS = function(fn, method){ let current = this.root; if(!!method) this[method](current, fn); else this._preOrder(current, fn);};
BinarySearchTree.prototype._inOrder = function(node, fn){ if(!!node){ this._inOrder(node.left, fn); if(!!fn) fn(node); this._inOrder(node.right, fn); }};
BinarySearchTree.prototype._preOrder = function(node, fn){ if(node){ if(fn) fn(node); this._preOrder(node.left, fn); this._preOrder(node.right, fn); }};
BinarySearchTree.prototype._postOrder = function(node, fn){ if(!!node){ this._postOrder(node.left, fn); this._postOrder(node.right, fn); if(!!fn) fn(node); }};

Убедитесь, что BST заполнен

Помните из предыдущего, BST является полным, если каждый узел имеет ноль или два дочерних.

// a BST is full if every node has zero two children (no nodes have one child)
BinarySearchTree.prototype.checkIfFull = function(fn){ let result = true; this.traverseBFS = (node) => {   if(!node.left && !node.right) result = false;   else if(node.left && !node.right) result = false;  } return result;};

Получить высоту BST

Что значит получить высоту дерева? Почему это важно? Вот где Временная сложность (он же Big O) вступает в игру. Основные операции пропорциональны высоте дерева. Итак, как мы упоминали ранее, если мы ищем конкретное значение, количество операций, которые мы должны выполнить, уменьшается вдвое на каждом шагу.

Это значит, что если у нас есть буханка хлеба и разрезаем ее пополам, то разрезаем эту половину пополам и продолжаем делать это, пока не получим именно тот кусок хлеба, который мы хотим.

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

Постоянное время равно O(1). Независимо от того, насколько велик или мал входной размер, операция выполняется за одинаковый промежуток времени. Например, push() и pop() из массива являются постоянным временем. Поиск значения в HashTable является постоянным временем.

Я объясню больше об этом в следующей статье, но пока я хотел вооружить вас этими знаниями.

Вернуться к высоте.

У нас есть рекурсивная функция, и наш базовый случай: ‘если у нас нет узла, мы начинаем с this.root’. Это означает, что мы можем начать со значений ниже в дереве и получить высоту дерева.

Итак, если мы передаем this.root для начала, мы рекурсивно перемещаемся вниз по дереву и добавляем вызовы функций к стеку исполнения (другие статьи здесь). Когда мы дойдем до дна, стопка заполнена. Затем вызовы выполняются и мы сравниваем высоту левого и правого и увеличиваем его на единицу.

BinarySearchTree.prototype._getHeights = function(node){ if(!node) return -1; let left = this._getHeights(node.left); let right = this._getHeights(node.right); return Math.max(left, right) + 1;};
BinarySearchTree.prototype.getHeight = function(node){ if(!node) node = this.root; return this._getHeights(node);};

Наконец, сбалансированный

То, что мы делаем, это проверяем, заполнено ли дерево на каждом уровне, а на последнем уровне, заполнено ли оно слева направо.

BinarySearchTree.prototype._isBalanced = function(node){ if(!node) return true; let heightLeft = this._getHeights(node.left); let heightRight = this._getHeights(node.right); let diff = Math.abs(heightLeft — heightRight); if(diff > 1) return false; else return this._isBalanced(node.left) &&    this._isBalanced(node.right);};
BinarySearchTree.prototype.isBalanced = function(node){ if(!node) node = this.root; return this._isBalanced(node);};

Печать

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

BinarySearchTree.prototype.print = function() { if(!this.root) {   return console.log(‘No root node found’); } let newline = new Node(‘|’); let queue = [this.root, newline]; let string = ‘’; while(queue.length) {   let node = queue.shift();   string += node.value.toString() + ‘ ‘;   if(node === newline && queue.length) queue.push(newline);    if(node.left) queue.push(node.left);   if(node.right) queue.push(node.right);  } console.log(string.slice(0, -2).trim());};

Наш друг Console.log!! Поиграйте и экспериментируйте.

const binarySearchTree = new BinarySearchTree();binarySearchTree.insert(5);binarySearchTree.insert(3);
binarySearchTree.insert(7);binarySearchTree.insert(2);binarySearchTree.insert(4);binarySearchTree.insert(4);binarySearchTree.insert(6);binarySearchTree.insert(8);binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8
binarySearchTree.contains(4);
//binarySearchTree.printByLevel(); // => 5 \n 3 7 \n 2 4 6 8console.log('--- DFS inOrder');
binarySearchTree.traverseDFS(function(node) { console.log(node.value); }, '_inOrder'); // => 2 3 4 5 6 7 8
console.log('--- DFS preOrder');
binarySearchTree.traverseDFS(function(node) { console.log(node.value); }, '_preOrder'); // => 5 3 2 4 7 6 8
console.log('--- DFS postOrder');
binarySearchTree.traverseDFS(function(node) { console.log(node.value); }, '_postOrder'); // => 2 4 3 6 8 7 5
console.log('--- BFS');
binarySearchTree.traverseBFS(function(node) { console.log(node.value); }); // => 5 3 7 2 4 6 8
console.log('min is 2:', binarySearchTree.getMin()); // => 2
console.log('max is 8:', binarySearchTree.getMax()); // => 8
console.log('tree contains 3 is true:', binarySearchTree.contains(3)); // => true
console.log('tree contains 9 is false:', binarySearchTree.contains(9)); // => false
// console.log('tree height is 2:', binarySearchTree.getHeight()); // => 2
console.log('tree is balanced is true:', binarySearchTree.isBalanced(),'line 220'); // => true
binarySearchTree. remove(11); // remove non existing node
binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8
binarySearchTree.remove(5); // remove 5, 6 goes up
binarySearchTree.print(); // => 6 | 3 7 | 2 4 8
console.log(binarySearchTree.checkIfFull(), 'should be true');
var fullBSTree = new BinarySearchTree(10);
fullBSTree.insert(5).insert(20).insert(15).insert(21).insert(16).insert(13);
console.log(fullBSTree.checkIfFull(), 'should be true');
binarySearchTree.remove(7); // remove 7, 8 goes up
binarySearchTree.print(); // => 6 | 3 8 | 2 4
binarySearchTree.remove(8); // remove 8, the tree becomes unbalanced
binarySearchTree.print(); // => 6 | 3 | 2 4
console.log('tree is balanced is false:', binarySearchTree.isBalanced()); // => true
console.log(binarySearchTree.getHeight(),'height is 2')
binarySearchTree.remove(4);
binarySearchTree.remove(2);
binarySearchTree.remove(3);
binarySearchTree.remove(6);
binarySearchTree.print(); // => 'No root node found'
//binarySearchTree.printByLevel(); // => 'No root node found'
console.log('tree height is -1:', binarySearchTree.getHeight()); // => -1
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
console.log('---');
binarySearchTree.insert(10);
console.log('tree height is 0:', binarySearchTree.getHeight()); // => 0
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
binarySearchTree.insert(6);
binarySearchTree.insert(14);
binarySearchTree.insert(4);
binarySearchTree.insert(8);
binarySearchTree.insert(12);
binarySearchTree.insert(16);
binarySearchTree.insert(3);
binarySearchTree.insert(5);
binarySearchTree.insert(7);
binarySearchTree.insert(9);
binarySearchTree.insert(11);
binarySearchTree.insert(13);
binarySearchTree.insert(15);
binarySearchTree.insert(17);
binarySearchTree.print(); // => 10 | 6 14 | 4 8 12 16 | 3 5 7 9 11 13 15 17
binarySearchTree.remove(10); // remove 10, 11 goes up
binarySearchTree.print(); // => 11 | 6 14 | 4 8 12 16 | 3 5 7 9 x 13 15 17
binarySearchTree.remove(12); // remove 12; 13 goes up
binarySearchTree.print(); // => 11 | 6 14 | 4 8 13 16 | 3 5 7 9 x x 15 17
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
//console.log('tree is balanced optimized is true:', binarySearchTree.isBalancedOptimized()); // => true
binarySearchTree.remove(13); // remove 13, 13 has no children so nothing changes
binarySearchTree.print(); // => 11 | 6 14 | 4 8 x 16 | 3 5 7 9 x x 15 17
console.log('tree is balanced is false:', binarySearchTree.isBalanced()); // => false
// yields ...5 | 3 7 | 2 4 6 8--- DFS inOrder2345678--- DFS preOrder5324768--- DFS postOrder2436875--- BFS5372468min is 2: 2max is 8: 8tree contains 3 is true: truetree contains 9 is false: falsetree is balanced is true: true line 2205 | 3 7 | 2 4 6 86 | 3 7 | 2 4 8true 'should be true'true 'should be true'6 | 3 8 | 2 46 | 3 | 2 4tree is balanced is false: false2 'height is 2'No root node foundtree height is -1: -1tree is balanced is true: true---tree height is 0: 0tree is balanced is true: true10 | 6 14 | 4 8 12 16 | 3 5 7 9 11 13 15 1711 | 6 14 | 4 8 12 16 | 3 5 7 9 13 15 1711 | 6 14 | 4 8 13 16 | 3 5 7 9 15 17tree is balanced is true: true11 | 6 14 | 4 8 16 | 3 5 7 9 15 17tree is balanced is false: false

Временная сложность

1. Вставка O(log n)
2. Удаление O(log n)
3. Поиск O(log n)

Вау, это действительно много информации. Надеюсь, объяснения были максимально понятны и вступительны. Опять же письмо помогает мне закрепить понятие, и, как сказал Ричард Фейнман: «Когда один человек учит, двое учатся».

Ресурсы

Пожалуй, самый лучший ресурс для визуализации, обязательно используйте его:

Визуализация структуры данных
Университет компьютерных наук Дэвида Галлеса в Сан-Францискоwww.cs.usfca.eduBinaryTreeVisualiser – дерево двоичного поиска
Описание сайта здесьbtv.melezinek.czVisuAlgo – дерево двоичного поиска, дерево AVL
Двоичное дерево поиска (BST) — это двоичное дерево, в котором каждая вершина имеет только до 2 дочерних, что удовлетворяет свойству BST.visualgo.netШпаргалка по сложности алгоритма Big-O (Знай свои сложности!) @ericdrowell
Привет! Эта веб-страница включает пространственные и временные сложности обычных алгоритмов, используемых в информатике. Когда…www.bigocheatsheet.comАлгоритмы, 4-е издание Роберта Седжвика и Кевина Уэйна
Учебник «Алгоритмы», 4-е издание Роберта Седжвика и Кевина Уэйна исследует важнейшие алгоритмы и данные…algs4.cs.princeton.eduДвоичное дерево поиска — Википедия
В информатике отдельным типом являются двоичные деревья поиска (BST), которые иногда называют упорядоченными или отсортированными бинарными деревьями.en.wikipedia.org

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *