Compartilhamento de tecnologia

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

Conceito de árvore de pesquisa binária

A árvore de pesquisa binária, também conhecida como árvore de classificação binária ou árvore de pesquisa binária, é um tipo de árvore binária que possui as três características a seguir.

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

Simplificando, todos os nós desta árvore binária satisfazem: filho esquerdo <nó pai <filho direito.

Operações de árvore de pesquisa binária

Pesquisa em árvore de pesquisa binária

A pesquisa em uma árvore de pesquisa binária é um pouco semelhante à pesquisa binária. Se a pesquisa for menor que o nó raiz, vá para a subárvore esquerda e, se for maior que o nó raiz, vá para a subárvore direita. Você pode pesquisar a altura no máximo uma vez. Se chegar a vazio e não for encontrado, significa que o valor não existe.

Inserção de árvore de pesquisa binária

Primeiro, siga o método de pesquisa e insira o nó quando ele estiver vazio. Isso completa a inserção da árvore de pesquisa binária.

Exclusão da árvore de pesquisa binária

A exclusão de nós na árvore de pesquisa binária precisa ser feita de acordo com diferentes situações.

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