Árbol AVL: guía completa con implementación en Python

Desbalance en árboles binarios de búsqueda

Los árboles binarios de búsqueda (BST) son un tipo de árbol binario estructura de datos que organiza los datos siguiendo un orden específico. Cada nodo contiene un valor y tiene enlaces a hasta otros dos nodos: los hijos izquierdo y derecho. En un BST, la regla es que el valor del hijo izquierdo debe ser menor que el de su padre, y el del hijo derecho debe ser mayor.

Los BST pueden ser muy eficientes para encontrar valores concretos porque permiten descartar grandes partes del árbol durante la búsqueda. Por ejemplo, si buscamos el valor uno en el árbol anterior, podemos ignorar todos los nodos a la derecha de seis. Esto se debe a que la propiedad de orden garantiza que todos esos valores son mayores que seis.

En un escenario ideal, cada nodo dividiría los datos por la mitad, de modo que en cada paso se elimine la mitad de los valores. Esto conduce a búsquedas extremadamente rápidas. Sin embargo, según el orden de inserción, es posible acabar con un árbol desbalanceado que no divide los datos de forma efectiva. Por ejemplo, insertar valores de menor a mayor produce un árbol lineal, que no rinde mejor que una lista.

Qué es un árbol AVL

Un árbol AVL es un árbol binario de búsqueda con la siguiente propiedad adicional:

Para cada nodo, las alturas de los subárboles izquierdo y derecho difieren como mucho en uno.

Desglosando esta definición, el subárbol izquierdo de un nodo incluye todos los nodos a su izquierda, mientras que el subárbol derecho comprende todos los nodos a su derecha. La altura de un árbol se define como la longitud del camino más largo desde la raíz (el nodo superior) hasta cualquiera de sus hojas descendientes (nodos sin hijos).

El factor de equilibrio de un nodo se calcula como la diferencia de altura entre su subárbol izquierdo y su subárbol derecho:

balance(N) = altura(subárbol izquierdo de N) - altura(subárbol derecho de N)

Por ejemplo, balance(6) = 1 - 3 = -2.

En el diagrama, el nodo 6 muestra un factor de equilibrio igual a -2, lo que indica que el árbol no cumple los criterios de un árbol AVL. Para que un árbol se clasifique como AVL, el factor de equilibrio de cada nodo debe ser -1, 0 o 1.

Por qué usar árboles AVL

La eficiencia de las consultas en un árbol binario de búsqueda depende de la altura del árbol. En el peor caso, la cantidad de nodos a examinar es igual a la altura. Un problema clave de los BST es que su altura puede igualar el número de nodos, lo que significa que una consulta podría requerir inspeccionar todos y cada uno de los nodos.

Sea M(h) el número mínimo de nodos que hay que añadir a un árbol binario de búsqueda para alcanzar una altura h. En BST simples, observamos que M(h) = h, es decir, podemos alcanzar altura h con solo h nodos. Esto implica que la altura de un BST puede crecer linealmente con el número de nodos, llevando a un tiempo de consulta proporcional al tamaño del conjunto de datos.

Demostración de que los árboles AVL tienen altura logarítmica

Consideremos el número mínimo de nodos, M(h), necesarios para crear un árbol AVL con altura h. Al ser un árbol AVL, es importante notar que el factor de equilibrio de cada nodo solo puede ser -1, 0 o 1.

No obstante, dado que asumimos que el árbol tiene el menor número posible de nodos para alcanzar la altura h, la raíz no puede tener balance 0. Si lo tuviera, podríamos quitar un nodo del lado izquierdo o derecho para obtener un balance -1 o 1, y seguiría siendo un árbol AVL válido.

Supongamos que el balance de la raíz es 1 (el razonamiento sería el mismo si fuera -1). Esto implica que el árbol tiene la siguiente estructura:

A su vez, tanto el subárbol izquierdo como el derecho también deben ser árboles AVL, cada uno con el número mínimo de nodos requerido para sus respectivas alturas (de lo contrario, sería posible eliminar nodos adicionales). El total de nodos del árbol es 1 (la raíz) más los nodos del subárbol izquierdo más los del derecho.

M(h) = 1 + (nodos en L) + (nodos en R) = 1 + M(h - 1) + M(h - 2)

A medida que crece la altura, necesitamos añadir más nodos para alcanzarla. Por tanto:

M(h - 1) > M(h - 2)

Combinando ambos, podemos decir que:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Podemos aplicar esto h/2 veces hasta llegar a M(1) = 1 o M(2) = 2:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Para mayor claridad, la siguiente imagen muestra ejemplos concretos para h = 7 y h = 6:

Concluimos que el número mínimo de nodos en un árbol AVL de altura h es al menos 2(h/2):

M(h) > 2(h/2)

Aplicando logaritmo en base dos a ambos lados, obtenemos:

