DEV Community

Cover image for Estructura de Datos - Binary Tree (Arbol Binario)
Ronny Medina
Ronny Medina

Posted on

Estructura de Datos - Binary Tree (Arbol Binario)

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 
Enter fullscreen mode Exit fullscreen mode

Algunas razones para usar trees

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

Alt Text

  • 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
Enter fullscreen mode Exit fullscreen mode
  • 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 
Enter fullscreen mode Exit fullscreen mode
  • 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 
Enter fullscreen mode Exit fullscreen mode
  • 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

  • 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   
Enter fullscreen mode Exit fullscreen mode

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.


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()
}


Enter fullscreen mode Exit fullscreen mode

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

// 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()
}
Enter fullscreen mode Exit fullscreen mode

Inserción en un Árbol Binario (Level Order)

// 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)
    }
}
Enter fullscreen mode Exit fullscreen mode

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.

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.


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()
}
Enter fullscreen mode Exit fullscreen mode

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/insertion-in-a-binary-tree-in-level-order/
https://www.geeksforgeeks.org/deletion-binary-tree/

Discussion (0)