Datastrukturer 101: Binært søgetræ

Sådan kombineres effektiviteten ved indsættelse af en sammenkædet liste og hurtig søgning i et ordnet array.

Hvad er et binært søgetræ?

Lad os starte med grundlæggende terminologi, så vi kan dele det samme sprog og undersøge relaterede begreber. For det første, hvad er de principper, der definerer et binært søgetræ?

* Herfra og ud vil jeg bruge "BST" for kortfattethed

En BST betragtes som en datastruktur, der består af noder , som f.eks. Sammenkædede lister . Disse noder er enten nul eller har referencer (links) til andre noder. Disse 'andre' noder er underordnede noder, kaldet en venstre knude og højre knude. Noder har værdier . Disse værdier bestemmer, hvor de er placeret inden for BST.

På samme måde som en linket liste henvises der til hver node kun af en anden node, dens overordnede (undtagen rodnoden). Så vi kan sige, at hver node i en BST i sig selv er en BST. Fordi længere nede i træet når vi en anden knude, og den knude har venstre og højre. Afhængigt af hvilken vej vi går, har den node derefter en venstre og en højre og så videre.

1. Den venstre knude er altid mindre end dens overordnede.

2. Den højre knude er altid større end dens overordnede.

3. En BST betragtes som afbalanceret, hvis hvert niveau i træet er fuldt udfyldt med undtagelse af det sidste niveau. På det sidste niveau fyldes træet fra venstre mod højre.

4. En perfekt BST er en, hvor den er både fuld og komplet (alle underordnede noder er på samme niveau, og hver node har en venstre og en højre undernode).

Hvorfor bruger vi dette?

Hvad er nogle virkelige eksempler på BST'er? Træer bruges ofte til søgning, spillogik, autofuldførelsesopgaver og grafik.

Hastighed. Som nævnt tidligere er BST en ordnet datastruktur. Efter indsættelse placeres noderne ordentligt. Denne iboende rækkefølge gør søgning hurtigt. Svarende til binær søgning (med en matrix, der er sorteret), skærer vi mængden af ​​data, der skal sorteres med halvdelen ved hvert pass. Antag for eksempel, at vi leder efter en lille node-værdi. Ved hvert pas fortsætter vi med at gå langs den venstre knude. Dette eliminerer automatisk halvdelen af ​​de større værdier!

I modsætning til et array lagres dataene også som reference. Når vi tilføjer datastrukturen, opretter vi et nyt stykke i hukommelsen og linker til det. Dette er hurtigere end at oprette et nyt array med mere plads og derefter indsætte data fra det mindre array til det nye, større.

Kort sagt, indsættelse, sletning og søgning er stjernerne for en BST

Nu hvor vi forstår principperne, fordelene og de grundlæggende komponenter i en BST, lad os implementere en i javascript.

API'en til en BST består af følgende: Indsæt, Indeholder, Få min, Få maks, Fjern knude, Kontroller, om fuld, er afbalanceret , og typerne af søgning - Dybde først (forudbestilling, indbestilling, postbestilling), bredde første søgning , og endelig få højde . Det er en stor API, tag det bare en sektion ad gangen.

Implementering

Konstruktøren

BST består af noder, og hver node har en værdi.

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

BST-konstruktøren består af en rodknude.

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 }

… så langt så godt.

Indskud

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

Lad os tilføje nogle flere værdier.

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

For en cool visualisering Gå her !!

Lad os pakke dette ud.

  1. Først videregiver vi en værdi og opretter en ny node
  2. Kontroller, om der er en rod, hvis ikke, skal du indstille denne nyoprettede node til rodnoden
  3. Hvis der er en rodnode, opretter vi en variabel, der er erklæret "aktuel", og indstiller dens værdi til rodnoden
  4. Hvis den nyoprettede node.value er mindre end rodnoden, bevæger vi os til venstre
  5. Vi sammenligner hele tiden denne node. Værdi med venstre noder.
  6. Hvis værdien er lille nok, og vi når et punkt, hvor der ikke er flere venstre noder, placerer vi denne vare her.
  7. Hvis node.value er større, gentager vi de samme trin som ovenfor, medmindre vi bevæger os langs højre.
  8. Vi har brug for pauseudtalelser, fordi der ikke er noget tælletrin for at afslutte while-sløjfen.

Indeholder

Dette er en ret ligetil tilgang.

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

Få min og få maks.

Fortsæt med at krydse venstre til den mindste værdi eller til højre for den største.

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

Fjernelse

Fjernelse af en node er den vanskeligste operation, fordi noder skal omordnes for at opretholde egenskaberne for en BST. Der er en sag, hvis en knude kun har et barn, og en sag, hvis der både er en venstre og en højre knude. Vi bruger den større hjælperfunktion til at løfte tunge løft.

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

Det fungerer sådan ...

I modsætning til deleteMin og deleteMax, hvor vi bare kan krydse hele vejen til venstre eller helt til højre og vælge den sidste værdi, skal vi tage en node ud og derefter erstatte den med noget. Denne løsning blev udviklet i 1962 af T. Hibbard. Vi tager højde for det tilfælde, hvor vi kan slette en node med kun et barn eller ingen, det er mindre. Hvis ingen børn, ikke noget problem. Hvis et barn er til stede, bevæger det sig bare et barn op.