log2(M(h)) > log2(2(h/2)) = h/2

En consecuencia, multiplicando ambos lados por dos, deducimos que la altura es como máximo el doble del logaritmo en base 2 del número de nodos:

2 × log2(M(h)) > h

Hemos demostrado que:

La altura de un árbol AVL con N nodos es como máximo 2 × log2(N).

Esto indica que las consultas en un árbol AVL solo requieren examinar un pequeño segmento del conjunto de datos. Por ejemplo, con mil millones de entradas, el logaritmo es aproximadamente 30, lo que significa que incluso con mil millones de datos, bastaría con inspeccionar en torno a 60 para encontrar un elemento concreto. Es una mejora enorme frente a los BST que, en el peor caso, obligan a revisar los mil millones de datos.

Si quieres profundizar en la complejidad temporal algorítmica y la diferencia entre complejidad lineal y logarítmica, consulta esta entrada sobre notación Big-O y complejidad temporal.

Mantener el equilibrio con árboles AVL

Los árboles AVL garantizan consultas rápidas forzando que el balance de cada nodo sea -1, 0 o 1. Para mantener ese equilibrio tras insertar un nuevo valor, hay que reequilibrar el árbol.

La inserción en árboles binarios de búsqueda consiste en seguir el camino desde la raíz hacia abajo. Vamos a la izquierda cuando el valor a insertar es menor y a la derecha en caso contrario.

Una inserción aumenta la altura como mucho en uno. Así que, si tras insertar no se respeta la propiedad de balance, significa que había un nodo con balance -1 que ahora es -2, o un nodo con balance 1 que ahora es 2. El primer caso es lo que ocurre en el ejemplo anterior.

Rotaciones simples

Para restaurar el equilibrio, recurrimos a rotaciones. Una rotación a la izquierda sobre el nodo A reestructura el árbol girando A hacia la izquierda, como se muestra a continuación:

En el diagrama:

• BL representa el subárbol izquierdo de B
• BR es el subárbol derecho
• AL es el subárbol izquierdo de A

Observa que tras la rotación, el orden de los nodos sigue siendo válido:

1. El nodo A es menor que B porque B era su hijo derecho.
2. Los nodos en BL son mayores que A porque estaban a la derecha de A.
3. Los nodos en AL son menores que B porque son menores que A.

Una rotación a la derecha funciona de forma simétrica girando A hacia la derecha.

Veamos un ejemplo concreto corrigiendo el desbalance del árbol tras insertar 19 con una rotación a la izquierda sobre el nodo 6.

Tras la inserción, corregimos el desbalance rotando un nodo con balance -2 o 2. En este caso, el factor de equilibrio del nodo 6 era -2, es decir, el árbol caía hacia la derecha, así que aplicamos una rotación a la izquierda (en sentido contrario al desbalance). Si el balance fuera 2, usaríamos una rotación a la derecha.

Rotaciones dobles

En el ejemplo anterior, el árbol volcaba completamente a la derecha, por lo que una rotación simple a la izquierda bastó para restaurar el equilibrio. Sin embargo, a veces aparece un desbalance en zigzag: el árbol se inclina a un lado, pero el subárbol se inclina al contrario. Para verlo, volvamos al árbol original antes de insertar 19 e insertemos 7 en su lugar:

Aquí, el árbol sigue inclinándose a la derecha, pero el subárbol con raíz en 10 se inclina a la izquierda. En este caso, primero debemos rotar el nodo 10 a la derecha:

Observa que el nodo B no tiene hijo derecho. Aun así lo mostramos en azul en el diagrama para facilitar la visualización. 

Tras la rotación a la derecha, caemos en el caso anterior, donde una rotación a la izquierda sobre 6 restaura el equilibrio:

Cómo implementar un árbol AVL en Python

Empecemos por la implementación del nodo.

Implementación de nodos

Cada nodo del árbol tiene cinco atributos:

