Важен принцип в компютърните науки е представянето на данни - което широко познаваме като структура на данните. Добре структурираните данни могат да помогнат за ефективното търсене. Но коя структура от данни? Ще работи ли свързан списък за всички видове търсения?

Докато търсим имаме две неща на наше разположение:

  1. Структура на данните —как са организирани данните
  2. Ключ за търсене — какво искаме да търсим

Първият фактор е структурата на данните. Трябва да изберем този, който прави търсенето по-ефективно. Имаме нужда от още две подробности, преди да изберем правилната структура на данните.

  1. Връзка между данните
  2. Идентифициране на границата на търсене с помощта на ключа за търсене

Връзката е един фактор при вземането на решение коя структура от данни ще отговаря на нашата цел. Нека проучим структура от данни, която работи чудесно, когато данните могат да се сравняват помежду си – тоест даден елемент е по-голям или по-малък от другия.

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

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

  • Лявото поддърво на възел съдържа само възли с ключове, по-малки от ключа на възела.
  • Дясното поддърво на възел съдържа само възли с ключове, по-големи от ключа на възела.
  • Всяко ляво и дясно поддърво също трябва да бъде двоично дърво за търсене.

Нека разгледаме списъка с числа — 60, 10, 25, 90, 75 и 0. Това може да бъде представено с помощта на дървото за двоично търсене по следния начин.

Сега, нека идентифицираме основните операции, които ще трябва да направим върху двоичното дърво за търсене.

Операции върху двоично дърво за търсене

Можем да вмъкнем елемент, да потърсим елемент (търсене) и да изтрием елемент в дървото.

Всяка операция има логаритмично време на изпълнение, защото за всяка операция ще разделим дървото наполовина на всяка стъпка. Ще научим подробно за всяка операция заедно с имплементацията в JavaScript. Нека направим основната настройка на кода.

Настройване на възела

Един възел Node за двоично дърво за търсене ще има три елемента за съхранение — стойността на възела, указателя за лявото поддърво и за дясното поддърво.

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

Ще използваме класа BinarySearchTree за внедряване на операциите — insert, lookup и remove в двоично дърво за търсене.

class BinarySearchTree {
     constructor() {
         this.root = null;
     }
      
     // Insert node to the tree.
     insert(value) {}
     
     // Search for a node in the tree.
     lookup (value) {}
 
     // Remove node from the tree.
     remove (value) {}
}

Вмъкване на възел

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

Нека вземем с елементите 9, 4, 6, 20, 78. Тъй като 9 е първият елемент, той става основният възел. 4 се сравнява с 9 — сравнението започва с основния възел. 4 е по-малко от 9 преместваме към левия указател на основния възел. В нашия случай няма такъв, така че вмъкваме нов възел със стойност 4.

За следващия елемент, 6 започваме отново от 9 и се движим наляво. Тъй като 6 е по-голямо от 4, ние се движим надясно. Тъй като няма възел, вмъкваме нов възел със стойност 6.

Алгоритъмът за вмъкване на всеки нов възел в двоично дърво има три стъпки:

  1. Ако няма възел, вмъкнете новия new.
  2. Ако има, сравнете стойностите. Ако новият възел има по-голяма стойност от текущия възел, отидете надясно, иначе се преместете наляво.
  3. Продължете към стъпка 1, докато не бъдат вмъкнати всички нови елементи.

Сега вече имаме добра представа за процеса на вмъкване, нека видим JavaScript кода за тази операция.

// Insert node to the tree.
insert(value) {
  const newNode = new Node(value);
  if (this.root === null) {             
    this.root = newNode;         
  } else {             
    let bFlag = true;
    let currentNode = this.root;              
    while (bFlag) {                 
      // Insert Left                 
      if (value < currentNode.value) {
        if (!currentNode.left) {  
          currentNode.left = newNode;
          bFlag = false;                     
        }                     
        currentNode = currentNode.left;                 
      } else if (value > currentNode.value) {                     
        // Insert Right                     
        if (!currentNode.right) {
          currentNode.right = newNode;
          bFlag = false;                     
      }                     
        currentNode = currentNode.right;                 
      } else if (value = currentNode.value) {
        // Duplicate Node Found
        bFlag = false;                 
      }             
    }         
  }     
}

