Get best of the week

Árvores vermelho-pretas em javascript

imagem

Oi Habr! Recentemente estudou árvores vermelho-pretas. Tentei visualizar os detalhes da operação dos algoritmos de inserção e exclusão no d3.js. Espero que o resultado ajude a economizar tempo para quem estuda algoritmos em javascript. Você pode vê-lo aqui . O código fonte da implementação da qual eu confiei aqui . Sob detalhes curtos de gatos.

Procure soluções existentes


O principal objetivo da idéia era entender a implementação do algoritmo e visualizá-lo. O primeiro passo foi procurar uma implementação com explicações completas e compreensíveis e código js. No processo de busca, ficou triste que os autores às vezes não tivessem terminado a fonte, por exemplo, existe um algoritmo de inserção, mas nenhuma exclusão. Ou eles visualizam assim , mas não fornecem links para a fonte. Então eu encontrei este excelente artigo. Mas pelo menos matar, ainda não consigo entender por que o autor inseriu o código com fotos e não deu um link para o código-fonte mediante solicitação nos comentários. Há também um pacote npm red-black-tree , cujo código-fonte inteiro é: 'in progress ...' in readme. Também encontrou uma implementação popular árvores vermelho-pretas em js, das quais muitos pacotes e milhões de downloads por semana dependem, mas o código tem cinco anos.

Priorização e especificação de tarefas


Decidi que a legibilidade e a compreensibilidade do código para fins educacionais são mais importantes, então tomei como base o artigo mencionado no início, e não o pacote npm. A implementação acabou sendo mais conveniente e visual em termos de leitura de código. No artigo, o autor começa com uma árvore binária e depois a estende para vermelho-preto. Para visualização, parece bastante lógico herdar de uma árvore vermelho-preta e criar uma árvore animada. Portanto, depois de redigitar o código e garantir que ele funcione, comecei a desenhar uma árvore animada. D3.js. vem em socorro. Existem transições maravilhosas que permitem mover elementos para as posições corretas e transformá-los suavemente em estados adequados, conforme o algoritmo funciona.

O significado das árvores vermelho-pretas


Pensei por um longo tempo, como se de uma maneira simples, para explicar o que é o quê. Provavelmente, mesmo assim, você precisa ler a teoria de diferentes fontes. Como diz o ditado: "Você não joga palavras em uma música". Mas conclusões resumidas simples podem ser formuladas em poucas palavras. A conclusão é que existem vários casos ao inserir e excluir um elemento, dependendo de quais “avós”, “pais”, “tios”, “filhos”, “irmãos” repintam e mudam (giram) para o lado onde há menos elementos . Como resultado, nunca acontece que o caminho do nó mais distante para o nó raiz seja muito longo, portanto, a pesquisa pelo elemento desejado em uma estrutura desse tipo é muito rápida. Bem, isso é compensado pela complexidade de inserção e exclusão.

More articles:


All Articles