Perguntas e respostas mais comuns em entrevistas sobre árvores binárias [para calouros e experientes]

Introdução

As estruturas de dados são um dos conceitos mais fundamentais na programação orientada a objetos. Para explicar de forma simples, uma estrutura de dados é uma maneira particular de organizar dados em um computador para que possam ser processados ​​de forma eficaz. Existem várias estruturas de dados como pilhas, filas e árvores que têm suas próprias propriedades exclusivas.

As árvores nos permitem organizar os dados de forma hierárquica. Essa estrutura de dados é muito diferente de estruturas de dados lineares, como listas vinculadas ou matrizes. Uma árvore consiste em nós que carregam informações.

Uma árvore binária é um tipo especial de árvore que só pode ter até dois filhos. Isso significa que um nó específico em uma árvore binária não pode ter filho, um filho ou dois filhos, mas não mais. Uma árvore binária é uma estrutura de dados importante que pode nos permitir resolver problemas difíceis e construir códigos complexos.

Se você está se candidatando a um emprego como desenvolvedor Java ou engenheiro de software, sua entrevista pode conter várias perguntas em torno desse conceito. Muitas vezes, os candidatos acham difícil responder a perguntas com base em árvores binárias, árvores binárias de pesquisa e programas relacionados. Neste artigo, exploraremos algumas das perguntas de entrevista mais frequentes relacionadas a árvores binárias. Este artigo irá ajudá-lo a entender melhor o conceito e prepará-lo para que você possa conseguir o emprego dos seus sonhos!

Principais perguntas e respostas da entrevista de árvore binária

A seção a seguir contém um catálogo de perguntas e suas respostas esperadas com base no conceito de árvore binária.

1) O que é um nó folha?

Qualquer nó em uma árvore binária ou em uma árvore que não tenha filhos é chamado de nó folha.

2) O que é um nó raiz?

O primeiro nó ou o nó superior em uma árvore é chamado de nó raiz.

3) Como você encontra o menor ancestral comum (LCA) de uma árvore binária em Java?

Consideremos dois nós n1 e n2 que fazem parte de uma árvore binária.

O menor ancestral comum (LCA) de n1 e n2 é o ancestral compartilhado de n1 e n2 que está localizado mais distante da raiz.

Você pode seguir o seguinte método para encontrar o LCA.

1. a) Encontre um caminho do nó raiz até n1 e armazene-o em um array.
2. b) Encontre um caminho do nó raiz até n2 e armazene-o em um array.
3. c) Percorra ambos os caminhos até que o valor seja o mesmo em ambas as matrizes.

4) Como você verifica se uma determinada árvore binária é uma subárvore de outra árvore binária?

Considere que temos uma árvore binária T. Agora queremos verificar se uma árvore binária S é uma subárvore de T.

Para fazer isso, primeiro, tente verificar se você encontra um nó em T que também esteja em S.

Depois de encontrar esse nó comum, verifique se os seguintes nós também fazem parte de S.

Se sim, podemos dizer com segurança que S é uma subárvore de T.

Leitura obrigatória: ideias e tópicos de projetos de estrutura de dados

5) Como você encontra a distância entre dois nós em uma árvore binária?

Considere dois nós n1 e n2 que fazem parte de uma árvore binária.

A distância entre n1 e n2 é igual ao número mínimo de arestas que precisam ser percorridas para ir de um nó ao outro.

É importante observar que você percorre a menor distância entre os nós.

6) O que é uma árvore de busca binária?

Uma árvore de busca binária (BST) é um tipo especial de árvore binária na qual cada nó interno contém uma chave. Para uma árvore de busca binária, a regra é:

1. a) Um nó pode ter uma chave maior que todas as chaves na subárvore esquerda do nó.
2. b) Um nó pode ter uma chave menor que todas as chaves da subárvore direita do nó.

Assim, se n1 é um nó que tem uma chave 8, então cada nó na subárvore esquerda de n1 conterá chaves menores que 8, e cada nó na subárvore direita de n1 conterá chaves maiores que 8.

