Cet article vous apporte une introduction (exemple de code) sur les arbres binaires (tas binaires) en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.
Arbre binaire
L'arbre binaire est une structure arborescente. Il se caractérise par le fait que chaque nœud a au plus deux nœuds de branche. Un arbre binaire se compose généralement de. nœud racine, nœud de branche et nœud feuille. Chaque nœud de branche est souvent appelé sous-arbre.
Nœud racine : le nœud supérieur de l'arbre binaire
Branche node : En plus du nœud racine et ayant des nœuds feuilles
nœud feuille : à part lui-même, il n'y a pas d'autres nœuds enfants
Termes courants
Dans un arbre binaire, nous utilisons souvent des nœuds parents et des nœuds enfants pour le décrire. Par exemple, 2 dans l'image est le nœud parent de 6 et 3, et inversement. 6 et 3 sont 2 nœuds enfants
Trois propriétés des arbres binaires
Au i-ème niveau de l'arbre binaire, il y a au la plupart des nœuds 2^i-1
Quand i=1, il n'y a qu'un seul nœud racine, 2^(i-1) = 2^0 = 1
L'arbre binaire de profondeur k est au plus Il y a 2^k-1 nœuds
Quand i=2, 2 ^k-1 = 2^2 - 1 = 3 nœuds
Pour tout arbre binaire T, si le nombre de points récapitulatifs est n0 et le nombre de nœuds de degré 2 (le nombre de sous-arbres est 2) est n2, alors n0=n2+1
Le nombre de nœuds d'un arbre est d'au moins 1, tandis que le nombre de nœuds d'un arbre binaire peut être 0
Le degré maximum (nombre de nœuds) d'un nœud dans un arbre n'est pas limité, alors que le degré maximum d'un nœud dans un arbre binaire est de 2. Les nœuds sont divisés en nœuds gauche et droit
Classification des arbres binaires
Arbre binaire complet : un arbre binaire de profondeur k et 2 ^ k - 1 nœuds est appelé un arbre binaire complet
Arbre binaire complet : un arbre binaire complet fait référence au dernier niveau. Un arbre binaire dans lequel le côté gauche est plein, le côté droit peut être plein ou non, et les niveaux restants sont pleins est appelé un arbre binaire complet (un l'arbre binaire complet est également un arbre binaire complet)
Représentation matricielle de l'arbre binaire
Utilisez un tableau pour représenter la structure de l'arbre binaire. Remplissez un ensemble de tableaux en commençant par le nœud racine de haut en bas et de gauche à droite, comme indiqué dans la figure ci-dessous
Grâce à la figure ci-dessus, nous pouvons analyser que l'arbre binaire complet représenté par le tableau a les propriétés suivantes : 
max tas (min tas)
Comme on peut le voir sur la photo ci-dessus :
Enregistrer la longueur du tableau
class Heap{
constructor(arr){
this.data = [...arr];
this.size = this.data.length;
}
}max-heapify consiste à mettre chaque élément qui le fait ne satisfait pas le tas maximum. Opération permettant d'ajuster les propriétés d'un nœud de branche.
Comme indiqué ci-dessus :
Ajustez le nœud de branche 2 (le nœud de branche 2 ne répond pas aux propriétés du tas maximum)
Par défaut, le nœud de branche est la valeur maximale
Comparez 2 avec la gauche et les branches droites, à partir de 2, 12, Trouvez la valeur maximale dans 5, puis échangez la position avec 2
Selon les propriétés du tas binaire mentionnées ci-dessus, obtenez la gauche le nœud et le nœud droit du nœud de branche 2 respectivement
Comparez trois nœuds et obtenez l'indice maximum de la valeur maximale
Si le nœud lui-même est la valeur maximale, arrêter l'opération
Échanger le nœud max avec le nœud parent
Répéter l'opération de l'étape 2, trouver la valeur maximale de 2, 4 et 7 et échangez-la avec 2
Récursif
maxHeapify(i) {
let max = i;
if(i >= this.size){
return;
}
// 当前序号的左节点
const l = i * 2 + 1;
// 当前需要的右节点
const r = i * 2 + 2;
// 求当前节点与其左右节点三者中的最大值
if(l this.data[max]){
max = l;
}
if(r this.data[max]){
max = r;
}
// 最终max节点是其本身,则已经满足最大堆性质，停止操作
if(max === i) {
return;
}
// 父节点与最大值节点做交换
const t = this.data[i];
this.data[i] = this.data[max];
this.data[max] = t;
// 递归向下继续执行
return this.maxHeapify(max);
}Nous pouvons voir que le tas juste initialisé est représenté par un tableau. À ce stade, il se peut qu'il ne satisfasse pas les propriétés d'un tas maximum ou d'un tas minimum. À ce stade, nous devrons peut-être construire le tas. tout un tas dans ce que nous voulons.
Nous avons effectué l'opération max-heapify ci-dessus, et max-heapify n'ajuste qu'un certain nœud de branche. Pour construire le tas entier en un tas maximum, vous devez effectuer une opération max-heapify sur tous les nœuds de branche. Dans la figure ci-dessous, nous devons effectuer des opérations max-hepify sur les quatre nœuds de branche 12, 3, 2 et 15 en séquence
Étapes spécifiques :
Trouver tous les nœuds de branche : Les propriétés du tas mentionnées ci-dessus mentionnent que le numéro de série du nœud feuille>=Math.floor(n/2), il est donc plus petit que le numéro de série de Math.floor(n/2) Ce sont tous des nœuds que nous devons ajuster.
Par exemple, le tableau affiché au milieu est [15,2,3,12,5,2,8,4,7] => (9/2 )=4 => Ceux dont l'indice est inférieur à 4 sont 15, 2, 3 et 12 (nœuds qui doivent être ajustés), tandis que 5, 2, 8, 4 et 7 sont des nœuds feuilles.
Effectuer l'opération maxHeapify sur tous les nœuds trouvés
rebuildHeap(){
// 叶子节点
const L = Math.floor(this.size / 2);
for(let i = L - 1; i>=0; i--){
this,maxHeapify(i);
}
} 
Tri maximal des tas, comme indiqué dans la figure ci-dessus :
Échanger les positions de tête et de queue
Le dernier élément est retiré du tas, ce qui équivaut à la taille 1 du tas
, puis une opération max-heapify est effectuée sur le nœud racine du tas
Répétez les trois étapes ci-dessus jusqu'à ce que size=0 (nous avons déjà effectué cette condition aux limites dans la fonction max-heapify)
sort() {
for(let i = this.size - 1; i > 0; i--){
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}L'insertion et la suppression de ceci est relativement simple, qui consiste à insérer et supprimer un tableau
insérer jusqu'à la fin
longueur du tas +1
Déterminer s'il s'agit toujours d'un tas maximum après l'insertion
Sinon, reconstruire le tas
insert(key) {
this.data[this.size] = key;
this.size++
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}Supprimer un élément du tableau
Longueur du tas -1
Déterminez s'il s'agit d'un tas
Sinon, refactorisez le tas
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}/**
* 最大堆
*/
function left(i) {
return i * 2 + 1;
}
function right(i) {
return i * 2 + 2;
}
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
class Heap {
constructor(arr) {
this.data = [...arr];
this.size = this.data.length;
}
/**
* 重构堆
*/
rebuildHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
this.maxHeapify(i);
}
}
isHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i++) {
const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {
return false;
}
return true;
}
}
sort() {
for (let i = this.size - 1; i > 0; i--) {
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
insert(key) {
this.data[this.size++] = key;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
/**
* 堆的其他地方都满足性质
* 唯独跟节点，重构堆性质
* @param {*} i
*/
maxHeapify(i) {
let max = i;
if (i >= this.size) {
return;
}
// 求左右节点中较大的序号
const l = left(i);
const r = right(i);
if (l this.data[max]) {
max = l;
}
if (r this.data[max]) {
max = r;
}
// 如果当前节点最大，已经是最大堆
if (max === i) {
return;
}
swap(this.data, i, max);
// 递归向下继续执行
return this.maxHeapify(max);
}
}
module.exports = Heap;La discussion sur le tas se termine ici. Le tas est relativement simple dans un arbre binaire et est souvent utilisé pour le tri et les files d'attente prioritaires. Le cœur du tas est l’opération max-heapify et les trois propriétés du tas.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
