"Olá, amigo!"
"Olá, Rishi!"
"Encontrei minhas anotações antigas ali e preparei um material interessante para você. Acho que vai se interessar em ouvi-lo."
"Vamos ouvir. Você sempre encontra algo interessante que depois se mostra muito útil."
"OK. Hoje eu quero falar sobre árvores , então vou começar com gráficos ."
" Um gráfico é um sistema de pontos e linhas que os conectam. Os pontos são chamados de vértices do gráfico e as linhas são chamadas de arestas do gráfico. Por exemplo:"
"Um gráfico é muito conveniente para usar como um modelo matemático para vários processos e tarefas do mundo real. Muitas tarefas e algoritmos diferentes foram inventados para gráficos, então eles são usados com bastante frequência."
"Por exemplo, suponha que os vértices sejam cidades e as arestas sejam estradas. Então, procurar a estrada mais curta entre as cidades torna-se: «dado um gráfico, encontre o caminho mais curto entre dois vértices». "
"Mas o caminho de A para B nem sempre é o mesmo que o caminho de B para A. Portanto, às vezes é preferível ter duas linhas diferentes. Para fazer isso, as linhas (bordas do gráfico) são substituídas por setas. Em ou seja, o gráfico pode ter duas setas: uma de A para B e outra de B para A."
"Se o gráfico usa setas, ele é chamado de gráfico direcionado ; se tiver apenas linhas, é chamado de gráfico não direcionado ."
"Cada vértice pode ter seu próprio número de arestas. Um vértice também pode não ter arestas. Por outro lado, um vértice pode ser conectado por arestas a todos os outros vértices. Se cada par de vértices em um grafo é conectado por uma aresta, então é chamado de grafo completo. "
"Se você pode usar arestas para alcançar cada vértice em um grafo, então ele é chamado de grafo conectado . Um grafo que tem três vértices separados e nenhuma aresta ainda é um grafo, mas nós o chamamos de grafo desconectado ."
"Para formar um gráfico conectado a partir de N vértices, você precisa de pelo menos N-1 arestas. Esse tipo de gráfico é chamado de árvore."
"Além disso, geralmente um vértice é escolhido para ser a raiz da árvore e os demais são declarados como ramos. Os ramos das árvores que não possuem seus próprios ramos são chamados de folhas . Por exemplo:"
"Se cada elemento da árvore tiver dois filhos, então é chamada de árvore binária . Em outras palavras, pode haver 0 ou 2 ramificações. Você pode ver uma árvore binária no canto superior direito."
" Uma árvore é chamada de árvore binária completa quando cada ramo tem 2 filhos e todas as folhas (vértices sem filhos) estão na mesma linha."
"Por exemplo:"
"Por que essas árvores são necessárias?"
"Oh, as árvores são usadas em muitos lugares. Em geral, as árvores binárias são dados estruturados classificados."
"O que é isso?"
"Sim, é muito simples. Armazenamos um determinado valor em cada vértice. E cada elemento segue uma regra: o valor armazenado no filho direito deve ser maior que o valor armazenado no vértice e o valor armazenado no filho esquerdo deve ser menor que o valor armazenado no vértice. Essa ordenação permite encontrar rapidamente os elementos da árvore que você precisa."
"Você pode esclarecer o que isso significa?"
"Os elementos da árvore geralmente são classificados por adição. Suponha que temos 7 elementos: 13, 5, 4, 16, 8, 11, 10"
"Aqui está como os elementos são adicionados à árvore."
"Se estamos procurando o número 7 nesta árvore, então é assim que a busca será"
"0) Comece pela raiz."
"1a) 7 é igual a 13? Não"
"1b) 7 é maior que 13? Não, então nos movemos para a subárvore esquerda."
"2a) 7 é igual a 5? Não."
"2b) 7 é maior que 5? Sim, então passamos para a subárvore direita."
"3a) 7 é igual a 8? Não"
"3b) 7 é maior que 8? Não, então nos movemos para a subárvore esquerda."
"4a) Não há subárvore esquerda, o que significa que o número 7 não está na árvore."
"Ah. Em outras palavras, só precisamos verificar os vértices no caminho da raiz até o possível local do número desejado. Sim, isso é realmente rápido."
"Além disso, se a árvore estiver balanceada, você só precisará passar por cerca de 20 vértices para pesquisar um milhão de elementos."
"Concordo - não são muitos."
"O que você quer dizer com árvore equilibrada?"
"Uma árvore que não está distorcida, ou seja, que não possui galhos longos. Por exemplo, se os elementos já estivessem classificados quando construímos a árvore, teríamos feito uma árvore muito longa com um galho. "
"Hmm. Você está certo. Então, o que fazemos?"
"Como você provavelmente já adivinhou, a árvore mais eficiente tem ramificações com aproximadamente o mesmo comprimento. Então, cada comparação descarta a maior parte da subárvore restante."
"Então, precisamos reconstruir a árvore?"
"Sim. Ele precisa ser «equilibrado» - para ser feito o mais próximo possível de uma árvore binária completa."
"Para resolver esse problema, as árvores de autobalanceamento foram inventadas. Se a árvore ficar distorcida depois de adicionar um elemento, ela reordena ligeiramente os elementos para deixar tudo OK. Aqui está um exemplo de balanceamento:"
"Algumas dessas árvores são conhecidas como árvores rubro -negras ."
"Por que eles são chamados de rubro-negros?"
"Seu inventor desenhou todos os vértices usando duas cores. Uma cor era vermelha e a outra era preta. Os diferentes vértices obedecem a regras diferentes. Isso forma toda a base para o procedimento de balanceamento."
"Por exemplo:"
"Então, quais são essas regras?"
"1) Um vértice vermelho não pode ser filho de um vértice vermelho."
"2) A profundidade preta de cada folha é a mesma (a profundidade preta refere-se ao número de vértices pretos no caminho desde a raiz)."
"3) A raiz da árvore é preta."
"Não vou explicar como isso funciona - sua cabeça provavelmente já está explodindo."
"Sim. Meu processador está soltando um pouco de fumaça."
"Aqui está um link para você. Se quiser, pode ler mais sobre isso aqui."
"E agora, vá fazer uma pausa."
GO TO FULL VERSION