de Kevin Turney

Structuri de date 101: copaci de căutare binari

Cum se combină eficiența inserării unei liste conectate și căutarea rapidă a unui tablou ordonat.

Structuri de date 101 Arborele de cautare binara
„Copac fără frunze pe deal” de Fabrice Villard pe Unsplash

Ce este un arbore de căutare binară?

Să începem cu terminologia de bază, astfel încât să putem împărtăși același limbaj și să investigăm conceptele conexe. În primul rând, care sunt principiile care definesc un arbore de căutare binară?

* De aici înainte voi folosi „BST” pentru scurtă durată

Un BST este considerat o structură de date formată din noduri, ca Liste conectate. Aceste noduri sunt fie nule, fie au referințe (legături) la alte noduri. Aceste „alte” noduri sunt noduri copil, numite nod stâng și nod drept. Nodurile au valori. Aceste valori determină unde sunt plasate în cadrul BST.

Similar cu o listă legată, fiecare nod este menționat de numai un alt nod, părintele său (cu excepția nodului rădăcină). Deci, putem spune că fiecare nod dintr-un BST este în sine un BST. Pentru că mai jos în copac, ajungem la un alt nod și acel nod are stânga și dreapta. Apoi, în funcție de ce drum mergem, acel nod are stânga și dreapta și așa mai departe.

1. Nodul din stânga este întotdeauna mai mic decât părintele său.

2. Nodul din dreapta este întotdeauna mai mare decât părintele său.

3. Un BST este considerat echilibrat dacă fiecare nivel al arborelui este complet umplut, cu excepția ultimului nivel. La ultimul nivel, arborele este umplut de la stânga la dreapta.

4. Un BST perfect este unul în care este atât complet, cât și complet (toate nodurile copil sunt la același nivel și fiecare nod are un nod copil stâng și unul drept).

1611891911 81 Structuri de date 101 Arborele de cautare binara

De ce am folosi asta?

Care sunt câteva exemple din lumea reală a BST? Copacii sunt adesea utilizați în căutare, logică de joc, sarcini de completare automată și grafică.

Viteză. După cum sa menționat mai devreme, BST este o structură de date ordonată. La inserare, nodurile sunt plasate în mod ordonat. Această ordine inerentă face căutarea rapidă. Similar cu căutarea binară (cu o matrice care este sortată), reducem cantitatea de date care trebuie sortate la jumătate la fiecare trecere. De exemplu, să presupunem că căutăm o valoare mică a nodului. La fiecare trecere, ne mișcăm de-a lungul nodului din stânga. Aceasta elimină automat jumătate din valorile mai mari!

De asemenea, spre deosebire de o matrice, datele sunt stocate prin referință. Pe măsură ce adăugăm la structura de date, creăm un nou fragment în memorie și îl conectăm la acesta. Acest lucru este mai rapid decât crearea unei matrice noi cu mai mult spațiu și apoi inserarea datelor din matricea mai mică în una nouă, mai mare.

Pe scurt, inserarea, ștergerea și căutarea sunt toate stelele pentru un BST

Acum că înțelegem principiile, beneficiile și componentele de bază ale unui BST, să implementăm unul în javascript.

API-ul pentru un BST constă din următoarele: Inserați, conține, obțineți min, obțineți maxim, eliminați nodul, verificați dacă este complet, este echilibratși tipurile de căutare – Adâncime întâi (preOrdine, inOrder, postOrder), Breadth First Search, și în cele din urmă Obțineți înălțimea. Acesta este un API mare, ia-l doar o secțiune la rând.

Implementare

Constructorul

BST este alcătuit din noduri și fiecare nod are o valoare.

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

Constructorul BST este alcătuit dintr-un nod rădăcină.

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 }

… Până acum, bine.

Inserare

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 } }

Să adăugăm câteva valori.

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 } } }

Pentru o vizualizare cool Du-te aici!!