Men med et knudepunkt, der er planlagt til at blive fjernet, og som har to børn, hvilket barn træder i stedet? Bestemt kan vi ikke flytte en større node ned. Så hvad vi gør er at erstatte det med sin efterfølger, den næste kingpin. Vi er nødt til at finde det mindste højre barn til højre, der er større end det venstre barn.

  1. Opret en temp-værdi, og gem den mindste node til højre. Hvad dette gør er at tilfredsstille egenskaben, at værdierne til venstre stadig er mindre, og værdierne til højre er stadig større.
  2. Nulstil nodens værdi til denne tempvariabel
  3. Fjern den højre knude.
  4. Derefter sammenligner vi værdier til venstre og højre og bestemmer den tildelte værdi.

Dette forklares bedst med et billede:

Søger

There are two types of search, Depth First and Breadth First. Breadth First is simply stopping at each level on the way down. It looks like this: we start at the root, then the left child, then the right child. Move to the next level, left child then right child. Think of this as moving horizontally. We employ, I should say simulate, a queue to help order the process. We pass a function, because many times we want to operate on a value.

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

Depth First Search involves moving down the BST in a specified manner, either, preOrder, inOrder, or postOrder. I’ll explain the differences shortly.

In the spirit of concise code, we have a basic traverseDepthFirst function and we pass a function and a method. Again the function implies that we want to do something to the values along the way, while the method is the type of search we wish to perform. In the traverseDFS, we have a fallback: preOrder search in place.

Now, how is each one different? First, let’s dispatch inOrder. It should be self-explanatory but it isn’t. Do we mean in order of insertion, in order of highest to lowest or lowest to highest? I just wanted you to consider these things beforehand. In this case, yes, it does mean lowest to highest.

preOrder can be thought of as Parent, Left Child, then Right child.

postOrder as Left Child, Right Child, Parent.

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

Check if the BST is full

Remember from earlier, a BST is full if every node has Zero or Two children.

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

Get Height of BST

What does it mean to get the height of a tree? Why is this important? This is where Time Complexity (aka Big O) comes into play. Basic operations are proportional to the height of a tree. So as we alluded to earlier, if we search for a particular value, the number of operations we have to do is halved on each step.

That means if we have a loaf of bread and cut it in half, then cut that half in half, and keep doing that till we get the exact piece of bread we want.

In computer science, this is called O(log n). We start with an input size of some sort, and over time that size gets smaller (kind of flattening out). A straight linear search is denoted as O(n), as the input size increases so does the time it takes to run operations. O(n) conceptually is a 45-degree line starting at origin zero on a chart and moving right. The horizontal scale represents the size of an input and the vertical scale represents the time it takes to complete.

Constant time is O(1). No matter how large or small the input size is, the operation takes place in the same amount of time. For example, push() and pop() off of an array are constant time. Looking up a value in a HashTable is constant time.

I will explain more about this in a future article, but I wanted to arm you with this knowledge for now.

Back to height.

We have a recursive function, and our base case is: ‘if we have no node then we start at this.root’. This implies that we can start at values lower in the tree and get tree sub-heights.

So if we pass in this.root to start, we recursively move down the tree and add the function calls to the execution stack (other articles here). When we get to the bottom, the stack is filled. Then the calls get executed and we compare the heights of the left and the heights of the right and increment by one.

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

Lastly, Is Balanced

What we are doing is checking if the tree is filled at every level, and on the last level, if it is filled left to right.

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

Print

Use this to visualize all the methods you see, especially depth first and breadth first traversals.

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

Our Friend Console.log!! Play around and experiment.

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

Time Complexity

1. Insertion O(log n)

2. Removal O(log n)

3. Search O(log n)

Wow, that is indeed a lot of information. I hope the explanations were as clear and as introductory as possible. Again, writing helps me solidify concepts and as Richard Feynman said, “When one person teaches, two learn.”

Resources

Probably the best resource for visualizing, definitely use it:

Data Structure Visualization

David Galles Computer Science University of San Franciscowww.cs.usfca.eduBinaryTreeVisualiser - Binary Search Tree

Site description herebtv.melezinek.czVisuAlgo - Binary Search Tree, AVL Tree

Et binært søgetræ (BST) er et binært træ, hvor hvert toppunkt kun har op til 2 børn, der tilfredsstiller BST-ejendom ... visualgo.net Big-O algoritmekompleksitet Snydeark (Kend dine kompleksiteter!) @Ericdrowell

Hej! Denne webside dækker plads og tid Big-O-kompleksiteter af almindelige algoritmer, der anvendes i datalogi. When ... www.bigocheatsheet.com Algorithms, 4. udgave af Robert Sedgewick og Kevin Wayne

Lærebogen Algoritmer, 4. udgave af Robert Sedgewick og Kevin Wayne undersøger de vigtigste algoritmer og data ... algs4.cs.princeton.edu Binært søgetræ - Wikipedia

I datalogi er binære søgetræer (BST), undertiden kaldet ordnede eller sorterede binære træer, en bestemt type ... da.wikipedia.org