День 12. Деревья бинарного поиска

Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов, имеющая определенные ограничения. Он состоит из узлов, которые имеют отношение родитель/потомок. Верхний узел дерева называется «корневым» узлом, и это единственный узел без родителя. Каждый узел может иметь 0, 1 или 2 дочерних элемента, которые называются левыми или правыми дочерними элементами. Левый потомок всегда меньше своего родителя. И правильный ребенок всегда больше, чем его родитель. Если узел не имеет потомков, он называется «листом». Каждый дочерний узел также является бинарным деревом поиска. Это дает много возможностей для использования рекурсии, которые мы увидим позже.

class BinarySearchTree {
    constructor(key=null, value=null, parent=null) {
        this.key = key;
        this.value = value;
        this.parent = parent;
        this.left = null;
        this.right = null;
    }
    ...

Вставка в дерево — наша первая возможность использовать рекурсию. Допустим, у нас есть дерево с именем bst, и мы хотим вставить элемент. bst.insert(10).

начните с корня.
10 больше, чем корень (5), поэтому он будет правым потомком корня
если в позиции this.right уже есть узел, мы сравним его с 10 и решим
10 ‹ 19, поэтому 10 будет левым потомком 19
10 ‹ 15, поэтому 10 будет левым потомком 15
Поскольку нет левого потомка 15, мы вставим 10 как левого потомка.

insert(key, value) {
   // if no key found set root.key to key
   if (this.key === null) { 
     this.key = key;
   // I am ignoring values because the tree uses keys for it's
   // operation and the value could be anything 
    this.value = value;
  
   } else if (key <= this.key) { 
   // key, 10, is not less than root.key(5) skip to main else block
     if (this.left === null) { 
       this.left = new BinarySearchTree(key, value, this); 
     } else {
       this.left.insert(key, value); 
     }
   } else {
     if (this.right === null) { 
   // 19 is there so above statement is false so go to else
       this.right = new BinarySearchTree(key, value, this);
     } else {
       this.right.insert(key, value); 
       // this.right(19).insert(10) so start back up at the top
       // except now this.key === 19,
       // first time through, 'this' was the root, but now
       //recursively calling it with 19 as the node sets this to 19
       // so this time through you will hit that first block we                       //skipped when comparing 10 to 5
       // reach the next recursive call with this.left(15).insert(10)
       // this refers to 15
       //this.left === null so -> this.left = new BinarySearchTree(key, value, this);      
     }
   }
 }

Теперь дерево выглядит так:

Вызов кодирования:

Напишите функцию для определения высоты bst. Например, высота нашего бст выше равна 4.

function heighOfBst(bst){
  if(!bst) return 0;//base case 
  let leftHeight = heighOfBst(bst.left); 
  let rightHeight = heighOfBst(bst.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

Похоже, ничего не происходит, потому что код такой короткий, но это всего лишь рекурсия. leftHeight рекурсивно проходит через всю левую половину и возвращает итог из «return Math.max(leftHeight, rightHeight) + 1;», точно так же, как и rightHeight. В конце концов вы нашли конец каждой стороны и, по сути, вернете увеличенную сумму той стороны, которая продолжалась дольше. Краткий и смелый день… сексуальный.

День 12. Вывод:

Рекурсия рекурсия рекурсия рекурсия. Начать с базового случая является ключевым. Делать это шаг за шагом является ключевым. Знание ответа для того, чтобы знать ответ, является ключевым. Рекурсия в двух словах… или, лучше сказать, многослойный лук…?

День 12. Деревья бинарного поиска