7) O que é uma árvore auto-equilibrada?

As árvores de busca binária auto-balanceadas mantêm automaticamente sua altura tão pequena quanto possível quando ocorrem operações como inserção e exclusão.

Para que um BST seja auto-equilibrado, é importante que ele siga consistentemente as regras do BST, de modo que a subárvore esquerda tenha chaves de menor valor enquanto a subárvore direita tenha chaves de alto valor.

Isso é feito usando duas operações:

- Rotação à esquerda

- Rotação direita

8) O que é uma árvore AVL?

A árvore AVL recebeu o nome de seus inventores: Adelson, Velski e Landis. Uma árvore AVL é uma árvore binária auto-balanceada que verifica a altura de sua subárvore esquerda e subárvore direita e garante que a diferença não seja maior que 1. Essa diferença é chamada de fator de equilíbrio

Assim, BalanceFactor = altura (subárvore esquerda) – altura (subárvore direita)

Se o fator de equilíbrio for maior que 1, a árvore será balanceada usando algumas das seguintes técnicas:

- Rotação à esquerda

- Rotação direita

- Rotação esquerda-direita

- Rotação direita-direita

Leia também: Classificação na estrutura de dados

9) Como você converte uma árvore binária em uma árvore de busca binária em Java?

A principal diferença entre uma árvore binária e uma árvore de busca binária é que o BST segue a subárvore esquerda deve ter valores de chave mais baixos e a subárvore direita deve ter a regra de valores de chave mais altos. Isso pode ser feito usando uma série de técnicas de travessia da seguinte forma:

1. Crie um array temporário que armazene o percurso inorder da árvore
2. Classifique a matriz temporária. Você pode usar qualquer algoritmo de classificação aqui.
3. Novamente execute uma travessia desordenada na árvore.
4. Copie os elementos do array um por um para cada nó da árvore.

10) Como você exclui um nó de uma árvore de pesquisa binária em Java?

A operação de exclusão de um BST pode ser complicada, pois suas propriedades precisam ser preservadas após a operação. Aqui está uma olhada em todos os três casos possíveis:

1. O nó a ser excluído é um nó folha.
   Simplesmente remova o nó.
2. O nó a ser removido tem um filho.

Nesse caso, copie o filho para o nó e exclua o filho.

1. O nó a ser removido tem dois filhos.

Neste caso, encontre o sucessor inorder do nó. Você pode então copiar seu conteúdo para o nó e excluir o sucessor inorder.

11) Qual é a estrutura de dados da árvore Red-Black?

A árvore Red-Black é um tipo especial de árvore de auto-equilíbrio que possui as seguintes propriedades:

1. Cada nó tem uma cor vermelha ou preta.
2. A raiz é sempre preta.
3. Um nó vermelho não pode ter um pai ou filho vermelho.
4. Cada caminho do nó raiz para um nó NULL tem o mesmo número de nós pretos.

Leitura obrigatória: ideias e tópicos de projetos de estrutura de dados

12) Como você descobre se duas árvores são idênticas?

Duas árvores binárias são idênticas se tiverem os mesmos dados e arranjo. Isso pode ser feito percorrendo ambas as árvores e comparando seus dados e arranjos.

Aqui está o algoritmo que pode nos permitir fazer isso:

1. Verifique os dados do nó raiz (dados da árvore1 ==dados da árvore2)
2. Verifique a subárvore esquerda recursivamente. call sameTree( tree1-> left subtree, tree2-> left subtree)
3. Da mesma forma, verifique a subárvore direita
4. se a,b,c são verdadeiros, return1

Checkout: Tipos de Árvore Binária

Pensamentos finais

Neste artigo, exploramos algumas das perguntas mais comuns da entrevista em árvore de busca binária. Explorar mais sobre estruturas de dados pode ajudá-lo a entender melhor a lógica e a programação. Você pode tentar ver os exemplos mencionados neste artigo e praticar alterando os valores para construir seus fundamentos. Com alguma prática, você estará em uma ótima posição para quebrar sua entrevista.

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.