Binary SearchYouTube↗  IA↗(long shot)
Education  128.6K views 0 likes 0 dislikes   26 Sep 2012
CS50 2.4M subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
[Powered by Google Translate] [Recherche binaire]
[Powered by Google Translate] [Ricerca binaria]
[Patrick Schmid - Université de Harvard]
[Patrick Schmid - Harvard University]
[C'est CS50. - CS50.TV]
[Questo è CS50. - CS50.TV]
>> Si je vous ai donné une liste de noms de personnages Disney dans l'ordre alphabétique
>> Se ti ho dato una lista dei nomi dei personaggi Disney in ordine alfabetico
et vous a demandé de trouver Mickey Mouse,
e ti ha chiesto di trovare Mickey Mouse,
comment feriez-vous pour cela?
come è possibile fare per fare questo?
Une façon évidente serait de parcourir la liste depuis le début
Un modo ovvio sarebbe quello di scorrere la lista dall'inizio
et vérifier chaque nom pour voir si c'est Mickey.
e controllare ogni nome per vedere se è Mickey.
Mais pendant que vous lisez Aladdin, Alice, Ariel, et ainsi de suite,
Ma come si legge Aladdin, Alice, Ariel, e così via,
vous vous rendrez vite compte que le démarrage sur le devant de la liste n'était pas une bonne idée.
si prende subito conto che a partire dalla parte anteriore della lista non era una buona idea.
Ok, peut-être vous devriez commencer à travailler à rebours à partir de la fin de la liste.
Ok, forse si dovrebbe iniziare a lavorare a ritroso dalla fine della lista.
Maintenant que vous lisez Tarzan, Stitch, Blanche-Neige, et ainsi de suite.
Ora si legge Tarzan, Stitch, Biancaneve, e così via.
Pourtant, cela ne semble pas être la meilleure façon de s'y prendre.
Eppure, questo non mi sembra il modo migliore per andare su di esso.
>> Eh bien, une autre façon que vous pourriez prendre pour ce faire est d'essayer d'affiner
>> Beh, un altro modo che si potrebbe fare per fare questo è quello di cercare di limitare
la liste des noms que vous avez à regarder.
l'elenco dei nomi che si deve guardare.
Puisque vous savez qu'ils sont dans l'ordre alphabétique,
Dal momento che si sa che sono in ordine alfabetico,
vous pouvez simplement regarder les noms dans le milieu de la liste
si può solo guardare i nomi al centro della lista
et vérifier si Mickey Mouse est avant ou après ce nom.
e verificare se Mickey Mouse è prima o dopo questo nome.
En regardant le nom de famille dans la deuxième colonne
Guardando il cognome nella seconda colonna
vous rendre compte que M pour Mickey vient après J pour Jasmine,
ti renderesti conto che M per Mickey viene dopo J per Jasmine,
si vous souhaitez tout simplement ignorer la première moitié de la liste.
in modo da dovreste semplicemente ignorare la prima metà della lista.
Ensuite, vous auriez probablement regarder le haut de la dernière colonne
Poi si sarebbe probabilmente guardare la parte superiore della colonna
et de voir qu'il commence par Raiponce.
e vedere che inizia con Rapunzel.
Mickey vient avant Rapunzel, dirait qu'on ne peut ignorer la dernière colonne ainsi.
Mickey viene prima di Raperonzolo, sembra che siamo in grado di ignorare l'ultima colonna pure.
Poursuite de la stratégie de recherche, vous verrez rapidement que Mickey
Proseguendo la strategia di ricerca, si prende subito vedere che Mickey
est dans la première moitié de la liste restante de noms
è nella prima metà della lista dei nomi rimanente
et enfin trouver Mickey caché entre Merlin et Minnie.
e, infine, trovare Mickey nascosto tra Merlino e Minnie.
>> Ce que vous venez de faire est essentiellement binaire de recherche.
>> Quello che hai appena fatto è stato fondamentalmente di ricerca binaria.
Comme ce nom l'indique, il effectue sa stratégie de recherche en quelques binaire.
Come il nome suggerisce, svolge la sua strategia di ricerca in pochi binario.
Qu'est-ce que cela signifie?
Che cosa significa?
Eh bien, étant donné une liste d'éléments triés, l'algorithme de recherche binaire prend une décision binaire -
Beh, data una lista di elementi ordinati, l'algoritmo di ricerca binaria prende una decisione binaria -
à gauche ou à droite, supérieure ou inférieure, avant ou après alphabétique - à chaque point.
sinistro o destro, superiore o inferiore, in ordine alfabetico prima o dopo - in ogni punto.
Maintenant que nous avons un nom qui va de pair avec cet algorithme de recherche,
Ora che abbiamo un nome che va di pari passo con questo algoritmo di ricerca,
Voyons un autre exemple, mais cette fois avec une liste de numéros triés.
Vediamo un altro esempio, ma questa volta con un elenco di numeri ordinati.
Disons que nous sommes à la recherche pour le numéro 144 dans la liste des numéros triés.
Dire che stiamo cercando il numero 144 in questo elenco di numeri ordinati.
Tout comme avant, nous trouvons que le nombre est au milieu -
Proprio come prima, troviamo il numero che sta in mezzo -
qui dans ce cas est de 13 - 144 et voir si est supérieur ou inférieur à 13.
che in questo caso è di 13 - 144 e vedere se è superiore o inferiore a 13.
Comme il est clairement supérieur à 13, on peut ignorer tout ce qui est 13 ou moins
Dal momento che è chiaramente superiore a 13, si può ignorare tutto ciò che è 13 o meno
et se concentrer uniquement sur la moitié restante.
e concentratevi solo sulla metà rimanente.
Puisque nous avons maintenant un nombre pair d'éléments à gauche,
Dal momento che ora abbiamo un numero pari di elementi a sinistra,
nous avons simplement choisir un numéro qui est proche de la moyenne.
semplicemente scegliere un numero che si trova vicino al centro.
Dans ce cas, nous choisissons 55.
In questo caso abbiamo scelto 55.
Nous aurions pu tout aussi bien choisi 89.
Avremmo potuto altrettanto facilmente scelto 89.
D'accord. Encore une fois, 144 est supérieur à 55, alors nous allons vers la droite.
Va bene. Anche in questo caso, 144 è maggiore di 55, così andiamo a destra.
Heureusement pour nous, le nombre du milieu prochaine est de 144,
Fortunatamente per noi, il numero medio successivo è 144,
celui que nous recherchons.
quello che stiamo cercando.
Ainsi, afin de trouver 144 en utilisant une recherche binaire, nous sommes en mesure de le trouver en seulement 3 étapes.
Quindi, al fine di trovare 144 con una ricerca binaria, siamo in grado di trovare in soli 3 passi.
Si nous avions utilisé la recherche linéaire ici, il nous aurait fallu 12 étapes.
Se avessimo utilizzato la ricerca lineare qui, ci avrebbe preso 12 passi.
En effet, depuis cette méthode de recherche de moitié le nombre d'éléments
È un dato di fatto, dal momento che questo metodo di ricerca dimezza il numero di articoli
il doit regarder à chaque étape, il va trouver l'élément qu'il est à la recherche
deve guardare ad ogni passo, si troverà la voce si è alla ricerca di
dans environ le logarithme du nombre d'éléments dans la liste.
in circa il logaritmo del numero di elementi nella lista.
Maintenant que nous avons vu 2 exemples, nous allons jeter un coup d'oeil à
Ora che abbiamo visto due esempi, diamo uno sguardo al
certains pseudo-code pour une fonction récursive qui implémente recherche binaire.
un po 'di pseudocodice per una funzione ricorsiva che implementa la ricerca binaria.
En partant du haut, nous voyons que nous devons trouver une fonction qui prend 4 arguments:
Partendo dall'alto, vediamo che dobbiamo trovare una funzione che accetta 4 argomenti:
clé, tableau, min et max.
chiave, array, min e max.
La clé, c'est le nombre que nous sommes à la recherche d', donc 144 dans l'exemple précédent.
La chiave è il numero che stiamo cercando, per cui 144 nel precedente esempio.
Array est la liste des numéros que nous recherchons.
Array è l'elenco dei numeri che stiamo cercando.
Min et max sont les indices des positions minimum et maximum
Min e max sono gli indici delle posizioni di minima e massima
que nous étudions actuellement.
che stiamo guardando.
Alors, quand nous commençons, min sera de zéro et max sera l'indice maximum de la matrice.
Così, quando si avvia, sarà zero min e max sarà massimo indice della matrice.
Comme nous l'limiter la recherche, nous mettrons à jour min et max
Come limitare la ricerca verso il basso, provvederemo ad aggiornare min e max
pour être juste la gamme que nous sommes toujours à la recherche po
essere proprio il campo che stiamo ancora cercando trovi
>> Passons à la partie intéressante premier.
>> Saltiamo alla parte prima e interessante.
La première chose à faire est de trouver le point milieu,
La prima cosa da fare è trovare il punto medio,
l'indice qui est à mi-chemin entre le mini et maxi du tableau que nous envisageons toujours.
l'indice che è a metà strada tra il minimo e il massimo della matrice che stiamo ancora valutando.
Ensuite, nous examinons la valeur du tableau à cet endroit mi-parcours
Poi consideriamo il valore della matrice in quella posizione punto centrale
et voir si le nombre que nous sommes à la recherche d'est inférieure à cette clé.
e vedere se il numero che stiamo cercando è inferiore a quella chiave.
Si le nombre est à cette position inférieure,
Se il numero in quella posizione è meno,
alors cela signifie que la clé est plus grand que tous les nombres à gauche de cette position.
allora significa che la chiave è più grande di tutti i numeri alla sinistra di tale posizione.
Ainsi, nous pouvons appeler la fonction de recherche binaire à nouveau,
Così possiamo chiamare la funzione di ricerca binaria di nuovo,
mais cette fois la mise à jour des valeurs minimum et maximum des paramètres de lire que la moitié
ma questa volta l'aggiornamento del minimo e massimo dei parametri di leggere solo la metà
qui est supérieure ou égale à la valeur que nous venons d'examiner.
che è maggiore o uguale al valore abbiamo appena visto.
D'autre part, si la clé est inférieur au nombre courant au milieu de la matrice,
D'altra parte, se la chiave è inferiore al numero nel punto centrale corrente dell'array,
nous voulons aller vers la gauche et ignorer tous les nombres supérieurs.
vogliamo andare a sinistra e ignorare tutti i numeri che sono maggiori.
Encore une fois, nous appelons binaire de recherche, mais cette fois avec la gamme des valeurs min et max à jour
Anche in questo caso, si chiama ricerca binaria, ma questa volta con la gamma di min e max aggiornato
pour inclure juste la moitié inférieure.
per includere solo la parte inferiore.
Si la valeur à mi-chemin de courant dans le réseau n'est pas
Se il valore nel punto centrale corrente nella matrice non è né
supérieur ni inférieur à la clé, il doit être égal à la clé.
maggiore né minore della chiave, allora deve essere uguale alla chiave.
Ainsi, nous pouvons simplement retourner l'indice milieu actuel, et nous avons fini.
Quindi, possiamo semplicemente restituire l'indice corrente punto medio, e abbiamo finito.
Enfin, ce contrôle est ici dans le cas où le nombre
Infine, questo controllo è qui per il caso che il numero
n'est pas réellement dans le tableau de nombres, nous sommes à la recherche.
in realtà non è nella matrice di numeri che stiamo cercando.
Si l'indice maximum de la plage que nous sommes à la recherche d'
Se l'indice massimo della gamma che stiamo cercando
est toujours inférieur au minimum, ce qui signifie que nous sommes allés trop loin.
è sempre inferiore al minimo, ciò significa che siamo andati troppo lontano.
Comme le nombre n'était pas dans le tableau d'entrée, nous renvoient -1
Dal momento che il numero non era nella matrice di input, ci restituisce -1
pour indiquer que rien n'a été trouvé.
per indicare che non è stato trovato.
>> Vous avez peut être remarqué que pour cet algorithme au travail,
>> Avrete notato che, per questo algoritmo al lavoro,
la liste des numéros doit être trié.
l'elenco dei numeri deve essere ordinato.
En d'autres termes, on ne peut que trouver 144 en utilisant la recherche binaire
In altre parole, si possono trovare solo 144 utilizzando la ricerca binaria
si tous les nombres sont triés du plus bas au plus élevé.
se tutti i numeri sono ordinati dal più basso al più alto.
Si ce n'était pas le cas, nous ne serions pas en mesure d'exclure la moitié des numéros à chaque étape.
Se questo non fosse il caso, non sarebbe in grado di escludere la metà dei numeri ad ogni passo.
Nous avons donc 2 options.
Quindi abbiamo 2 opzioni.
Soit on peut prendre une liste non triée et trier avant en utilisant la recherche binaire,
O si può prendere un elenco non ordinato e ordinare prima di usare la ricerca binaria,
ou nous pouvons faire en sorte que la liste des numéros est triée comme nous ajouter des numéros à elle.
o possiamo fare in modo che l'elenco dei numeri è ordinata come aggiungere numeri ad esso.
Ainsi, au lieu de trier juste au moment où nous devons rechercher,
Così, invece di ordinamento proprio quando dobbiamo cercare,
pourquoi ne pas garder la liste triée en tout temps?
perché non mantenere la lista ordinata in ogni momento?
>> Une façon de garder une liste de numéros triés tout en permettant
>> Un modo per mantenere un elenco di numeri ordinati consentendo allo stesso tempo
un pour ajouter ou déplacer des numéros de cette liste
uno per aggiungere o spostare i numeri dall'elenco
est d'utiliser ce qu'on appelle un arbre binaire de recherche.
è quello di utilizzare qualcosa che si chiama un albero binario di ricerca.
Un arbre binaire de recherche est une structure de données qui possède 3 propriétés.
Un albero binario di ricerca è una struttura dati che ha 3 proprietà.
En premier lieu, le sous-arbre gauche du noeud contient aucune seules valeurs qui sont inférieures à
In primo luogo, il sottoalbero sinistro di un nodo contiene solo i valori che sono meno
ou égale à la valeur du nœud.
o uguale al valore del nodo.
Deuxièmement, le sous-arbre droit d'un noeud ne contient que des valeurs qui sont supérieures à
Secondo, il sottoalbero destro di un nodo contiene solo valori che sono maggiori di
ou égale à la valeur du nœud.
o uguale al valore del nodo.
Et, enfin, les deux sous-arbres gauche et droit de tous les nœuds
E, infine, entrambi i sottoalberi sinistro e destro di tutti i nodi
sont aussi des arbres binaires de recherche.
sono anche alberi binari di ricerca.
Regardons un exemple avec les mêmes numéros que nous avons utilisés précédemment.
Vediamo un esempio con gli stessi numeri che abbiamo usato in precedenza.
Pour ceux d'entre vous qui n'ont jamais vu un arbre en informatique avant,
Per quelli di voi che non hanno mai visto un albero di informatica prima,
permettez-moi de commencer par vous dire qu'un arbre pousse vers le bas de l'informatique.
vorrei iniziare dicendo che un albero informatica cresce verso il basso.
Oui, contrairement aux arbres vous êtes habitués,
Sì, a differenza di alberi a cui siete abituati,
la racine d'un arbre de l'informatique est au sommet,
la radice di una struttura informatica è in alto,
et les feuilles sont en bas.
e le foglie sono in fondo.
Chaque petite boîte est appelée un nœud et les noeuds sont reliés les uns aux autres par des arêtes.
Ogni piccola scatola è detto nodo ei nodi sono collegati tra loro da bordi.
Ainsi, la racine de cet arbre est une valeur de nœud avec la valeur 13,
Quindi, la radice di questo albero è un valore nodo con il valore 13,
qui a 2 nœuds enfants avec les valeurs 5 et 34.
che ha 2 nodi bambini con i valori 5 e 34.
Un sous-arbre est l'arbre qui est formé juste en regardant une sous-section de l'arbre entier.
Un sottoalbero è l'albero che si forma solo guardando una sottosezione dell'intero albero.
>> Par exemple, le sous-arbre gauche du noeud 3 est l'arbre créé par les noeuds 0, 1, et 2.
>> Per esempio, il sottoalbero sinistro del nodo 3 è l'albero creato dai nodi 0, 1 e 2.
Donc, si nous revenons aux propriétés d'un arbre binaire de recherche,
Quindi, se torniamo alle proprietà di un albero binario di ricerca,
nous voyons que chaque nœud de l'arbre est conforme à toutes les 3 propriétés, à savoir,
si vede che ogni nodo dell'albero è conforme a tutti i 3 oggetti, vale a dire,
la sous-arborescence de gauche ne contient que des valeurs qui sont inférieures ou égales à la valeur du noeud;
il sottoalbero sinistro contiene solo i valori che sono inferiori o pari al valore del nodo;
le sous-arbre droit de tous les nœuds
il sottoalbero destro di tutti i nodi
ne contient que des valeurs qui sont supérieures ou égales à la valeur du noeud, et
contiene solo valori maggiori o uguali al valore del nodo, e
sous-arbres gauche et droit de tous les nœuds sont aussi des arbres binaires de recherche.
sottoalberi sinistro e destro di tutti i nodi sono anche alberi binari di ricerca.
Bien que cet arbre est différent, c'est un arbre binaire de recherche valide
Anche se questo albero un aspetto diverso, si tratta di un valido albero binario di ricerca
pour le même ensemble de nombres.
per la stessa serie di numeri.
En fait, il existe de nombreuses façons que vous pouvez créer
È un dato di fatto, ci sono molti modi possibili che si possono creare
un arbre binaire de recherche valable à partir de ces chiffres.
una valida ricerca albero binario da questi numeri.
Eh bien, revenons à la première que nous avons créé.
Bene, torniamo al primo che abbiamo creato.
Alors, que pouvons-nous faire avec ces arbres?
Che cosa possiamo fare con questi alberi?
Eh bien, nous pouvons très simplement trouver les valeurs minimales et maximales.
Beh, possiamo in modo molto semplice trovare i valori minimo e massimo.
Les valeurs minimales peuvent être trouvés en va toujours vers la gauche
I valori minimi possono trovare sempre andando a sinistra
jusqu'à ce qu'il n'y pas d'autres nœuds à visiter.
fino a quando non esistono altri nodi da visitare.
A l'inverse, pour trouver le maximum tout simplement descend vers la droite à chaque fois.
Al contrario, per trovare il massimo semplicemente scende a destra ogni volta.
>> Trouver tout autre numéro qui n'est pas le minimum ou le maximum
>> Trovare qualsiasi altro numero che non è il minimo o il massimo
est tout aussi facile.
è altrettanto facile.
Dire que nous sommes à la recherche pour le nombre 89.
Dire che stiamo cercando il numero 89.
Nous avons simplement vérifier la valeur de chaque nœud et allez vers la gauche ou vers la droite,
Abbiamo semplicemente controllare il valore di ogni nodo e di andare a sinistra oa destra,
selon que la valeur du noeud est inférieur ou supérieur à
a seconda che il valore del nodo è inferiore o superiore
celui que nous recherchons.
quello che stiamo cercando.
Donc, à partir de la racine de 13, nous voyons que 89 est plus grand,
Quindi, partendo dalla radice del 13, vediamo che 89 è maggiore,
et si nous allons vers la droite.
e così andiamo a destra.
Ensuite, nous voyons le nœud 34, et encore une fois nous allons à droite.
Poi vediamo il nodo per il 34, e di nuovo si va a destra.
89 est toujours supérieur à 55, donc nous continuons à aller vers la droite.
89 è ancora superiore a 55, quindi continuiamo a andare a destra.
Nous avons ensuite mis au point un nœud avec la valeur de 144 et allez vers la gauche.
Abbiamo quindi messo a punto un nodo con il valore di 144 e andate a sinistra.
Et voilà, 89 est juste là.
Ed ecco, 89 è proprio lì.
>> Une autre chose que nous pouvons faire est d'imprimer tous les numéros en effectuant un parcours infixe.
>> Un'altra cosa che possiamo fare è stampare tutti i numeri eseguendo un attraversamento in ordine simmetrico.
Un parcours infixe signifie tout imprimer dans le sous-arbre gauche
Un attraversamento in ordine simmetrico significa stampare tutto nel sottoalbero sinistro
suivie de l'impression elle-même le noeud
seguita da una stampa del nodo stesso
puis suivie par une impression tout dans le sous-arbre droit.
e poi seguita da una stampa tutto ciò che nel sottoalbero destro.
Par exemple, prenons notre arbre binaire de recherche favori
Per esempio, prendiamo il nostro preferito albero binario di ricerca
et imprimer les numéros dans l'ordre.
e stampare i numeri in modo ordinato.
Nous commençons à la racine de 13, mais avant l'impression 13, nous devons imprimer
Partiamo alla radice del 13, ma prima di stampare 13 si ha di stampare
tout dans le sous-arbre gauche.
tutto nel sottoalbero sinistro.
Donc, nous allons à 5. Nous devons encore aller plus loin dans l'arbre jusqu'à ce qu'on trouve le nœud le plus à gauche,
Quindi andiamo a 5. Dobbiamo ancora andare più in profondità nella struttura ad albero fino a trovare la più a sinistra del nodo,
qui est égale à zéro.
che è zero.
Après l'impression de zéro, nous remontons à la 1 et imprimer cela.
Dopo la stampa zero, torniamo alla 1 e la stampa che fuori.
Puis nous allons à la sous-arbre droit, qui est 2, et imprimer cela.
Poi andiamo al sottoalbero destro, che è 2, e la stampa che fuori.
Maintenant que nous avons terminé avec ce sous-arbre,
Ora che abbiamo finito con questo sottoalbero,
nous pouvons revenir à la 3 et l'imprimer.
siamo in grado di risalire al 3 e stamparlo.
Poursuivant back up, nous imprimons le 5 puis le 8.
Continuando il backup, stampiamo il 5 e poi il 8.
Maintenant que nous avons terminé l'ensemble du sous-arbre gauche,
Ora che abbiamo completato l'intero sottoalbero sinistro,
nous pouvons imprimer le 13 et commencer à travailler sur le sous-arbre droit.
siamo in grado di stampare il 13 e iniziare a lavorare sul sottoalbero destro.
Nous sautons jusqu'au 34, mais avant impression 34, nous devons imprimer son sous-arbre gauche.
Saltiamo giù a 34, ma prima di stampare 34 dobbiamo stampare il suo sottoalbero sinistro.
Donc, nous imprimons 21; puis nous arrivons à imprimer 34 et visiter son sous-arbre droit.
Così abbiamo stampare 21; poi si arriva a stampare 34 e visitare il suo sottoalbero destro.
Comme 55 n'a pas de sous-arbre gauche, nous l'imprimer et de continuer sur son sous-arbre droit.
Dal momento che 55 non ha sottoalbero sinistro, lo stampare e proseguire per il suo sottoalbero destro.
144 comporte un sous-arbre gauche, et ainsi nous imprimons le 89, suivi du 144,
144 ha un sottoalbero di sinistra, e quindi abbiamo stampare il 89, seguita dalla 144,
et enfin le nœud le plus à droite de la 233.
e infine il più a destra del nodo 233.
Il vous en avez, tous les nombres sont imprimées dans l'ordre du plus bas au plus élevé.
Il gioco è fatto, tutti i numeri vengono stampati in ordine dal più basso al più alto.
>> Ajouter quelque chose à l'arbre est relativement indolore ainsi.
>> L'aggiunta di qualcosa per l'albero è relativamente indolore pure.
Tout ce que nous avons à faire est de s'assurer que nous suivons 3 propriétés binaires de recherche arborescente
Tutto ciò che dobbiamo fare è fare in modo che seguiamo tre binari proprietà albero di ricerca
puis insérez la valeur là où il ya de l'espace.
e quindi inserire il valore in cui ci sia spazio.
Disons que nous voulons insérer la valeur de 7.
Diciamo che vogliamo inserire il valore di 7.
Depuis le 7 est inférieur à 13, on va vers la gauche.
Dal 7 è inferiore a 13, si va a sinistra.
Mais elle est supérieure à 5, donc nous traversons vers la droite.
Ma è maggiore di 5, quindi abbiamo attraversate a destra.
Comme il est inférieur à 8 et 8 est un noeud feuille, on ajoute 7 à la gauche de l'enfant 8.
Dal momento che è meno di 8 e 8 è un nodo foglia, si aggiungono 7 al bambino di sinistra 8.
Voila! Nous avons ajouté un certain nombre à notre arbre binaire de recherche.
Voila! Abbiamo aggiunto un numero al nostro albero binario di ricerca.
>> Si nous pouvons ajouter des choses, nous ferions mieux en mesure de supprimer les choses ainsi.
>> Se siamo in grado di aggiungere le cose, è meglio essere in grado di cancellare le cose pure.
Malheureusement pour nous, la suppression est un peu plus compliqué -
Purtroppo per noi, l'eliminazione è un po 'più complicata -
pas beaucoup, mais juste un peu.
non molto, ma solo un po '.
Il ya 3 différents scénarios que nous avons à examiner
Ci sono 3 diversi scenari che dobbiamo prendere in considerazione
lors de la suppression d'éléments d'arbres binaires de recherche.
quando si eliminano elementi da alberi binari di ricerca.
Tout d'abord, le cas le plus simple est que l'élément est un nœud feuille.
Primo, il caso più semplice è che l'elemento è un nodo foglia.
Dans ce cas, il suffit de le supprimer et continuer avec notre entreprise.
In questo caso, abbiamo semplicemente cancellare e andare avanti con la nostra attività.
Disons que nous voulons supprimer le 7 que nous venons d'ajouter.
Supponiamo di voler cancellare il 7 che abbiamo appena aggiunto.
Eh bien, il suffit de le trouver, retirez-le et c'est tout.
Beh, abbiamo semplicemente trovato, rimuoverlo, e questo è tutto.
Le cas suivant est de savoir si le nœud a seulement 1 enfant.
Il caso successivo è se il nodo ha solo 1 bambino.
Ici, nous pouvons supprimer le noeud, mais nous devons d'abord assurez-vous
Qui siamo in grado di eliminare il nodo, ma dobbiamo prima fare in modo
pour relier le sous-arbre qui est maintenant laissé orphelin
per collegare la sottostruttura che viene ora lasciato senza genitori
pour le parent du nœud que nous venons supprimé.
per il genitore del nodo che abbiamo appena cancellato.
Disons que nous voulons supprimer 3 de notre arbre.
Supponiamo di voler cancellare 3 dal nostro albero.
Nous prenons l'élément enfant de ce noeud et le fixer au parent du noeud.
Prendiamo l'elemento figlio di quel nodo e collegarlo al padre del nodo.
Dans ce cas, nous sommes en train de fixer la 1 à la 5.
In questo caso, stiamo ora collegando il 1 alla 5.
Cela fonctionne sans problème parce que nous savons, d'après la propriété d'arbre binaire de recherche,
Questo funziona senza un problema, perché si sa, in base alla proprietà albero binario di ricerca,
que tout, dans le sous-arbre gauche du 3 étant inférieur à 5.
che tutto il sottoalbero sinistro di 3 era inferiore a 5.
Maintenant que 3 sous-arbre est pris en charge, on peut le supprimer.
Ora che il 3 di sottostruttura è curato, siamo in grado di eliminarlo.
Le troisième et dernier cas est le plus complexe.
Il terzo caso, infine, è il più complesso.
C'est le cas lorsque le nœud que nous voulons supprimer a 2 enfants.
Questo è il caso quando il nodo si desidera eliminare ha 2 bambini.
Pour ce faire, nous devons d'abord trouver le nœud qui possède la plus grande valeur suivante,
Per fare questo, dobbiamo prima trovare il nodo che ha il valore più prossimo,
permuter les deux, puis supprimez le nœud en question.
scambiare i due, e quindi eliminare il nodo in questione.
Notez que le nœud qui possède la plus grande valeur suivante ne peut pas avoir 2 enfants se
Si noti il ​​nodo che ha il valore più grande non può avere 2 figli stessa
depuis son enfant de gauche serait un meilleur candidat pour le plus grand côté.
poiché il suo figlio sinistro sarebbe un candidato migliore a quello immediatamente superiore.
Par conséquent, la suppression d'un nœud avec 2 enfants revient à la permutation de 2 nœuds,
Di conseguenza, l'eliminazione di un nodo con 2 bambini ammonta a scambio di 2 nodi,
et en supprimant ensuite est traité par 1 des 2 règles précitées.
e quindi l'eliminazione è gestita da 1 delle 2 regole di cui sopra.
Par exemple, disons que nous voulons supprimer le nœud racine, 13.
Ad esempio, supponiamo di voler eliminare il nodo radice, 13.
La première chose à faire est de nous trouver la plus grande valeur suivant dans l'arborescence
La prima cosa che facciamo è trovare il valore più grande nella struttura ad albero
qui, dans ce cas, est de 21.
che, in questo caso, è di 21.
Nous avons ensuite permuter les 2 noeuds, soit 13 et 21 une feuille le nœud du groupe central.
Abbiamo poi scambiare i 2 nodi, facendo una foglia 13 e 21 il nodo del gruppo centrale.
Maintenant, nous pouvons simplement supprimer 13.
Ora possiamo semplicemente eliminare 13.
>> Comme mentionné précédemment, il existe de nombreuses façons de faire un arbre binaire de recherche valide.
>> Come accennato in precedenza, ci sono molti modi possibili per fare un valido albero binario di ricerca.
Malheureusement pour nous, certains sont pires que d'autres.
Purtroppo per noi, alcuni sono peggio di altri.
Par exemple, qu'est-ce qui se passe quand on construit un arbre binaire de recherche
Ad esempio, cosa succede quando si costruisce un albero binario di ricerca
à partir d'une liste triée des chiffres?
da una lista ordinata di numeri?
Tous les numéros sont simplement ajoutés à la droite à chaque étape.
Tutti i numeri sono appena aggiunto a destra ad ogni passo.
Quand nous voulons rechercher un numéro,
Quando vogliamo cercare un numero,
nous n'avons pas le choix, mais seulement à regarder à droite à chaque étape.
non abbiamo altra scelta, ma solo per guardare a destra ad ogni passo.
Ce n'est pas mieux que la recherche linéaire du tout.
Questo non è migliore di ricerca lineare affatto.
Bien que nous ne les couvrir ici, il existe d'autres, plus complexes,
Anche se non li coprire qui, ci sono altri, più complessi,
des structures de données qui font en sorte que cela n'arrive pas.
strutture di dati che fanno in modo che questo non accada.
Cependant, une chose simple qui peut être fait pour éviter cela est
Tuttavia, una cosa semplice che si può fare per evitare questo è
simplement modifier aléatoirement les valeurs d'entrée.
a poco a caso mischiare i valori di input.
Il est hautement improbable que par hasard une liste de numéros mélangées sont triées.
E 'altamente improbabile che per caso a caso un elenco di numeri mischiato è ordinato.
Si tel était le cas, les casinos ne voulait pas rester en affaires longtemps.
Se questo fosse il caso, i casinò non sarebbe rimasto in attività a lungo.
>> Il vous en avez.
>> Il gioco è fatto.
Vous savez maintenant sur la recherche binaire et les arbres binaires de recherche.
Ora si sa sulla ricerca binaria e alberi binari di ricerca.
Je suis Patrick Schmid, et c'est CS50.
Sono Patrick Schmid, e questo è CS50.
[CS50.TV]
[CS50.TV]
Une façon évidente serait d'examiner la liste de ... [bip]
Un modo ovvio sarebbe quello di scorrere la lista di ... [bip]
... Le nombre d'articles ... yep
... Il numero di elementi ... yep
[Rires]
[Ride]
... Poster nœud de 234 ... Augh.
Nodo di inviare ... 234 ... augh.
>> Yay! C'était -
>> Yay! Questo è stato -
Similar videos:

Binary Search
CS50
43.7K views 248 likes 7 dislikes 07 Oct 2015100% match










What is binary search
mycodeschool
637.6K views 5.2K likes 231 dislikes 23 Jan 2013100% match

C++ binary search
misterminich
15K views 74 likes 2 dislikes 03 Apr 2013100% match

what is an binary search
KV ALGORITHMS
5K views 12 likes 7 dislikes 23 Sep 2019100% match

Algorithms
CS50
215.4K views 0 likes 0 dislikes 16 Sep 201278% match










Computational Complexity
CS50
41.4K views 245 likes 12 dislikes 07 Oct 201571% match










一直認為是和棋的古譜：用AI繞60步，竟然能贏？強無敵！ 【象棋教室】
Chess classroom
10.5K views 161 likes 10 dislikes 26 Oct 202069% match

Operators
CS50
44.3K views 89 likes 4 dislikes 07 Oct 201569% match










暗黑高清版，有拼单乔丹之石的吗，我就录视频的时候用
Uncle_Arcade82
13.2K views 168 likes 3 dislikes 29 Oct 202069% match

Doubly-Linked Lists
CS50
20.4K views 107 likes 5 dislikes 14 Oct 201569% match










The Wonder of Calendar | कैलेंडर पर चर्चा | 3030 STEM | S01 E03
CCL IITGN
242K views 9.6K likes 460 dislikes 30 Aug 202069% match

Self-Driving Cars
CS50
10K views 85 likes 5 dislikes 10 Nov 201569% match










Confectioners made ​​Fomy Minnie and Donald
Arte en Tus Manos
190.9K views 2.3K likes 105 dislikes 09 May 201669% match

Loops
CS50
42.2K views 95 likes 2 dislikes 07 Oct 201569% match










Arrays
CS50
41.2K views 121 likes 5 dislikes 07 Oct 201568% match










Recommender Systems
CS50
82.2K views 1.3K likes 16 dislikes 10 Nov 201568% match










Hyundai i30N Hot Hatch Uphill Drive
zerotohundred
286.7K views 2.3K likes 247 dislikes 20 Aug 202068% match



How to control multiple Servo motors using one potentiometer with Arduino
Robojax
1.6K views 117 likes 1 dislikes 28 Oct 202068% match








双截龙，敌方小兵反水，你猜玛丽安用了什么手段
Uncle_Arcade82
5.2K views 72 likes 2 dislikes 01 Nov 202068% match

Merge Sort
CS50
38.2K views 180 likes 23 dislikes 07 Oct 201568% match










MVC
CS50
7.1K views 57 likes 2 dislikes 02 Nov 201568% match










「小白測評」 Mate40 Pro的8個熱點問題！風格大變今年不再爵士了~
Xiaobai's Tech Reviews
11.4K views 236 likes 14 dislikes 31 Oct 202067% match

小绿与梨花的决斗终于分出胜负，冠军渡表示很欣慰，但是四天王菊子就有点不爽了
Capijun
26K views 351 likes 11 dislikes 09 Dec 202067% match

Video Geçiş Efektlerini Uygulamalı Öğreniyoruz ve Editliyoruz/Broll/Premier Pro
Gokhan Karakas
3.2K views 225 likes 5 dislikes 10 Dec 202067% match

















暗黑高清版，米山和大菠萝同归于尽，地上装备是我的了
Uncle_Arcade82
21.6K views 196 likes 5 dislikes 10 Oct 202067% match

binary search in hindi
Sandeep Prasad
9.2K views 29 likes 7 dislikes 19 Sep 201367% match

暗黑高清版，刺客集不齐娜塔亚，穿套西岗也凑合
Uncle_Arcade82
17.7K views 153 likes 3 dislikes 03 Nov 202067% match

PHP for Web Development
CS50
15.6K views 114 likes 5 dislikes 16 Jun 201667% match










Another 15 Excel 2016 Tips and Tricks
Sele Training
382.4K views 5.7K likes 116 dislikes 28 May 201867% match



暗黑高清版，出了六件黄金，巴尔业内良心
Uncle_Arcade82
21.6K views 180 likes 7 dislikes 12 Oct 202067% match


Settings Privacy About Contact Donate