Să despachetăm asta.

  1. În primul rând, trecem o valoare și creăm un nou nod
  2. Verificați dacă există o rădăcină, dacă nu, setați acest nod nou creat la nodul rădăcină
  3. Dacă există un nod rădăcină, creăm o variabilă declarată „curentă” și îi setăm valoarea la nodul rădăcină
  4. Dacă noul node.value creat este mai mic decât nodul rădăcină, ne vom deplasa la stânga
  5. Comparăm în continuare acest nod.valor cu nodurile din stânga.
  6. Dacă valoarea este suficient de mică și ajungem la un punct în care nu mai există noduri stânga, plasăm acest element aici.
  7. Dacă valoarea nodului este mai mare, repetăm ​​aceiași pași ca mai sus, cu excepția faptului că ne deplasăm de-a lungul dreapta.
  8. Avem nevoie de instrucțiunile de pauză, deoarece nu există un pas de numărare pentru a termina bucla while.

Conține

Aceasta este o abordare destul de simplă.

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;};

Ia Min și Ia Max.

Continuați să parcurgeți stânga până la cea mai mică valoare sau dreapta pentru cea mai mare.

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;};

Îndepărtarea

Eliminarea unui nod este cea mai dificilă operațiune, deoarece nodurile trebuie reordonate pentru a menține proprietățile unui BST. Există un caz dacă un nod are un singur copil și un caz dacă există atât un nod stâng, cât și unul drept. Folosim funcția de ajutor mai mare pentru a face greutăți.

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);};

Funcționează așa…

Spre deosebire de deleteMin și deleteMax, unde putem parcurge tot drumul spre stânga sau până la dreapta și să selectăm ultima valoare, trebuie să scoatem un nod și apoi să îl înlocuim cu ceva. Această soluție a fost dezvoltată în 1962 de T. Hibbard. Contabilizăm cazul în care putem șterge un nod cu un singur copil sau niciunul, acesta fiind minor. Dacă nu există copii, nicio problemă. Dacă este prezent un copil, copilul respectiv doar se deplasează în sus.

Dar cu un nod programat pentru a fi eliminat care are doi copii, care copil îi ia locul? Cu siguranță, nu putem muta un nod mai mare în jos. Deci, ceea ce facem este să-l înlocuim cu succesorul său, următorul rege. Trebuie să găsim cel mai mic copil din dreapta care este mai mare decât copilul din stânga.

  1. Creați o valoare temporară și stocați cel mai mic nod din dreapta sa. Ceea ce face este să satisfacă proprietatea că valorile din stânga sunt încă mai mici și valorile din dreapta sunt încă mai mari.
  2. Resetați valoarea nodului la această variabilă temp
  3. Eliminați nodul din dreapta.
  4. Apoi comparăm valorile din stânga și din dreapta și determinăm valoarea atribuită.

Acest lucru se explică cel mai bine cu o imagine:

1611891911 622 Structuri de date 101 Arborele de cautare binara

In cautarea

Există două tipuri de căutare, Adâncimea întâi și Lățimea întâi. Breadth First se oprește pur și simplu la fiecare nivel pe jos. Arată așa: începem de la rădăcină, apoi copilul stâng, apoi copilul potrivit. Treceți la nivelul următor, copilul stâng, apoi copilul drept. Gândiți-vă la acest lucru ca la mișcare orizontală. Folosim, ar trebui să spun simulează, o coadă pentru a ajuta la comandarea procesului. Trecem o funcție, pentru că de multe ori vrem să operăm pe o valoare.

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);  }}

Căutarea în adâncime implică deplasarea în jos a BST într-un mod specific, fie preOrder, inOrder, fie postOrder. Voi explica diferențele în scurt timp.

În spiritul codului concis, avem o funcție de bază traverseDepthFirst și trecem o funcție și o metodă. Din nou, funcția implică faptul că vrem să facem ceva valorilor pe parcurs, în timp ce metoda este tipul de căutare pe care dorim să o efectuăm. În traverseDFS, avem o soluție alternativă: căutare pre-comandă în loc.

Acum, ce diferă fiecare dintre ele? În primul rând, să trimitem comanda. Ar trebui să se explice de la sine, dar nu este. Înțelegem în ordinea inserării, în ordinea de la cel mai mare la cel mai mic sau de la cel mai mic la cel mai mare? Voiam doar să luați în considerare aceste lucruri în prealabil. În acest caz, da, înseamnă de la cel mai mic la cel mai mare.

pre-comanda poate fi gândit ca Părinte, copil stâng, apoi copil drept.

postOrder la fel de Copilul stâng, copilul drept, părinte.

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); }};

Verificați dacă BST este plin

Amintiți-vă de mai devreme, un BST este plin dacă fiecare nod are zero sau doi copii.

// 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;};

Obțineți înălțimea BST

