Árbol binario de búsqueda (BST)

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Definición

Subárbol izquierdo de un nodo:
- valores menores que el nodo
Subárbol derecho de un nodo:
- valores mayores que el nodo
Los subárboles izquierdo y derecho deben ser BST

Representación esquemática de un árbol binario de búsqueda.

Implementación

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

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

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda.

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda donde la raíz está en amarillo.

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda donde el nodo raíz y su subárbol izquierdo están en gris. El primer nodo del subárbol derecho está en amarillo.

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda. El último nodo raíz y su subárbol izquierdo están en gris. El nuevo nodo raíz está en amarillo.

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda donde el nuevo nodo raíz está en amarillo y el resto en gris.

Búsqueda

Busca 72

Representación esquemática de un árbol binario de búsqueda donde el nuevo nodo raíz está en amarillo y el resto en gris. El nodo coloreado tiene el número 72 y está resaltado.

Búsqueda

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Inserción

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Representación gráfica de un nodo nuevo.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Representación gráfica del nodo nuevo que se ha convertido en la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Representación gráfica de un nodo nuevo y una raíz con un hijo derecho.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Representación gráfica de un nodo nuevo y una raíz con un hijo derecho. El current_node es la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Representación gráfica de una raíz con hijo derecho e izquierdo. El current_node es la raíz. El nodo nuevo es el hijo izquierdo.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Representación gráfica de un nodo nuevo y un BST con varios elementos. El current_node es la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Representación gráfica de un nodo nuevo y un BST con varios elementos. El current_node es el hijo izquierdo de la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Representación gráfica de un nodo nuevo y un BST con subárbol izquierdo.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Representación gráfica de un BST con subárbol izquierdo. El nodo nuevo es ahora el hijo derecho de la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Representación gráfica de un nodo nuevo y un BST con varios elementos.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representación gráfica de un nodo nuevo y un BST con varios elementos. El current_node es el hijo derecho de la raíz.

Inserción

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representación gráfica de un nodo nuevo y un BST con varios elementos. El current_node es el hijo derecho de la raíz. El nodo nuevo es el hijo izquierdo del current_node.

Eliminación

Sin hijos

Representación gráfica de un BST con varios elementos. Uno de los nodos está en rojo porque se va a eliminar. Este nodo no tiene hijos.

Eliminación

Sin hijos
- elimínalo

Representación gráfica de un BST con varios elementos. El nodo que se iba a eliminar ha desaparecido del árbol.

Eliminación

Un hijo

Representación gráfica de un BST con varios elementos. Uno de los nodos está en rojo porque se va a eliminar. Este nodo tiene un hijo derecho.

Eliminación

Un hijo
- elimínalo
- conecta el hijo con el padre del nodo

Representación gráfica de un BST con varios elementos. El nodo eliminado ha desaparecido y la raíz apunta al hijo derecho del nodo eliminado.

Eliminación

Un hijo
- elimínalo
- conecta el hijo con el padre del nodo

Representación gráfica de un árbol binario de búsqueda.

Eliminación

Dos hijos

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo. El hijo derecho de la raíz está en amarillo.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo. Otro nodo está en amarillo para encontrar el sucesor.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo. Otro nodo está en amarillo para encontrar el sucesor.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final

Representación gráfica de un BST donde la raíz (a eliminar) está en rojo. Otro nodo está en amarillo para encontrar el sucesor. Se ha encontrado el sucesor y es el número 13.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final

Representación gráfica de un BST. La raíz ha sido sustituida por el sucesor.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final
  - si el sucesor tiene hijo derecho:

Representación gráfica de un BST donde el sucesor tiene un hijo derecho.

Eliminación

Dos hijos
- sustitúyela por su sucesor
  - el nodo con el menor valor mayor que el del nodo
- para hallar el sucesor:
  - ve al hijo derecho
  - sigue yendo a la izquierda hasta el final
  - si el sucesor tiene hijo derecho:
    - el hijo pasa a ser el hijo izquierdo del padre del sucesor.

Representación gráfica de un BST donde el sucesor tenía un hijo derecho. El hijo del sucesor ha pasado a ser el hijo izquierdo del padre del sucesor y la raíz ha sido reemplazada por el sucesor.

Usos

Ordena listas de forma eficiente
Mucho más rápido al buscar que arrays y listas enlazadas
Mucho más rápido al insertar y eliminar que arrays
Se usa para implementar estructuras más avanzadas:
- conjuntos dinámicos
- tablas de consulta
- colas de prioridad

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python