Δομές δεδομένων 101: Δυαδικό δέντρο αναζήτησης

Πώς να συνδυάσετε την αποτελεσματικότητα της εισαγωγής μιας συνδεδεμένης λίστας και της γρήγορης αναζήτησης ενός παραγγελθέντος πίνακα.

Τι είναι το Δυαδικό Δέντρο Αναζήτησης;

Ας ξεκινήσουμε με τη βασική ορολογία, ώστε να μοιραστούμε την ίδια γλώσσα και να διερευνήσουμε σχετικές έννοιες. Πρώτον, ποιες είναι οι αρχές που ορίζουν ένα Δυαδικό Δέντρο Αναζήτησης;

* Από εδώ και πέρα ​​θα χρησιμοποιήσω το "BST" για συντομία

Ένα BST θεωρείται μια δομή δεδομένων που αποτελείται από κόμβους , όπως οι συνδεδεμένες λίστες . Αυτοί οι κόμβοι είναι είτε μηδενικοί είτε έχουν αναφορές (συνδέσεις) σε άλλους κόμβους. Αυτοί οι «άλλοι» κόμβοι είναι θυγατρικοί κόμβοι, που ονομάζονται αριστερός και δεξί κόμβος. Οι κόμβοι έχουν τιμές . Αυτές οι τιμές καθορίζουν πού τοποθετούνται εντός του BST.

Ομοίως με μια συνδεδεμένη λίστα, κάθε κόμβος αναφέρεται μόνο από έναν άλλο κόμβο, τον γονέα του (εκτός από τον ριζικό κόμβο). Έτσι μπορούμε να πούμε ότι κάθε κόμβος σε ένα BST είναι από μόνο του ένα BST. Επειδή πιο κάτω από το δέντρο, φτάνουμε σε έναν άλλο κόμβο και αυτός ο κόμβος έχει αριστερά και δεξιά. Στη συνέχεια, ανάλογα με τον τρόπο που πηγαίνουμε, αυτός ο κόμβος έχει αριστερά και δεξιά και ούτω καθεξής.

1. Ο αριστερός κόμβος είναι πάντα μικρότερος από τον γονικό του.

2. Ο σωστός κόμβος είναι πάντα μεγαλύτερος από τον γονικό του.

3. Ένα BST θεωρείται ισορροπημένο εάν κάθε επίπεδο του δέντρου γεμίζει πλήρως με την εξαίρεση του τελευταίου επιπέδου. Στο τελευταίο επίπεδο, το δέντρο γεμίζει αριστερά προς τα δεξιά.

4. Ένα τέλειο BST είναι εκείνο στο οποίο είναι τόσο πλήρες όσο και πλήρες (όλοι οι θυγατρικοί κόμβοι βρίσκονται στο ίδιο επίπεδο και κάθε κόμβος έχει έναν αριστερό και έναν δεξιό θυγατρικό κόμβο).

Γιατί θα το χρησιμοποιούσαμε;

Ποια είναι μερικά πραγματικά παραδείγματα BST's; Τα δέντρα χρησιμοποιούνται συχνά στην αναζήτηση, τη λογική του παιχνιδιού, τις εργασίες αυτόματης συμπλήρωσης και τα γραφικά.

Ταχύτητα. Όπως αναφέρθηκε προηγουμένως, το BST είναι μια δομημένη δομή δεδομένων. Κατά την εισαγωγή, οι κόμβοι τοποθετούνται με ομαλό τρόπο. Αυτή η εγγενής σειρά κάνει την αναζήτηση γρήγορη. Παρόμοια με τη δυαδική αναζήτηση (με έναν πίνακα που έχει ταξινομηθεί), κόβουμε τον όγκο των δεδομένων για ταξινόμηση κατά το ήμισυ σε κάθε πάσο. Για παράδειγμα, ας υποθέσουμε ότι ψάχνουμε μια μικρή τιμή κόμβου. Σε κάθε πάσο, συνεχίζουμε να κινούμαστε κατά μήκος του αριστερότερου κόμβου. Αυτό εξαλείφει τις μισές μεγαλύτερες τιμές αυτόματα!

Επίσης, σε αντίθεση με έναν πίνακα, τα δεδομένα αποθηκεύονται με αναφορά. Καθώς προσθέτουμε στη δομή δεδομένων, δημιουργούμε ένα νέο κομμάτι στη μνήμη και συνδέουμε με αυτήν. Αυτό είναι ταχύτερο από τη δημιουργία ενός νέου πίνακα με περισσότερο χώρο και στη συνέχεια την εισαγωγή των δεδομένων από τον μικρότερο πίνακα στο νέο, μεγαλύτερο.

Με λίγα λόγια, η εισαγωγή, η διαγραφή και η αναζήτηση είναι όλα τα αστέρια για ένα BST

Τώρα που κατανοούμε τις αρχές, τα οφέλη και τα βασικά στοιχεία ενός BST, ας το εφαρμόσουμε σε javascript.

