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.
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
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.
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.
// 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)
// 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.
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()
}
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/
Oldest comments (0)