Обърнете внимание на последната част от кода, където ако възелът бъде намерен, той прекратява цикъла while, като по този начин завършва процеса на вмъкване. Не може да има дублирани възли в двоичното дърво за търсене.

Намиране на възел

Намирането на възел в двоично дърво за търсене е подобно на процеса на вмъкване. Представете си, че възелът, който искате да намерите, е възелът, който искате да вмъкнете, или намирате възела, който търсите, или има null, който ви чака.

В дървото има 12 стойности и са необходими само максимум 3 стъпки за търсене на всяка стойност — трябва да се повтори, че връзката между възлите играе най-важната роля тук. Сега нека видим JavaScript кода за тази операция.

// Look for a node in the tree. 
    
lookup (value) {         
  let keepLooking = true;         
  let currentNode = this.root;              
  
  while (keepLooking && currentNode !== null) {             
    if (currentNode.value === value) {                 
      keepLooking = false;             
    } else if (currentNode.value > value) {
      currentNode = currentNode.left;             
    } else if (currentNode.value < value) {                 
      currentNode = currentNode.right;             
    }         
  }              
  
  if (currentNode && currentNode.value) {               
    return currentNode;         
  } else {             
    return null;
  }
}

Премахване на възел

Първата част от изтриването на възел е намирането му, което разгледахме в операцията за търсене по-горе. Втората част е да фиксирате указателите - запълнете празнотата, поддържайки баланса.

Нека видим някои примери, за да разберем различните случаи на употреба.

В първия набор от примери ще започнем с най-малките двоични дървета - изтриването на основния възел в следните случаи е лесно.

В този втори пример ще опитаме с малко по-голямо дърво. В този пример ще изтрием родителски възел, който не е основният възел.

Ето какво направихме -

  1. Изтрийте възел 1, който има само един десен дъщерен елемент
  2. Дясното дете, което е възел 3, става ляво дете на родителския възел или основния възел 4.

Нека преминем към друг пример.

Първата стъпка е ясна, изтрийте възел 4, но има и дясно, и ляво дете.

Тук попитайте това кой възел да запълни празнотата?

  • Възел 1 вече има десен дъщерен възел, той не може да заеме мястото на основния възел — къде ще отиде възел 3?
  • Възел 6 има ляв дъщерен възел, той не може да заеме мястото на коренния възел — къде ще отиде възел 5?
  • Възел 3 и възел 5 могат да работят. Ако преместим някое от тях, дървото все още е двоично дърво за търсене.

Можем да изведем факта, че за да запълним празнина, ни трябва или най-малкият възел, по-голям от възела, който трябва да бъде изтрит, или най-големият възел, по-малък от възела, който ще бъде изтрит. Това отнема известно време, за да се консумира (ако сте като мен), но след като идеята бъде разбрана, изглежда достатъчно просто, за да започнете да кодирате. Освен това, ако идеята е ясна, можем да й дадем име — празнината се запълва или с наследник, или с предшественик.

Нека видим още няколко примера.

Тук намерихме възела наследник на възел 9 и го преместихме на мястото му. Не е различно, ако не е основният възел. В следващия пример направихме същото за възел 20.

Нека видим изпълнението в JavaScript. На пръв поглед е много, но след като основната идея е ясна, има повече смисъл.

Простото не трябва да означава лесно — Филип Кийл

