In [1]:
using LLRBTrees, LLRBVisualize
El árbol LLRB (left-leaning red-black o rojo-negro inclinado a la izquierda) es una estructura de datos, es decir, un objeto que guarda datos y soporta cietas operaciones.
Esta estructura salva datos en nodos, que son pares de claves (keys) y valores (values) y que tienen vínculos a otros nodos. Como cualquier árbol, debe tener un nodo raíz (root), que no tiene ningún padre (osea no está vinculado a ningún otro nodo), desde el cuál se puede acceder a todos los otros nodos.
Además, este tipo de árbol es binario. Así que cada nodo puede tener dos hijos como máximo. Si no tiene hijos en alguna de sus vacantes, a esta vacante la llamaremos hoja (leaf).
El orden de los nodos se hace mediante las claves (keys). La convención es que un hijo izquierdo siempre tiene una clave menor a la de su padre y uno derecho, mayor.
Para visualizar esto armemos un árbol básico.
El objeto árbol lo podemos iniciar especificando los tipos de objeto de las claves y valores (las claves deben de tener un orden total):
In [2]:
arbol = LLRBTree{Int, ASCIIString}()
Out[2]:
O podemos simplemente indicar los valores de la raíz y julia adivinará los tipos
In [3]:
arbol = LLRBTree(1,"a")
display(arbol)
Out[3]:
In [4]:
typeof(arbol)
Out[4]:
Para añadir un hijo adoptamos el método de Base push! y le podemos dar la clave y valor a añadir
In [5]:
push!(arbol, 0, "b")
display(arbol)
Out[5]:
O un nodo
In [6]:
nodo = TreeNode(2, "c")
push!(arbol, nodo)
display(arbol)
Out[6]:
La conveniencia de los árboles binarios de búsqueda (binary-search trees o BST's) es la velocidad que ofrecen en la búsqueda de una clave.
Para mantener un arreglo de objetos en la memoria se guarda normalmente uno de sus elementos en la memoria y a los demás se les accede por medio de vínculos entre ellos.
Si se tuviera una cadena lineal de objetos (e.d. un arreglo no ordenado)
In [7]:
unsorted = LLRBTree(1,1)
nodoactual = unsorted.root
for i in 2:5
nodoactual.right = TreeNode(i,i)
nodoactual = nodoactual.right
end
unsorted|>display
Out[7]:
Se necesitarían tantos pasos para llegar al último elemento como elementos tenga el árbol.
In [8]:
@time unsorted[5]
Out[8]:
En cambio, en un arbol binario de búsqueda (BST) las claves tienen un orden. Entonces, se hace una comparación para ver si la clave buscada es mayor o menor.
Así que en cada comparación se salta uno en promedio la mitad del arbol debajo del nodo.
Por lo que cada búsqueda, inserción o extracción toma aproximadamte el logaritmo base 2 del número de elementos del árbol en pasos.
In [9]:
arbol = LLRBTree(1,1)
for i in 2:5
push!(arbol, i,i)
end
display(arbol)
Out[9]:
In [10]:
@time arbol[5]
Out[10]:
Hay que tomar en cuenta que esta comparación en tiempos no es tan justa pues el getindex() de los arboles pregunta por el elemento izquierdo primero y luego va al derecho.
Ahora, algo que no es tan fácil es mantener el árbol más o menos balanceado.
Balanceado quiere decir que cualquier camino de la raíz a una hoja tenga el mismo número de pasos.
Para mantener a los árboles balanceados se han diseñado muchos tipos de árboles auto-balanceados (self-balancing trees). Osea que, a medida que se le añaden o quitan elementos, se ejecutan otras operaciones que aseguran una especie de balance.
El método que usamos nosotros es una variación de los árboles rojo-negros (red-black trees o RBT) (que fueron introducidos por Guibas y Robert Sedgewick hace 30 años) diseñada por el mismo autor Sedgewick.
Los RBT's son una representación binaria de árboles con nodos que pueden tener hasta 4 hijos (2-3-4 Trees). En nuestra implementación representamos a un vínculo rojo con el padre como un nodo rojo (al que se la añade "_r" en nuestra representación ASCII) y los nodos vinculados son parte de un gran nodo. Para que se puedan tener solo hasta 4 hijos se debe de cumplir que nunca haya dos vínculos uno después del otro.
Estos nodos grandes se utilizan para no tener que aumentar o disminuir la altura de solo una rama del árbol cuando se añade o sustrae un nodo.
Por eso, en nuestra implementación, siempre habrá el mismo número de saltos hacia nodos negros, cuando se va de la raíz a cualquier hoja y nunca habrá dos nodos rojos consecutivos. Estas dos características son invarianzas de la estructura, que queremos manter.
En esta implementación se siguen tres principios básicos que hacen que el código sea mas elegante:
Para manipular los objetos en nuestro código, sin violar el balance de negros (que siempre haya el mismo numero de nodos negros llendo de la raíz a una hoja), usamos tres operaciones que mantienen ese balance. Las rotaciones izquierda y derecha y el voltear colores.
Las rotaciones pueden usarse para convertir un 3-nodo que se inclina a la izquierda (derecha) en uno que se inclina al lado opuesto.
En un rotación derecha podemos tener el siguiente caso
In [11]:
arbol = LLRBTree(3,3)
arbol.root.left = TreeNode(2,2)
arbol.root.left.left = TreeNode(1,1)
arbol.root.left.left.isRed = false
arbol.root.right = TreeNode(5,5)
arbol.root.right.isRed = false
display(arbol)
Out[11]:
function rotateright{K,V}(node::TreeNode{K,V})
if isleftleaf(node)
error("The left part of the given node must be a node")
end
son=node.left
if !isrightleaf(son)
node.left=son.right
else
node.left=TreeNode{K,V}()
end
son.right=node
son.isRed=node.isRed
node.isRed=true
return son
end
In [12]:
arbol.root=LLRBTrees.rotateright(arbol.root)
display(arbol)
Out[12]:
Y en la rotación izquierda
In [13]:
arbol = LLRBTree(3,3)
arbol.root.left = TreeNode(2,2)
arbol.root.left.isRed = false
arbol.root.right = TreeNode(4,4)
arbol.root.right.right = TreeNode(5,5)
arbol.root.right.right.isRed =false
display(arbol)
Out[13]:
In [14]:
#Con un codigo análogo logramos esto
arbol.root=LLRBTrees.rotateleft(arbol.root)
display(arbol)
Out[14]:
Para eliminar un 4-nodo podemos invertir el color de un nodo y sus hijos. Esto mantiene el balance pues se pasa el vínculo rojo al nodo padre.
In [15]:
arbol = LLRBTree(3,3)
arbol.root.left = TreeNode(2,2)
arbol.root.right = TreeNode(4,4)
old = arbol.root
arbol.root = TreeNode(1,1)
arbol.root.right = old
display(arbol)
Out[15]:
function flipcolor!{K,V}(node::TreeNode{K,V})
node.isRed = !node.isRed
if !isleftleaf(node)
node.left.isRed = !node.left.isRed
end
if !isrightleaf(node)
node.right.isRed = !node.right.isRed
end
end
In [16]:
LLRBTrees.flipcolor!(arbol.root.right)
display(arbol)
Out[16]:
Las tres operaciones anteriores se pueden utilizar en conjunto para mantener las invariantes deseadas. Las convenciones de inclinación a la izquierda, etc, permiten que se reduzcan los casos a considerar.
En su artículo, Sedgewick presenta los casos en una gráfica muy concisa.
Siempre insertamos nodos rojos al llegar a una hoja, es por eso que tenemos que considerar los 3 casos en el diagrama de arriba.
Al final, siempre terminamos pasando el vínculo al padre y la implementación recursiva se encarga de que volvamos a tomar esta misma decisión si tenemos dos nodos rojos.
Además, como las operaciones son balanceadas, se mantiene el balance del árbol.
El borrado de nodos en BST's normalmente requiere de mucho código y se deben de considerar muchos casos. Esta nueva implementación simplica mucho el código pues, debido a que hay una correspondencia uno a uno con los árboles 2-3, los casos a considerar disminuyen mucho.
La idea primordial es ir modificando el nodo por el que pasamos en la recursión de tal manera que el o su hijo derecho siempre sean rojos. Es decir, que nunca estemos en un 2-nodo para que si lo borramos no perdamos el balance.
Para lograr que siempre estemos en un 3-nodo, hacemos uso de los métodos moveredleft y moveredright, los cuales nadamás son una combinación de rotaciones y volteadas de color, por lo que también mantienen el balance.
Como indica el nombre, si nos estamos moviendo a la izquierda, lo único que tenemos que hacer, para asegurar que el nodo a donde nos moveremos sea un 3-nodo, es jalar el nodo padre a su hijo izquierdo. Esto lo tenemos que hacer en todos los contextos posibles los cuales estan resumidos en la siguiente figura:
*La letra en gris representa un nodo que podría estar o no, pues es fácil cambiar de árboles que solo tienen nodos rojos izquierdos a unos que tengan de los dos lados*
Como podemos ver en el siguiente código, el caso en el que el hijo derecho es un 3 o 4-nodo se cubre dentro del if y el caso en el que los dos hijos son 2-nodos se resuelve con un simple flipcolor!
function moveredleft{K,V}(node::TreeNode{K,V})
flipcolor!(node)
if !isrightleaf(node)
if ( isred(node, :right, :left) )
node.right = rotateright(node.right)
node = rotateleft(node)
flipcolor!(node)
end
end
return node
end
Mover a la derecha es la misma idea pero es más fácil de implementar, pues no hay nodos rojos a la derecha:
function moveredright{K,V}(node::TreeNode{K,V})
flipcolor!(node)
if ( isred(node, :left, :left) )
node= rotateright(node)
flipcolor!(node)
end
return node
end
Una vez que llegamos al nodo que queremos borrar, si este nodo no es un nodo final, no podemos sustituirlo por un nodo vacío.
Por eso, lo que hacemos es bajar hasta el nodo mínimo en su rama derecha, con los movimientos que nos aseguran estar en un nodo grande y convertir el nodo mínimo en un hoja. No sin antes haber copiado los valores del nodo mínimo al nodo que queríamos borrar.
Para visualizar esto, borraremos el hijo derecho del árbol siguiente.
In [39]:
arbol = LLRBTree(1,1)
populate!(arbol, 9)
display(arbol)
Out[39]:
In [40]:
node=arbol.root.right
min = minimum(node.right)
node.key=min.key
node.value=min.value
node.right=LLRBTrees.deletemin(node.right)
display(arbol)
Out[40]:
function deletemin{K,V}(node::TreeNode{K,V})
if(!isleftleaf(node))
if(!isred(node, :left) && !isred(node, :left, :left) )
moveredleft(node)
end
node.left = deletemin(node.left)
return fixup(node)
else
return TreeNode{K,V}()
end
end
Las operaciones que usamos para el método de borrado, pueden dejar algunos 4-nodos en el camino. Sin embargo, podemos resolver esto como lo hicimos en el método para inserción:
Ejecutando un método que llamamos fixup, el cual tiene las últimas 5 líneas del método de inserción, en el camino de regreso, es decir cuando hacemos la llamada a return.
Juntando todos estos 3 métodos podemos borrar nodos manteniendo las invariantes que deseamos.
En este manual tratamos de dar una idea de para que son y como funcionan las estructuras de datos de los árboles LLRB.
Para dar un entendimiento más a fondo vimos como se implementan las operaciones básicas para esta estructura de datos de una manera elegante y no tan difícil de entender.
A pesar de que el algoritmo usado es muy nuevo y debería de estar a la par con los objetos que usen árboles 2-3, el que sea una estructura muy básica hace que programarlo en un nivel alto como el de Base en Julia, tena repercusiones en su rendimiento y que no se compare con el de las librerias de Julia que están programadas en C.
Esto se puede ver en la siguente sección, donde se hace una comparación del tiempo y la alocación de objetos necesaria para el ordereddict de Julia (que tmb usa árboles 2-3) y los LLRBTrees que programamos nosotros.
In [17]:
using DataStructures
using LLRBTrees
using ProfileView
elems = 100000
Out[17]:
In [18]:
dict = OrderedDict{Int,Int}()
@time for c in 1:elems
dict[c] = rand(1:elems)
end
In [19]:
dict = OrderedDict{Int,Int}()
Profile.clear()
@profile for c in 1:elems
dict[c] = rand(1:elems)
end
ProfileView.view()
Out[19]:
In [20]:
arbol = LLRBTree{Int,Int}()
@time for c in 1:elems
arbol[c] = rand(1:elems)
end
In [21]:
arbol = LLRBTree{Int,Int}()
Profile.clear()
@profile for c in 1:elems
arbol[c] = rand(1:elems)
end
ProfileView.view()
Out[21]:
In [22]:
@time for c in 1:elems
(arbol[c])
end
In [23]:
@time for c in 1:elems
(dict[c])
end
In [24]:
sizeof(arbol)
Out[24]:
In [25]:
sizeof(dict)
Out[25]:
In [26]:
whos(r"dict")
In [27]:
whos(r"arbol")
In [28]:
@code_warntype delete!(arbol, 1)
In [ ]: