Estructura de Datos - Binary Tree (Arbol Binario)
Tags: kotlin, datastructure, tutorial, beginners
Published: 2020-12-18 00:57:19

Hola a todos, siguiendo con la serie de post de estructuras de datos, seguimos con **Binary Tree**. Tratare de hacer un resumen sobre los conceptos principales de este tema y mostrar algunas operaciones básicas con el lenguaje **Kotlin**.

Los **trees** son un tipo de estructura de datos jerárquica, a diferencia de las **Linked Lists**, **Stack and Queues**, **Array** que son estructuras de datos lineales. 

### Vocabulario

- El nodo principal es llamado **root**.

- Los nodos que están abajo directamente de un elemento son llamados **children**.

- Los elementos directamente de arriba son llamados **parent**.

- Los elementos que no tienen **children** son llamados **leaves**.

Por ejemplo **a** es hijo de **f** y **f** es parent (padre) de **a**.

```
       j    <-- root
     /   \
    f      k <-- children de root 
  /   \      \
 a     h      z    <-- leaves 
```

### Algunas razones para usar **trees**

- Si necesita guardar informacion jerárquica como por ejemplo un sistema de archivos.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/rv057h65mo8yhqz9698d.jpg)

- Los arboles proveen acceso moderado para búsqueda, implementando **BST** (Binary Search Tree), el cual es más rápido que un **Linked List** y más lento que un **Array**.

- Provee moderada inserción y eliminar elementos, el cual es más rápido que un **Array** y más lento que un **Linked List** no ordenada.

Un tree cuyo elementos al menos tienen 2 hijos (children) es llamado **Binary Tree**. Ya que cada elemento en un **Binary Tree** tiene solo 2 hijos, estos son llamados **left** y  **right**.

### Tipos de **Binary Tree**

- Full Binary Tree: Un **binary tree** es un **full binary tree** si cada nodo tiene 0 o 2 hijos. Podemos ademas decir un **full binary tree** es un **binary tree** en cual todos los nodos excepto el nodo hoja tiene dos hijos.

```
               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

             18
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

               18
            /     \  
          40       30  
                   /  \
                 100   40
``` 

- Complete Binary Tree: Un **Binary Tree** puede ser **Complete Binary Tree** si todos los niveles están completamente llenos exceptos posiblemente el ultimo nivel y el ultimo nivel tiene todas las llaves a la izquierda.

```
              18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9 
```

- Perfect Binary Tree: **Binary Tree** es un **Perfect Binary Tree** cuando todos los nodos internos tienen dos hijos y todos los nodos hojas tiene el mismo nivel.

```
               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30 
```

- Balanced Binary Tree: Un **Binary Tree** es balanceado si la altura del árbol es O(Log n) donde n es el numero de nodos. Por ejemplo [AVL](https://es.wikipedia.org/wiki/%C3%81rbol_AVL)

- A degenerate (or pathological) tree: Es un tree donde todos los nodos internos tienen un hijo (child). Se podria decir que son iguales en rendimiento que una **Linked List**.

```
       10
      /
    20
     \
     30
      \
      40   
```

### Tree Traversal

Para acceder a la información de los árboles podemos dividirlo en dos secciones.

#### Depth-first
- Pre-order

- In-order

- Post-order

#### Breadth-first
- Level order

Si bien los ejemplos mostrados usaremos la recursividad, debo mencionar que realizar estas mismas operaciones sin recursividad tiene una mejora en término de espacio, si estas interesado en saber como realizarla, puedes consultar esta información en la página de los recursos.

```kotlin

class Node (var value: Int) {
    var left: Node? = null
    var right: Node? = null
}

class TraversalBinaryTree {
    var root = Node(1)
    init {

        root.left = Node(2)
        root.right = Node(3)
        root.left?.left = Node(4)
        root.left?.right = Node(5)

        println("Inorder traversal of binary tree is ")
        this.printInorder(this.root)
        println()

        println("printPreorder traversal of binary tree is ")
        this.printPreorder(this.root)
        println()

        println("printPostorder traversal of binary tree is ")
        this.printPostorder(this.root)
        println()

        println("printLevelOrder traversal of binary tree is ")
        this.printLevelOrder()
    }

    private fun printInorder(node: Node?) {
        if (node == null) return

        this.printInorder(node.left)
        print(node.value.toString() + " ")
        this.printInorder(node.right)
    }

    private fun printPreorder(node: Node?) {
        if (node == null) return

        print(node.value.toString() + " ")
        this.printPreorder(node.left)
        this.printPreorder(node.right)
    }

    private fun printPostorder(node: Node?) {
        if (node == null) return

        this.printPostorder(node.left)
        this.printPostorder(node.right)
        print(node.value.toString() + " ")
    }

    fun printLevelOrder() {
        val queue: Queue<Node?> = LinkedList()
        queue.add(this.root)
        while (!queue.isEmpty()) {

            /* poll() removes the present head.
            For more information on poll() visit
            http://www.tutorialspoint.com/java/
            util/linkedlist_poll.htm */
            val tempNode = queue.poll()
            print(tempNode?.value.toString() + " ")

            if (tempNode?.left != null) queue.add(tempNode.left)
            if (tempNode?.right != null) queue.add(tempNode.right)
        }
    }
}




fun main() {
//    Inorder traversal of binary tree is
//            4 2 5 1 3
//    printPreorder traversal of binary tree is
//            1 2 4 5 3
//    printPostorder traversal of binary tree is
//            4 5 2 3 1
//    printLevelOrder traversal of binary tree is
//            1 2 3 4 5
    TraversalBinaryTree()
}


```

Bien con esto completamos lo básico de teoría sobre los **Arboles Binario**. Ahora un poco de código para demostrar su funcionamiento.



```kotlin
// class node
class Node (val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

// simple tree

class SimpleTree {
    init {
        var root = Node(1)
        //        1
        //      /   \
        //     None  None

        root.left = Node(2)
        root.right = Node(3)
        //        2 and 3 become left and right children of 1
        //           1
        //         /   \
        //        2      3
        //     /    \    /  \
        //   None None None None

        root.left!!.left  = Node(4)
        //        4 becomes left child of 2
        //           1
        //       /       \
        //      2          3
        //    /   \       /  \
        //   4    None  None  None
        //  /  \
        //None None
    }
}

// main file
fun main() {
    val simpleTree = SimpleTree()
}
```
### Inserción en un Árbol Binario (Level Order)

```kotlin
// En este ejemplo simplemente enteramos por el árbol
// y buscamos una posición que este vacía, para agregar el nuevo valor

import java.util.*

class InsertBinaryTree {
    var root: Node? = null

    private fun inorder(node: Node?) {
        if (node == null) return

        this.inorder(node.left)
        print(node.value.toString() + " ")
        this.inorder(node.right)
    }

    private fun insert(node: Node?, value: Int) {
        if (node == null) {
            this.root = Node(value)
            return
        }

        var temp = node
        val q: Queue<Node?> = LinkedList()
        q.add(temp)

        while (!q.isEmpty()) {
            temp = q.peek()
            q.remove()
            if (temp!!.left == null) {
                temp.left = Node(value)
                break
            } else q.add(temp.left)

            if (temp.right == null) {
                temp.right = Node(value)
                break
            } else q.add(temp.right)
        }
    }

    init {
        this.root = Node(10)
        this.root?.left = Node(11)
        this.root?.left?.left = Node(7)
        this.root?.right = Node(9)
        this.root?.right?.left = Node(15)
        this.root?.right?.right = Node(8)

        this.inorder(root)
        println()
        println("====== output before ======")

        this.insert(this.root, 12)

        this.inorder(root)
    }
}
```

### Remover elemento en Árbol Binario

Para remover un elemento en el Árbol lo que tenemos que hacer son dos pasos.

1) Buscar el elemento a remover y remplazarlo con el nodo que esta más a la derecha.
2) Remover el nodo que esta más a la derecha, esto quiere decir el nodo que usamos para remplazar el nodo a eliminar.

Si tienes dudas puedes ver el post original [deletion-binary-tree](https://www.geeksforgeeks.org/deletion-binary-tree/).

Lo que pasa en este código es lo siguiente. Primero en la función `deletionBT` iteramos el Árbol Binario buscando el nodo a remover, una vez encontrado ese valor lo guardamos en una variable y luego seguimos iterando el resto de los elementos hasta que nos encontramos en el último elemento hacia la derecha `rightmost node` y por ende este valor lo tenemos en la variable temporal.

Luego comparamos si el valor a remover existe, si existe guardamos el valor del nodo que esta más a la izquierda y en una variable y luego llamamos a la función `deleteDeepest`.

En la función `deleteDeepest` realizamos el mismo proceso de iterar el Árbol Binario y comparamos si el valor en cada iteración y con esto quedaría completo el proceso de remover un elemento en un Árbol Binario.

```kotlin

package trees

import java.util.*


// https://www.geeksforgeeks.org/deletion-binary-tree/
/*
Delete 10 in below tree
10
/    \
20     30
Output :
30
/
20


Delete 20 in below tree
10
/    \
20     30
\
40
Output :
10
/   \
40    30


 */

class DeleteBinaryTree {
    private var root: Node? = Node(10)

    init {
        root?.left = Node(11)
        root?.left?.left = Node(7)
        root?.left?.right = Node(12)
        root?.right = Node(9)
        root?.right?.left = Node(15)
        root?.right?.right = Node(8)
        this.inorder(root)
        println("The tree before the deletion:")
        println()
        val key = 11
        this.deletionBT(key)
        this.inorder(root)
    }

    private fun deleteDeepest(nodeToDelete: Node?) {
        val q: Queue<Node?> = LinkedList()
        var temp: Node?
        q.add(this.root)
        // Do level order traversal until last node
        while (!q.isEmpty()) {
            temp = q.peek()
            q.remove()
            if (temp == nodeToDelete) {
                return
            }
            if (temp?.right != null) {
                if (temp.right == nodeToDelete) {
                    temp.right = null
                    return
                } else q.add(temp.right)
            }
            if (temp?.left != null) {
                if (temp.left == nodeToDelete) {
                    temp.left = null
                    return
                } else q.add(temp.left)
            }
        }
    }

    private fun deletionBT(key: Int) {
        val q: Queue<Node?> = LinkedList()
        var keyNode: Node? = null
        var temp: Node? = null

        q.add(this.root)
        while (!q.isEmpty()) {
            temp = q.peek()
            q.remove()

            if (key == temp?.value) keyNode = temp
            if (temp?.left != null) q.add(temp.left)
            if (temp?.right != null) q.add(temp.right)
        }

        if (keyNode != null) {
            val value = temp?.value!!.toInt()

            this.deleteDeepest(temp)
            keyNode.value = value
        }
    }

    private fun inorder(node: Node?) {
        if (node == null) return

        this.inorder(node.left)
        print(node.value.toString() + " ")
        this.inorder(node.right)
    }
}


fun main() {
    DeleteBinaryTree()
}
```

Espero que les haya gustado este post. Si tienen sugerencias o correcciones no dudes en dejarme un mensaje.

### Recursos
[https://www.geeksforgeeks.org/binary-tree-data-structure/](https://www.geeksforgeeks.org/binary-tree-data-structure/)
[https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/](https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/)
[https://www.geeksforgeeks.org/deletion-binary-tree/](https://www.geeksforgeeks.org/deletion-binary-tree/)