Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Concetto di albero di ricerca binario

L'albero di ricerca binario, noto anche come albero di ordinamento binario o albero di ricerca binario, è un tipo di albero binario che presenta le seguenti tre caratteristiche.

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。
1
2
3

Per dirla semplicemente, tutti i nodi di questo albero binario soddisfano: figlio sinistro < nodo genitore < figlio destro.

Operazioni sull'albero di ricerca binario

Ricerca nell'albero di ricerca binario

La ricerca in un albero di ricerca binario è in qualche modo simile alla ricerca binaria. Se la ricerca è più piccola del nodo radice, vai al sottoalbero di sinistra, e se è più grande del nodo radice, vai al sottoalbero di destra. Puoi cercare l'altezza un massimo di volte. Se arriva a vuoto e non viene trovata, significa che il valore non esiste.

Inserimento dell'albero di ricerca binario

Innanzitutto, segui il metodo di ricerca e inserisci il nodo quando è vuoto. Questo completa l'inserimento dell'albero di ricerca binario.

Eliminazione dell'albero di ricerca binario

L'eliminazione dei nodi nell'albero di ricerca binario deve essere eseguita in base alle diverse situazioni.

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。
1
2
3
4