Двоично дърво за търсене в JavaScript

Проблем

Индексът на цените се влачи

Филтърът „цена от … до …“ в магазина търси в индекс на цените, а не в целия каталог. Индексът е двоично дърво: всяка цена е възел, по-евтините са вляво, по-скъпите вдясно. При 1000 разбъркани цени дървото е с 22 нива, а записът и търсенето на всяка цена правят общо 22 990 сравнения: по около 23 на цена.

Тази сутрин доставчикът смени формата: фийдът идва подреден по цена. Същите 1000 цени, същият код, а сравненията стават 1 000 000: 43 пъти повече. Дървото вече е с 1000 нива.

Защо редът на входа има значение, след като цените са същите?

Идеята

По-малкото вляво, по-голямото вдясно

Двоично дърво за търсене (binary search tree, BST) е от възли с по две връзки, left и right. Правилото е едно: всичко в лявото поддърво на възел е по-малко от него, всичко в дясното е по-голямо.

Затова търсенето е двоично търсене без масив: при всеки възел сравняваш и прескачаш цяло поддърво. Добавянето върви по същия път, докато стигне празно място, и закача новия възел там. Нищо не се мести, както при вмъкване в подреден масив.

add(price) {
  let parent = null;
  let cur = this.root;
  let level = 1;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return false;
    parent = cur;
    cur = price < cur.price ? cur.left : cur.right;
    level++;
  }
  const node = new Node(price);
  if (parent === null) this.root = node;
  else if (price < parent.price) parent.left = node;
  else parent.right = node;
  this.size++;
  this.depth = Math.max(this.depth, level);
  return true;
}

add(price) {
  let parent = null;
  let cur = this.root;
  let level = 1;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return false;
    parent = cur;
    cur = price < cur.price ? cur.left : cur.right;
    level++;
  }
  const node = new Node(price);
  if (parent === null) this.root = node;
  else if (price < parent.price) parent.left = node;
  else parent.right = node;
  this.size++;
  this.depth = Math.max(this.depth, level);
  return true;
}

Стъпка по стъпка, с думи

Празен индекс на цените. Всяка цена слиза от корена: по-евтината наляво, по-скъпата надясно.
49 е първа. Дървото е празно и 49 става корен.
12 < 49: наляво. Там е празно и 12 става ляво дете на 49. 89 отива надясно.
24: по-евтина от 49 (наляво), по-скъпа от 12 (надясно). Две сравнения и е на ниво 3.
32: 49, 12, 24 и надясно. Три сравнения при 7 цени: всяко прескача цяло поддърво.
walk: лявото поддърво, възелът, дясното поддърво. Цените излизат подредени: 6 12 24 32 49 89 159.

Броят сравнения е колкото нивата по пътя. Ако дървото е ниско, около log₂ n нива, всяко търсене е O(log n).

Виж го

Своето дърво

Възелът пази цената и двете връзки:

class Node {
  constructor(price) {
    this.price = price;
    this.left = null;
    this.right = null;
  }
}

add слиза от корена и помни последния възел (parent). Щом стигне празно място, закача новия възел отляво или отдясно на parent. Същата цена втори път не влиза. level брои нивата по пътя, за да знае дървото колко е дълбоко:

add(price) {
  let parent = null;
  let cur = this.root;
  let level = 1;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return false;
    parent = cur;
    cur = price < cur.price ? cur.left : cur.right;
    level++;
  }
  const node = new Node(price);
  if (parent === null) this.root = node;
  else if (price < parent.price) parent.left = node;
  else parent.right = node;
  this.size++;
  this.depth = Math.max(this.depth, level);
  return true;
}

contains върви по същия път, само че не закача нищо:

contains(price) {
  let cur = this.root;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return true;
    cur = price < cur.price ? cur.left : cur.right;
  }
  return false;
}

Най-евтиното е най-вляво, най-скъпото най-вдясно (дървото не е празно):

min() {
  let node = this.root;
  while (node.left !== null) node = node.left;
  return node.price;
}

max() {
  let node = this.root;
  while (node.right !== null) node = node.right;
  return node.price;
}

Обхождане по ред (in-order): първо лявото поддърво, после възелът, после дясното. Така цените излизат подредени. Тук е с рекурсия, защото всяко поддърво е пак дърво:

sorted() {
  const out = [];
  this.walk(this.root, out);
  return out;
}

walk(node, out) {
  if (node === null) return;
  this.walk(node.left, out);
  out.push(node.price);
  this.walk(node.right, out);
}

const tree = new PriceTree();
for (const price of [49, 12, 89, 24, 6, 159, 32]) {
  tree.add(price);
}
console.log(`по ред: [${tree.sorted().join(", ")}]`);
console.log(`най-евтино: ${tree.min()}, най-скъпо: ${tree.max()}`);
for (const price of [32, 50]) {
  tree.compares = 0;
  const found = tree.contains(price);
  console.log(`${price}: ${found ? "да" : "не"}, сравнения: ${tree.compares}`);
}