Το API για ένα BST αποτελείται από τα ακόλουθα: Εισαγωγή, Περιέχει, Λήψη ελάχιστου, Λήψη μέγιστου, Κατάργηση κόμβου, Έλεγχος εάν είναι πλήρες, Ισορροπημένο και οι τύποι αναζήτησης - Πρώτο βάθος (preOrder, inOrder, postOrder), Breadth First Search , και τέλος, αποκτήστε ύψος . Αυτό είναι ένα μεγάλο API, απλώς πάρτε ένα τμήμα κάθε φορά.

Εκτέλεση

Ο κατασκευαστής

Το BST αποτελείται από κόμβους και κάθε κόμβος έχει τιμή.

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

Ο κατασκευαστής BST αποτελείται από έναν ριζικό κόμβο.

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 }

… μέχρι εδώ καλά.

Εισαγωγή

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

Ας προσθέσουμε μερικές ακόμη τιμές.

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

Για μια δροσερή απεικόνιση Πηγαίνετε εδώ !!

Ας αποσυμπιέσουμε αυτό.

  1. Αρχικά, περνάμε μια τιμή και δημιουργούμε έναν νέο κόμβο
  2. Ελέγξτε αν υπάρχει ρίζα, αν όχι, ορίστε αυτόν τον κόμβο που δημιουργήθηκε πρόσφατα στον ριζικό κόμβο
  3. Εάν υπάρχει ριζικός κόμβος, δημιουργούμε μια μεταβλητή που δηλώνεται "τρέχουσα" και θέτουμε την τιμή της στον ριζικό κόμβο
  4. Εάν το node.value που δημιουργήθηκε πρόσφατα είναι μικρότερο από τον ριζικό κόμβο, θα κινηθούμε αριστερά
  5. Συνεχίζουμε τη σύγκριση αυτού του node.value με τους αριστερούς κόμβους.
  6. Εάν η τιμή είναι αρκετά μικρή και φτάσουμε σε ένα σημείο όπου δεν υπάρχουν πλέον αριστεροί κόμβοι, τοποθετούμε αυτό το αντικείμενο εδώ.
  7. Εάν η τιμή node.value είναι μεγαλύτερη, επαναλαμβάνουμε τα ίδια βήματα όπως παραπάνω, εκτός εάν κινούμαστε προς τα δεξιά.
  8. Χρειαζόμαστε τις δηλώσεις διακοπής επειδή δεν υπάρχει κανένα μέτρο για τον τερματισμό του loop loop.

Περιέχει

Αυτή είναι μια αρκετά απλή προσέγγιση.

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

Λάβετε Ελάχ.

Συνεχίστε να περνάτε αριστερά στη μικρότερη τιμή ή δεξιά για τη μεγαλύτερη.

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

Μετακίνηση

Removing a node is the trickiest operation, because nodes have to be reordered to maintain the properties of a BST. There is a case if a node has only one child and a case if there is both a left and a right node. We use the larger helper function to do the heavy lifting.

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

It works like this…

Unlike deleteMin and deleteMax, where we can just traverse all the way left or all the way right and pick off the last value, we have to take out a node and then replace it with something. This solution was developed in 1962 by T. Hibbard. We account for the case where we can delete a node with only one child or none, that’s minor. If no children, no problem. If a child is present, that child just moves up one.

But with a node scheduled to be removed that has two children, which child takes its place? Certainly, we can’t move a larger node down. So what we do is replace it with its successor, the next kingpin. We have to find the smallest right child on the right that is larger than the left child.

  1. Create a temp value and store the smallest node on its right. What this does is satisfy the property that values to the left are still smaller and values to the right are still greater.
  2. Reset the node’s value to this temp variable
  3. Remove the right node.
  4. Then we compare values on the left and the right and determine the assigned value.

This is best explained with a picture:

Searching

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

Το Δυαδικό Δέντρο Αναζήτησης (BST) είναι ένα δυαδικό δέντρο στο οποίο κάθε κορυφή έχει μόνο έως 2 παιδιά που ικανοποιούν την ιδιοκτησία BST… visualgo.net Big-O Algorithm Complexity Cheat Sheet (Know Your Th complexities!) @Ericdrowell

Γεια σου! Αυτή η ιστοσελίδα καλύπτει το διάστημα και το χρόνο πολυπλοκότητες των κοινών αλγορίθμων που χρησιμοποιούνται στην Επιστήμη των Υπολογιστών. Όταν… www.bigocheatsheet.com Αλγόριθμοι, 4η έκδοση των Robert Sedgewick και Kevin Wayne

Το Αλγόριθμοι του εγχειριδίου, 4η έκδοση των Robert Sedgewick και Kevin Wayne ερευνά τους πιο σημαντικούς αλγόριθμους και δεδομένα… algs4.cs.princeton.edu Δυαδικό δέντρο αναζήτησης - Wikipedia

Στην επιστήμη των υπολογιστών, τα δέντρα δυαδικής αναζήτησης (BST), που μερικές φορές ονομάζονται δυαδικά δέντρα ταξινομημένα ή ταξινομημένα, είναι ένας συγκεκριμένος τύπος… en.wikipedia.org