Ce înseamnă să obții înălțimea unui copac? De ce este important acest lucru? Aici e locul Complexitatea timpului (aka Big O) intră în joc. Operațiile de bază sunt proporționale cu înălțimea unui copac. Așa cum am făcut aluzie mai devreme, dacă căutăm o anumită valoare, numărul de operații pe care trebuie să le facem este înjumătățit pe fiecare pas.

Asta înseamnă că, dacă avem o pâine și o tăiem în jumătate, apoi tăiem acea jumătate în jumătate și continuăm să facem asta până obținem bucata exactă de pâine pe care o dorim.

În informatică, aceasta se numește O (log n). Începem cu o dimensiune de intrare de un fel și, în timp, această dimensiune devine mai mică (un fel de aplatizare). O căutare liniară dreaptă este notată ca O (n), pe măsură ce dimensiunea intrării crește, la fel crește și timpul necesar pentru a rula operațiunile. O (n) conceptual este o linie de 45 de grade care începe la originea zero pe o diagramă și se deplasează spre dreapta. Scara orizontală reprezintă dimensiunea unei intrări, iar scala verticală reprezintă timpul necesar pentru finalizare.

Timpul constant este O (1). Indiferent cât de mare sau mică este dimensiunea de intrare, operația are loc în aceeași perioadă de timp. De exemplu, push () și pop () off dintr-o matrice sunt timp constant. Căutarea unei valori într-un HashTable este timp constant.

Voi explica mai multe despre acest lucru într-un articol viitor, dar am vrut să vă înarmez cu aceste cunoștințe deocamdată.

Înapoi la înălțime.

Avem o funcție recursivă, iar cazul nostru de bază este: „dacă nu avem nod atunci începem de la this.root”. Acest lucru implică faptul că putem începe cu valori mai mici în copac și să obținem subînălțimi de copac.

Deci, dacă trecem în this.root pentru a începe, ne deplasăm recursiv în jos în copac și adăugăm apelurile de funcții în stiva de execuție (alte articole aici). Când ajungem în partea de jos, stiva este umplută. Apoi apelurile sunt executate și comparăm înălțimile din stânga și înălțimile din dreapta și se măresc cu una.

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);};

În cele din urmă, este echilibrat

Ceea ce facem este să verificăm dacă arborele este umplut la fiecare nivel, iar la ultimul nivel, dacă este umplut de la stânga la dreapta.

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);};

Imprimare

Utilizați acest lucru pentru a vizualiza toate metodele pe care le vedeți, în special adâncimea întâi și lățimea primelor traversări.

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());};

Consola noastră de prieteni.log !! Joacă-te și experimentează.

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

Complexitatea timpului

1. Inserarea O (jurnal n)
2. Eliminarea O (jurnal n)
3. Căutați O (jurnal n)

Uau, asta este într-adevăr o mulțime de informații. Sper că explicațiile au fost cât mai clare și cât mai introductive. Din nou, scrisul mă ajută să consolidez concepte și, după cum spunea Richard Feynman, „Când o persoană predă, două învață”.

Resurse

Probabil cea mai bună resursă pentru vizualizare, folosiți-o cu siguranță:

Vizualizarea structurii datelor
David Galles Universitatea de Informatică din San Franciscowww.cs.usfca.eduBinaryTreeVisualiser – Arborele de căutare binară
Descrierea site-ului aicibtv.melezinek.czVisuAlgo – Arborele de căutare binar, Arborele AVL
Un copac de căutare binar (BST) este un copac binar în care fiecare vârf are doar până la 2 copii care îndeplinesc proprietatea BST …visualgo.netBig-O Algorithm Complexity Cheat Sheet (Cunoașteți complexitățile voastre!) @Ericdrowell
Bună! Această pagină web acoperă complexitatea spațială și temporală Big-O a algoritmilor obișnuiți utilizați în informatică. Când…www.bigocheatsheet.comAlgoritmi, ediția a IV-a de Robert Sedgewick și Kevin Wayne
Manualul Algoritmi, ediția a IV-a de Robert Sedgewick și Kevin Wayne analizează cei mai importanți algoritmi și date …algs4.cs.princeton.eduArborele de căutare binar – Wikipedia
În informatică, arborii binari de căutare (BST), numiți uneori arbori binari ordonați sau sortați, sunt un anumit tip …en.wikipedia.org