• El valor que almacena (self.value)
• El nodo padre (self.parent)
• El hijo izquierdo (self.left)
• El hijo derecho (self.right)
• La altura del subárbol con raíz en ese nodo (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1

Usamos el valor None para representar nodos ausentes. La height por defecto se establece en 1 porque un árbol con un único nodo tiene altura 1. 

Para facilitar la implementación del árbol, añadimos varios métodos a la clase Node.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Observa que usamos los métodos .set_left() y .set_right() para asignar los hijos izquierdo y derecho, respectivamente. El motivo de usar estos métodos, en lugar de modificar directamente los atributos self.left y self.right, es que siempre que se cambia un hijo, es necesario actualizar también el padre del nuevo hijo y la altura del nodo.

Implementación del árbol AVL

El árbol AVL mantiene un único parámetro: la raíz del árbol, que es el nodo superior.

class AVLTree:
  def __init__(self):
    self.root = None

Para mantener el equilibrio del árbol, debemos implementar rotaciones izquierda y derecha. Recordemos cómo se ilustra una rotación a la izquierda en el diagrama:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Las rotaciones a la derecha se implementan de forma simétrica:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

Con las rotaciones, podemos reequilibrar el árbol. Un nodo requiere reequilibrio cuando su factor de equilibrio alcanza 2 (el árbol se inclina a la izquierda) o -2 (se inclina a la derecha). En total, hay cuatro casos a considerar:

Implementamos estos cuatro casos en el método .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Fíjate en que, en cada caso, el método devuelve la raíz del subárbol que acaba de equilibrarse. Esta nueva raíz del subárbol se usará después para actualizar los hijos durante el proceso de reequilibrado.

Añadir un nodo a un árbol AVL es similar al proceso en un BST normal, con el añadido de restaurar el equilibrio tras insertar el nodo. Para añadir un nodo en un BST, empezamos en la raíz y descendemos por el árbol. En cada paso, comparamos el valor a añadir con el del nodo actual. Si es menor, vamos a la izquierda; en caso contrario, a la derecha. Mientras bajamos, guardamos el nodo padre para poder insertar el nuevo nodo como su hijo.

Cuando llegamos a un nodo vacío, hay dos casos:

1. El padre es None; el árbol está vacío, así que el nuevo nodo pasa a ser la raíz.
2. Hemos encontrado el padre, así que debemos establecer el nuevo nodo como hijo izquierdo o derecho, según los valores.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

La única diferencia entre el método .add() de un BST y el de un árbol AVL está en el paso final. Consiste en subir por el árbol desde el nodo recién añadido hasta la raíz y reequilibrar cada nodo usando el método .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Ten en cuenta que el método .rebalance() no hace nada cuando el nodo ya está equilibrado: simplemente devuelve ese mismo nodo. Por eso, al subir por el árbol, podemos llamarlo en ambos lados, aunque solo uno de ellos esté desbalanceado. La otra llamada deja el árbol sin cambios.

Recuerda que implementamos .rebalance() para que devuelva la (potencialmente) nueva raíz del subárbol. La razón es poder actualizar los hijos izquierdo y derecho de los nodos actuales mientras subimos restaurando el equilibrio.

El siguiente diagrama muestra los pasos de .restore_balance() al subir por el árbol.

En el ejemplo, primero añadimos el nodo 8. Después, el proceso de restaurar el equilibrio comienza en ese nodo y asciende por el árbol, comprobando y reequilibrando los hijos izquierdo y derecho de cada nodo encontrado. Continúa hasta llegar al nodo 10. Hasta ese punto, ninguna de las invocaciones de .rebalance() tiene efecto porque los nodos están equilibrados.

Sin embargo, al llegar al nodo 10, se observa que su hijo izquierdo, el nodo 7, tiene un factor de equilibrio de -2, lo que indica que hay que reequilibrar. En consecuencia, se llama a .rebalance(7), lo que sustituye el hijo izquierdo de 10 por la nueva raíz del subárbol izquierdo, el nodo 8, restaurando así el equilibrio del árbol.

Otras operaciones en árboles AVL

Además de añadir y borrar elementos manteniendo el equilibrio, los árboles AVL admiten varias operaciones esenciales más.

Mínimo y máximo

Gracias al orden del BST, el valor mínimo se encuentra en el nodo más a la izquierda del árbol, mientras que el máximo está en el nodo más a la derecha.

Hemos implementado dos funciones auxiliares que identifican los nodos más a la izquierda y a la derecha a partir de un nodo dado. Son útiles para facilitar la implementación del borrado de nodos.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Contains

Para saber si un árbol contiene un valor concreto, aprovechamos su propiedad de orden para guiar la búsqueda. Partiendo de la raíz, vamos a la izquierda si el valor buscado es menor que el nodo actual y a la derecha si es mayor. Si llegamos al final sin encontrarlo, significa que no está en el árbol.

Para facilitar el proceso, implementamos un método auxiliar llamado .locate_node(). Es útil no solo para buscar, sino también para operaciones como borrar valores del árbol. Además, usamos el método .__contains__(), que nos permite utilizar el operador in para comprobar de forma sencilla si un valor está presente.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Borrado

Borrar un nodo en un árbol AVL puede ser especialmente complejo cuando el nodo está en medio del árbol. Si el nodo es una hoja, es decir, no tiene hijos, podemos borrarlo fácilmente estableciendo el puntero del hijo izquierdo o derecho de su padre a None según sea hijo izquierdo o derecho.

Hay un caso especial cuando el nodo a borrar es la propia raíz del árbol. En ese escenario, podemos eliminarlo poniendo la raíz a None.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Para borrar un valor de un árbol AVL, primero debemos localizar el nodo que lo contiene con el método .locate_node(). Una vez localizado, podemos eliminarlo con .delete_leaf() si es una hoja. Si no lo es, borrarlo directamente rompería la estructura del árbol. Para solucionarlo, buscamos un nodo de reemplazo adecuado. Si el nodo a borrar tiene hijo izquierdo, seleccionamos el nodo más a la derecha de su subárbol izquierdo. Así mantenemos el orden del árbol.

El diagrama siguiente ejemplifica la eliminación del nodo 10. Como tiene hijo izquierdo, lo sustituimos por el nodo más a la derecha del subárbol izquierdo. Tras el reemplazo, es fundamental reequilibrar el árbol empezando por el padre del nodo recién sustituido.

En este ejemplo, el nodo de reemplazo es una hoja. No obstante, si tuviera hijos, sería necesario reasignarlos al padre del nodo de reemplazo. Dado que el nodo de reemplazo es extremo (o el más a la izquierda o el más a la derecha), solo puede tener un hijo. Por tanto, esta reasignación siempre es posible.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Consulta por rango

Las consultas por rango consisten en identificar todos los valores comprendidos entre dos valores dados. Gracias al orden de los árboles AVL, podemos localizarlos de forma eficiente.

Para localizar todos los valores dentro del rango definido por el límite inferior lb y el límite superior ub, usamos un enfoque recursivo. Para cada nodo que visitamos, si su valor cae dentro del rango, lo añadimos a los resultados. Después, exploramos tanto el subárbol izquierdo como el derecho para continuar la búsqueda.

Ignoramos el subárbol izquierdo si el valor del nodo es menor que el límite inferior, porque todos los valores del subárbol izquierdo serán menores que el del nodo. De forma análoga, ignoramos el subárbol derecho si el valor del nodo es mayor que el límite superior, ya que todos los valores del subárbol derecho serán mayores que el del nodo.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Otros árboles autoequilibrados

Hemos implementado un árbol AVL capaz de realizar las siguientes operaciones:

• Añadir un valor
• Borrar un valor
• Buscar un valor
• Consultar mínimo y máximo
• Consultar todos los valores comprendidos entre dos valores

El paquete avltree ofrece una implementación en Python con estas capacidades.

Otros árboles binarios de búsqueda autoequilibrados, como los árboles rojo-negro, los splay trees y los B-trees, proporcionan funcionalidades similares. En general, su rendimiento es comparable en la mayoría de aplicaciones, ya que todos garantizan altura logarítmica. No obstante, los árboles AVL están más finamente equilibrados, optimizando las búsquedas a costa de inserciones potencialmente más lentas por los requisitos de reequilibrado más estrictos.

Los splay trees son especialmente eficaces cuando los elementos accedidos recientemente se reutilizan con frecuencia, lo que los hace una opción excelente para implementaciones de caché.

Los B-trees están diseñados específicamente para funcionar bien en disco y no en memoria, por lo que son muy valiosos para manejar grandes volúmenes de datos que exceden la memoria, como en la creación de índices de bases de datos.

Mejoras adicionales

Hay varias formas de mejorar nuestra implementación. Aquí tienes algunas propuestas de ejercicios para profundizar en los árboles AVL:

• En la implementación actual, los nodos almacenan un único valor. Para usarlos como índices de bases de datos, es necesario almacenar filas completas, ya que el valor corresponderá a una de las columnas de la tabla. Podemos mejorar la implementación para que el árbol AVL funcione como un diccionario, mapeando valores a sus filas correspondientes.
• Nuestra implementación no admite valores duplicados. Sin embargo, se puede modificar para permitir que varios nodos compartan el mismo valor.
• Normalmente, los árboles AVL se implementan de forma recursiva. Hemos evitado este enfoque para no requerir una comprensión profunda de la recursión. Aunque las implementaciones recursivas suelen ser más elegantes y concisas, requieren dominar bien el concepto.

Conclusión

Los BST son un tipo de estructura de datos de árbol binario que organiza la información con un orden específico. Gracias a ello, evita inspeccionar todo el conjunto de datos al buscar valores concretos. Sin embargo, pueden desbalancearse y degradar su rendimiento, hasta el punto de requerir revisar todo el conjunto de datos en algunos casos.

Los árboles AVL resuelven este problema aplicando propiedades adicionales de equilibrio mediante rotaciones. Estas propiedades aseguran que la altura del árbol se mantenga logarítmica con respecto al tamaño del conjunto de datos, lo que supone una mejora significativa.

La complejidad temporal logarítmica es una mejora notable frente a la complejidad lineal, lo que hace que los árboles AVL sean increíblemente eficientes para resolver consultas. Incluso con miles de millones de entradas, un árbol AVL solo necesita inspeccionar unos pocos datos para localizar un elemento, lo que los convierte en una opción mucho más eficiente.