по ред: [6, 12, 24, 32, 49, 89, 159]
най-евтино: 6, най-скъпо: 159
32: да, сравнения: 4
50: не, сравнения: 2

32 се намира за 4 сравнения: 49, 12, 24, 32. За 50 стигат 2: 49, после 89, а вляво на 89 няма нищо, значи 50 липсва.

Пробвай

Колко сравнения?

const tree = new PriceTree();
for (const price of [50, 30, 70, 20, 40, 60, 80]) {
  tree.add(price);
}
tree.compares = 0;
tree.contains(65);
console.log(tree.compares);

Отговор

Пробвай

Попълни

Най-евтината цена:

min() {
  let node = this.root;
  while (node. !== null) node = node.left;
  return node.price;
}

Идеята

Подреденият вход: дървото става верига

Обратно към фийда. Когато цените идват подредени, всяка нова е по-скъпа от всички досега. Тя минава надясно покрай всеки възел и се закача най-вдясно. Наляво не отива нищо, и дървото е верига: свързан списък с излишни празни връзки.

add(price) {
  let parent = null;
  let cur = this.root;
  let level = 1;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return false;
    parent = cur;
    cur = price < cur.price ? cur.left : cur.right;
    level++;
  }
  const node = new Node(price);
  if (parent === null) this.root = node;
  else if (price < parent.price) parent.left = node;
  else parent.right = node;
  this.size++;
  this.depth = Math.max(this.depth, level);
  return true;
}

Стъпка по стъпка, с думи

Фийдът на доставчика праща същите 7 цени, но подредени: 6, 12, 24, 32, 49, 89, 159.
Всяка нова цена е по-скъпа от всички досега и винаги отива надясно. Наляво не отива нищо.
Цена номер i минава през всички i преди нея: 0 + 1 + … + 6 = 21 сравнения. Дървото е верига от 7 нива.
contains(159) минава през всичките 7 възела, като свързан списък. При 1000 цени: 1000 нива.
Същите цени, балансирани: 3 нива вместо 7. AVL и червено-черните дървета пазят тази форма с ротации.

Цена номер i минава през i възела. За n цени това е 0 + 1 + … + (n − 1) при записа и още толкова плюс n при търсенето: точно n² сравнения. Това е същият капан като лошия пивот на quick sort: подреден вход и най-лошият случай.

Програмата на проблема: същите 1000 цени, веднъж подредени, веднъж разбъркани:

function shuffled(n) {
  const a = Array.from({ length: n }, (_, i) => 100 + i);
  let x = 2026;
  for (let i = n - 1; i > 0; i--) {
    x = (x * 48271) % 2147483647;
    const j = x % (i + 1);
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function report(prices) {
  const tree = new PriceTree();
  for (const p of prices) tree.add(p);
  for (const p of prices) tree.contains(p);
  return `дълбочина ${tree.depth}, сравнения ${tree.compares}`;
}

const feed = Array.from({ length: 1000 }, (_, i) => 100 + i);
console.log(`нарастващи: ${report(feed)}`);
console.log(`разбъркани: ${report(shuffled(1000))}`);

нарастващи: дълбочина 1000, сравнения 1000000
разбъркани: дълбочина 22, сравнения 22990

Пусни двата входа в браузъра:

Цените в разбъркан ред O(n log n)
Цените в нарастващ ред O(n²)

Алгоритъм	n = 10	n = 1000	n = 5000	n = 100 000
Цените в разбъркан ред	56	22 990	157 880	4 029 826
Цените в нарастващ ред	100	1 000 000	25 000 000	≈ 10 000 000 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При разбъркан вход едно търсене минава средно през около 2 · ln n − 3 възела (при 1000 цени около 12), което расте като log n, и всичко е O(n log n). При подреден е O(n²): при 1000 цени 1 000 000 сравнения срещу 22 990. Това е разликата между средния и най-лошия случай, и истинските данни често са точно подредени: по цена, по дата, по номер.

Идеята

Балансирано дърво

Да разбъркаш входа помага, но не винаги можеш: цените идват една по една, докато магазинът работи. Балансираното дърво се оправя само: след всяко добавяне проверява дали някой клон не е станал много по-дълъг от другия и го пренарежда. Така височината остава O(log n) при всякакъв вход, и всяко търсене, добавяне и махане е O(log n).

Пренареждането е ротация: възел и детето му си разменят местата. При дясна ротация лявото дете става родител, старият родител става негово дясно дете, а дясното поддърво на детето минава вляво на стария родител. Правилото „по-малкото вляво“ остава вярно, а един клон се скъсява с едно ниво.

По-точно, за любопитните

Дясна ротация около 32 във веригата 32 → 24 → 12 (всеки е ляво дете на предишния):

      32               24
     /                /  \
   24        →      12    32
   /
 12

24 става корен, 32 отива вдясно от него. Подреденият ред е същият: 12, 24, 32.

AVL (Адельсон-Велски и Ландис, 1962) пази във всеки възел височината на поддървото. Ако височините на двете деца се различат с повече от 1, прави една или две ротации. Дървото е много ниско (най-много около 1,44 · log₂ n), затова търсенето е бързо, но добавянето понякога прави повече работа.

Червено-черното дърво оцветява възлите и пази две правила: червен възел няма червено дете, и всеки път от корена до празно място минава през еднакъв брой черни. Това позволява един клон да е най-много два пъти по-дълъг от друг, затова височината е най-много 2 · log₂ n. При добавяне и махане стигат прекоцветяване и най-много две-три ротации.

Как е в езиците:

Java: TreeMap и TreeSet са червено-черни дървета. Освен get и put имат и подредените операции: firstKey, floorKey (най-голямото до дадено), subMap(от, до). Подреждат по Comparable или по Comparator, който подадеш.
C#: SortedSet<T> е червено-черно дърво, а SortedDictionary<TKey, TValue> е изградено върху него. SortedSet има Min, Max и GetViewBetween(от, до). Внимавай със SortedList<TKey, TValue>: то е два подредени масива, затова търсенето е O(log n), но добавянето в средата е O(n).
Python: вградено балансирано дърво няма. Модулът bisect търси в подреден списък за O(log n), но insort вмъква за O(n), защото мести елементите. Пакетът sortedcontainers (SortedList, SortedDict) се инсталира отделно и не е дърво: пази списък от подредени списъци с по около хиляда елемента.
JavaScript: вградено подредено дърво няма. Map и Set пазят реда на добавяне, не реда по стойност. Остават подреден масив с двоично търсене или библиотека.

Пробвай

Намери грешката

Някой е преписал add. Пет цени влизат, но обхождането показва само част от тях, а търсенето не намира 6 и 24:

add(price) {
  let parent = null;
  let cur = this.root;
  let level = 1;
  while (cur !== null) {
    this.compares++;
    if (price === cur.price) return false;
    parent = cur;
    cur = price < cur.price ? cur.left : cur.right;
    level++;
  }
  const node = new Node(price);
  if (parent === null) this.root = node;
  else if (price > parent.price) parent.left = node;
  else parent.right = node;
  this.size++;
  this.depth = Math.max(this.depth, level);
  return true;
}

const tree = new PriceTree();
for (const price of [49, 12, 89, 24, 6]) {
  tree.add(price);
}
console.log(`по ред: [${tree.sorted().join(", ")}]`);
console.log(`6: ${tree.contains(6) ? "да" : "не"}`);
console.log(`24: ${tree.contains(24) ? "да" : "не"}`);

по ред: [49, 6]
6: не
24: не

На кой ред е грешката?

Избери реда с грешката.

Упражнение

Цената спира да важи

Реши задачата в редактора си.

Махане от индекса. Добави remove(price), който връща дали е махнал цена. Има три случая:

възелът е лист: просто го откачаш;
има едно дете: детето заема мястото му;
има две деца: намери следващата по големина цена (най-лявата в дясното поддърво), сложи я на мястото на махнатата и махни нея от дясното поддърво. Тя няма ляво дете, затова това е някой от първите два случая.

Сложи цените 49, 12, 89, 24, 6, 159, 32 и махни 12 (две деца), 49 (коренът, две деца) и 70 (липсва):

-12: [6, 24, 32, 49, 89, 159]
-49: [6, 24, 32, 89, 159]
-70: няма
корен: 89

Още задачи

Цени в диапазон. Напиши between(from, to), който връща подредени цените от from до to, без да обхожда цялото дърво: не слизай наляво от възел, по-малък от from, нито надясно от възел, по-голям от to.
Най-доброто в бюджета. Напиши floor(budget): най-скъпата цена, която не е над бюджета. Сравни с floorKey в Java или GetViewBetween в C#.
Височина с рекурсия. Напиши height(node) като 1 + по-голямата от височините на двете деца. Пусни го върху веригата от 1000 подредени цени. Какво става в Python? А при 100 000 цени в Java?

Тест

Провери се

1. В дървото са цените 49, 12, 89, 24, 6, 159 и 32. Как излизат при обхождане по ред?49 12 6 24 32 89 15949 12 89 24 6 159 326 12 24 32 49 89 159

2. Защо хеш таблицата не става за „всички продукти между 20 и 60 €“, а дървото става?Защото хешът разпръсква близките цени по случайни кофи, а дървото ги пази подредениЗащото хеш таблицата е по-бавна при търсенеСтава и в двете еднакво

3. В обикновено двоично дърво влизат 1000 цени в нарастващ ред. Колко нива има дървото?500Около 101000

4. Кое е вярно за TreeMap в Java и SortedDictionary в C#?Двете са хеш таблици с подредени ключовеДвете са червено-черни дървета: височината остава O(log n) при всякакъв входСамо TreeMap е балансирано

Двоично дърво за търсене

Бисквитки