{"id":4083,"date":"2023-04-17T10:00:56","date_gmt":"2023-04-17T13:00:56","guid":{"rendered":"https:\/\/elemarjr.com\/clube-de-estudos\/?p=4083"},"modified":"2023-10-21T21:40:28","modified_gmt":"2023-10-22T00:40:28","slug":"introducao-a-arvore-binaria-conceitos-terminologias-e-implementacao","status":"publish","type":"artigos","link":"https:\/\/elemarjr.com\/clube-de-estudos\/artigos\/introducao-a-arvore-binaria-conceitos-terminologias-e-implementacao\/","title":{"rendered":"Introdu\u00e7\u00e3o \u00e0 \u00e1rvore bin\u00e1ria: conceitos, terminologias e implementa\u00e7\u00e3o"},"content":{"rendered":"\n

Como um desenvolvedor experiente com mais de 30 anos de carreira na \u00e1rea de tecnologia, eu tive a oportunidade de trabalhar com uma variedade de algoritmos e estruturas de dados ao longo dos anos. Um dos mais importantes e \u00fateis para resolver muitos problemas de programa\u00e7\u00e3o \u00e9 a \u00c1rvore Bin\u00e1ria de Busca.<\/p>\n\n\n\n

O que \u00e9 uma \u00c1rvore Bin\u00e1ria de Busca?<\/h2>\n\n\n\n

Uma \u00c1rvore Bin\u00e1ria de Busca \u00e9 uma estrutura de dados que permite armazenar e pesquisar informa\u00e7\u00f5es de maneira eficiente. \u00c9 composta por n\u00f3s que podem ter at\u00e9 dois filhos, um \u00e0 esquerda e outro \u00e0 direita. Cada n\u00f3 na \u00e1rvore cont\u00e9m um valor \u00fanico e os n\u00f3s \u00e0 esquerda t\u00eam valores menores do que o n\u00f3 pai, enquanto os n\u00f3s \u00e0 direita t\u00eam valores maiores.<\/p>\n\n\n\n

\"\"
Uma simples \u00e1rvore bin\u00e1ria de tamanho 9 e altura 3, com um n\u00f3 raiz de valor 2. A \u00e1rvore acima n\u00e3o est\u00e1 balanceada (elemento 5 possui 2 filhos a direita e nenhum a esquerda), nem est\u00e1 ordenada – notar que n\u00e3o \u00e9 uma \u00e1rvore bin\u00e1ria de procura. – Fonte: Wikipedia<\/a><\/figcaption><\/figure>\n\n\n\n

A estrutura da \u00e1rvore bin\u00e1ria de busca permite uma busca eficiente em tempo logar\u00edtmico, ou seja, O(log n), onde n \u00e9 o n\u00famero de elementos na \u00e1rvore. Essa efici\u00eancia \u00e9 alcan\u00e7ada porque a \u00e1rvore \u00e9 estruturada de tal forma que as compara\u00e7\u00f5es para encontrar um elemento s\u00e3o realizadas em caminhos \u00fanicos e ordenados.<\/p>\n\n\n\n

Exemplo de implementa\u00e7\u00e3o em C#<\/h3>\n\n\n\n

Veja um exemplo simples de uma \u00e1rvore bin\u00e1ria de busca implementada em C#:<\/p>\n\n\n\n

C#<\/span><\/path><\/path><\/svg><\/span>
public<\/span> <\/span>class<\/span> <\/span>Node<\/span><\/span>\n{<\/span><\/span>\n    <\/span>public<\/span> <\/span>int<\/span> Value;<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> Left;<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> Right;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>Node<\/span>(<\/span>int<\/span> <\/span>value<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        Value <\/span>=<\/span> value;<\/span><\/span>\n        Left <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n        Right <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>BinarySearchTree<\/span><\/span>\n{<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> Root;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BinarySearchTree<\/span>()<\/span><\/span>\n    {<\/span><\/span>\n        Root <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>Insert<\/span>(<\/span>int<\/span> <\/span>value<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        <\/span>Node<\/span> node <\/span>=<\/span> <\/span>new<\/span> <\/span>Node<\/span>(value);<\/span><\/span>\n        <\/span>if<\/span> (Root <\/span>==<\/span> <\/span>null<\/span>)<\/span><\/span>\n        {<\/span><\/span>\n            Root <\/span>=<\/span> node;<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>else<\/span><\/span>\n        {<\/span><\/span>\n            <\/span>Node<\/span> currentNode <\/span>=<\/span> Root;<\/span><\/span>\n            <\/span>while<\/span> (<\/span>true<\/span>)<\/span><\/span>\n            {<\/span><\/span>\n                <\/span>if<\/span> (value <\/span><<\/span> currentNode.Value)<\/span><\/span>\n                {<\/span><\/span>\n                    <\/span>if<\/span> (currentNode.Left <\/span>==<\/span> <\/span>null<\/span>)<\/span><\/span>\n                    {<\/span><\/span>\n                        currentNode.Left <\/span>=<\/span> node;<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    }<\/span><\/span>\n                    currentNode <\/span>=<\/span> currentNode.Left;<\/span><\/span>\n                }<\/span><\/span>\n                <\/span>else<\/span><\/span>\n                {<\/span><\/span>\n                    <\/span>if<\/span> (currentNode.Right <\/span>==<\/span> <\/span>null<\/span>)<\/span><\/span>\n                    {<\/span><\/span>\n                        currentNode.Right <\/span>=<\/span> node;<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    }<\/span><\/span>\n                    currentNode <\/span>=<\/span> currentNode.Right;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: Chat GPT<\/span><\/span><\/code><\/pre>C#<\/span><\/div>\n\n\n\n
A classe Node<\/code> representa um n\u00f3 da \u00e1rvore, que cont\u00e9m um valor inteiro (Value<\/code>) e duas refer\u00eancias a outros n\u00f3s, um para o filho \u00e0 esquerda (Left<\/code>) e outro para o filho \u00e0 direita (Right<\/code>).<\/p>\n\n\n\n
A classe BinarySearchTree<\/code> \u00e9 a \u00e1rvore em si, e cont\u00e9m uma refer\u00eancia para o n\u00f3 raiz (Root<\/code>). A classe oferece um m\u00e9todo Insert<\/code> que insere um novo n\u00f3 na \u00e1rvore. Esse m\u00e9todo come\u00e7a procurando o lugar correto para inserir o novo n\u00f3, percorrendo a \u00e1rvore a partir do n\u00f3 raiz e seguindo sempre para a esquerda se o valor do novo n\u00f3 for menor que o valor do n\u00f3 atual, ou para a direita se for maior ou igual.<\/p>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Java<\/h3>\n\n\n\n
Confira o mesmo c\u00f3digo implementado em Java:<\/p>\n\n\n\n
Java<\/span><\/path><\/path><\/svg><\/span>
public<\/span> <\/span>class<\/span> <\/span>Node<\/span> {<\/span><\/span>\n    <\/span>public<\/span> <\/span>int<\/span> value;<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> left;<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> right;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>Node<\/span>(<\/span>int<\/span> <\/span>value<\/span>) {<\/span><\/span>\n        <\/span>this<\/span>.value <\/span>=<\/span> value;<\/span><\/span>\n        <\/span>this<\/span>.left <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n        <\/span>this<\/span>.right <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>BinarySearchTree<\/span> {<\/span><\/span>\n    <\/span>public<\/span> <\/span>Node<\/span> root;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BinarySearchTree<\/span>() {<\/span><\/span>\n        <\/span>this<\/span>.root <\/span>=<\/span> <\/span>null<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>insert<\/span>(<\/span>int<\/span> <\/span>value<\/span>) {<\/span><\/span>\n        <\/span>Node<\/span> node <\/span>=<\/span> <\/span>new<\/span> <\/span>Node<\/span>(value);<\/span><\/span>\n        <\/span>if<\/span> (root <\/span>==<\/span> <\/span>null<\/span>) {<\/span><\/span>\n            root <\/span>=<\/span> node;<\/span><\/span>\n        } <\/span>else<\/span> {<\/span><\/span>\n            <\/span>Node<\/span> currentNode <\/span>=<\/span> root;<\/span><\/span>\n            <\/span>while<\/span> (<\/span>true<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (value <\/span><<\/span> currentNode.value) {<\/span><\/span>\n                    <\/span>if<\/span> (currentNode.left <\/span>==<\/span> <\/span>null<\/span>) {<\/span><\/span>\n                        currentNode.left <\/span>=<\/span> node;<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    }<\/span><\/span>\n                    currentNode <\/span>=<\/span> currentNode.left;<\/span><\/span>\n                } <\/span>else<\/span> {<\/span><\/span>\n                    <\/span>if<\/span> (currentNode.right <\/span>==<\/span> <\/span>null<\/span>) {<\/span><\/span>\n                        currentNode.right <\/span>=<\/span> node;<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    }<\/span><\/span>\n                    currentNode <\/span>=<\/span> currentNode.right;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: Chat GPT<\/span><\/span><\/code><\/pre>Java<\/span><\/div>\n\n\n\n
Note que a estrutura da classe Node<\/code> \u00e9 a mesma, com os atributos value<\/code>, left<\/code> e right<\/code>. J\u00e1 a classe BinarySearchTree<\/code> tamb\u00e9m \u00e9 semelhante, com o atributo root<\/code>, o construtor que inicializa o atributo como null<\/code>, e o m\u00e9todo insert<\/code> que insere um novo n\u00f3 na \u00e1rvore seguindo as regras de uma \u00e1rvore bin\u00e1ria de busca.<\/p>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Python<\/h3>\n\n\n\n
Confira o mesmo c\u00f3digo implementado em Python:<\/p>\n\n\n\n
Python<\/span><\/path><\/path><\/svg><\/span>
class<\/span> <\/span>Node<\/span>:<\/span><\/span>\n    <\/span>def<\/span> <\/span>__init__<\/span>(<\/span>self<\/span>, <\/span>value<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.value <\/span>=<\/span> value<\/span><\/span>\n        <\/span>self<\/span>.left <\/span>=<\/span> <\/span>None<\/span><\/span>\n        <\/span>self<\/span>.right <\/span>=<\/span> <\/span>None<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>BinarySearchTree<\/span>:<\/span><\/span>\n    <\/span>def<\/span> <\/span>__init__<\/span>(<\/span>self<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.root <\/span>=<\/span> <\/span>None<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>insert<\/span>(<\/span>self<\/span>, <\/span>value<\/span>):<\/span><\/span>\n        node <\/span>=<\/span> Node(value)<\/span><\/span>\n        <\/span>if<\/span> <\/span>not<\/span> <\/span>self<\/span>.root:<\/span><\/span>\n            <\/span>self<\/span>.root <\/span>=<\/span> node<\/span><\/span>\n        <\/span>else<\/span>:<\/span><\/span>\n            current_node <\/span>=<\/span> <\/span>self<\/span>.root<\/span><\/span>\n            <\/span>while<\/span> <\/span>True<\/span>:<\/span><\/span>\n                <\/span>if<\/span> value <\/span><<\/span> current_node.value:<\/span><\/span>\n                    <\/span>if<\/span> <\/span>not<\/span> current_node.left:<\/span><\/span>\n                        current_node.left <\/span>=<\/span> node<\/span><\/span>\n                        <\/span>break<\/span><\/span>\n                    current_node <\/span>=<\/span> current_node.left<\/span><\/span>\n                <\/span>else<\/span>:<\/span><\/span>\n                    <\/span>if<\/span> <\/span>not<\/span> current_node.right:<\/span><\/span>\n                        current_node.right <\/span>=<\/span> node<\/span><\/span>\n                        <\/span>break<\/span><\/span>\n                    current_node <\/span>=<\/span> current_node.right<\/span><\/span>\n<\/span>\n# Fonte: Chat GPT<\/span><\/span><\/code><\/pre>Python<\/span><\/div>\n\n\n\n
O c\u00f3digo acima define a classe Node, que \u00e9 utilizada para representar um n\u00f3 na \u00e1rvore.<\/p>\n\n\n\n
Cada n\u00f3 tem um valor e refer\u00eancias para seus filhos esquerdo e direito. A classe \u201cBinarySearchTree\u201d \u00e9 usada para criar e manipular a \u00e1rvore bin\u00e1ria de busca. O m\u00e9todo \u201cinsert\u201d \u00e9 utilizado para inserir um novo valor na \u00e1rvore. A implementa\u00e7\u00e3o utiliza um loop <\/em>\u201cwhile\u201d para navegar pela \u00e1rvore e encontrar o local correto para inserir o novo n\u00f3.<\/p>\n\n\n\n
Aplica\u00e7\u00f5es<\/h2>\n\n\n\n
As \u00e1rvores bin\u00e1rias de busca s\u00e3o amplamente utilizadas em algoritmos de busca, ordena\u00e7\u00e3o e filtragem de dados. Alguns exemplos de aplica\u00e7\u00e3o s\u00e3o:<\/p>\n\n\n\n