// Remove node from the tree.
remove (value) {
  if (!this.root) {
    return false;
  }

  let currentNode = this.root;
  let parentNode = null;

  while (currentNode) {
    if (value < currentNode.value) {
      parentNode = currentNode;
      currentNode = currentNode.left;
    } else if (value > currentNode.value) {
      parentNode = currentNode;
      currentNode = currentNode.right;
     } else if (currentNode.value === value) {
       //We have a match, get to work!

       //Option 1: No right child:
       if (currentNode.right === null) {
         if (parentNode === null) {
           this.root = currentNode.left;
         } else {
           //if parent > current value, make current left child a child of parent
           if (currentNode.value < parentNode.value) {
              parentNode.left = currentNode.left;
        
           //if parent < current value, make left child a right child of parent
           } else if (currentNode.value > parentNode.value) {
             parentNode.right = currentNode.left;
           }
         }
        
       //Option 2: Right child which doesnt have a left child
       } else if (currentNode.right.left === null) {
         currentNode.right.left = currentNode.left;
         if (parentNode === null) {
           this.root = currentNode.right;
         } else {
           //if parent > current, make right child of the left the parent
           if (currentNode.value < parentNode.value) {
             parentNode.left = currentNode.right;
            
           //if parent < current, make right child a right child of the parent
           } else if (currentNode.value > parentNode.value) {
             parentNode.right = currentNode.right;
           }
         }
        
       //Option 3: Right child that has a left child
       } else if (currentNode.left && currentNode.right) {
         //find the Right child's left most child
         let leftmost = currentNode.right.left;
         let leftmostParent = currentNode.right;
                    
         while (leftmost.left !== null) {
           leftmostParent = leftmost;
           leftmost = leftmost.left;
         }
        
         //Parent's left subtree is now leftmost's right subtree
         leftmostParent.left = leftmost.right;
         leftmost.left = currentNode.left;
         leftmost.right = currentNode.right;
        
         if (parentNode === null) {
           this.root = leftmost;
         } else {
           if (currentNode.value < parentNode.value) {
             parentNode.left = leftmost;
           } else if (currentNode.value > parentNode.value) {
             parentNode.right = leftmost;
           }
         }
        
       // Option 4: No left child but right child is there
       } else {
         if (parentNode === null) {
           this.root = currentNode.right;
         } else {
           if (currentNode.value < parentNode.value) {
             parentNode.left = currentNode.right;
           } else if (currentNode.value > parentNode.value) {
             parentNode.right = currentNode.right;
           }
         }
       }
       
      return true;
    }
  }
}

Единственото неприятно усещане тук е какво ще стане, ако с изтриването на възли дървото на двоичното търсене вече не е балансирано. Методът, който видяхме тук, е най-грубият начин за обработка на изтриването, той не балансира дървото. За да преодолеем това, можем да използваме AVL дърво — самобалансиращо се двоично дърво за търсене.



Малкото AVL дърво, което би могло
Колкото повече и повече научавам за компютърните науки, толкова повече и повече се убеждавам, че любимото ми нещо за...медиум .com



Това приключва операциите в дървото за двоично търсене и беше много, но за последно нека видим времевата сложност на всяка операция в дървото за двоично търсене.

Търсене = O(log N)

Поставете = O(log N)

Изтриване = O(log N)

където N е броят на възлите в дървото.

Всяка операция в дървото за двоично търсене е намалена наполовина, което ни дава страхотна производителност. Но имайте предвид нещото за структурите от данни — не съхранявайте обувките си в хладилника, всеки обект има свое собствено място.

Следователно следващия път, когато търсите двоично дърво за търсене, потърсете следния контролен списък.

✅ Сложността е O(log N), което е по-добре от O(n)

✅ Данните са подредени (възможно е сравнение)

✅ Гъвкав размер

❌ Без O(1) операции

Препратки

  1. Операция по изтриване в дървото за двоично търсене: наследник или предшественик — Stackoverflow
  2. Вижте дървото за двоично търсене в действие — visualgo.net
  3. Прочетете за дърветата — DS с JS — дървета