Implementación de Árboles, BST y Grafos en Python con Algoritmos y Complejidad

Árboles de Expresión y Conversión

def ade_to_expr(node):
if not node:
return
print("(", end="")
ade_to_expr(node._left)
print(node._data, end="")
ade_to_expr(node._right)
print(")", end="") O(n)

def expr_to_ade(expr: str, operadores: set) -> AdE:
s = Stack()
e = expr.split(" ")
for c in e:
if c in operadores:
opnd2 = s.pop()
opnd1 = s.pop()
T = AdE(c)
T.add_left(opnd1)
T.add_right(opnd2)
s.push(T)
else:
T = AdE(c)
s.push(T)
return s.pop() O(n)

Operaciones en Árboles Binarios de Búsqueda (BST)

Búsqueda de Máximos y Mínimos

class BSTree:
def _maximum_rec(self, node):
if not node._right:
return node
return self._maximum_rec(node._right)

def maximum_rec(self):
if self._root:
return self._maximum_rec(self._root)._data
return None O(h)

def maximum_iter(self):
if not self._root:
return None
node = self._root
while node._right:
node = node._right
return node._data O(h)

def _minimum_rec(self, node):
if not node._left:
return node
return self._minimum_rec(node._left)

def minimum_rec(self):
if self._root:
return self._minimum_rec(self._root)._data
return None O(h)

def minimum_iter(self):
if not self._root:
return None
node = self._root
while node._left:
node = node._left
return node._data O(h)

Búsqueda de Elementos

def find_rec(self, x: Any):
def _find(node, item):
if node is None:
return None
if node._data == item:
return node
elif node._data < item:
return _find(node._right, item)
else:
return _find(node._left, item)
return _find(self._root, x) O(h)

def find_iter(self, item):
node = self._root
while node and node._data != item:
if item < node._data:
node = node._left
else:
node = node._right
return node O(h)

Predecesor y Sucesor

class BSTree:
def _successor(self, x):
if x._right:
return self._minimum_rec(x._right)
else:
y = x._parent
while y and y._left != x:
x, y = y, y._parent
return y O(h)

def _predecessor(self, x):
if x._left:
return self._maximum_rec(x._left)
else:
y = x._parent
while y and y._right != x:
x, y = y, y._parent
return y O(h)

Ordenamiento y Recorridos Especiales

def ordenar_lista(l: List) -> List:
T = BSTree()
for e in l:
T.insert(e)
lista_ordenada = T.inorder()
return lista_ordenada O(n*h), BST equilibrado O(n log n), BST desequilibrado O(n^2).

def lista_decreciente(self) -> List:
l = []
def _lista(node):
if not node:
return
_lista(node._right)
l.append(node._data)
_lista(node._left)
_lista(self._root)
return l O(n)

class Tree:
def apply_funcion(self, fun, *args, **kwargs) -> List:
l = []
def _apply(node):
if not node:
return
f = fun(node._data, *args, **kwargs)
l.append(f)
_apply(node._left)
_apply(node._right)
_apply(self._root)
return l O(n)

Algoritmos en Grafos

Recorrido DFS y Detección de Ciclos

class Graph_(Graph):
def dfs_rec_fixed(self):
time = [0]
cycle = [False]
def _dfs_visit(u):
time[0] += 1
self.set_node(u, 'color', 'GRAY')
self.set_node(u, 'd_time', time[0])
for v in self.adj(u):
if self.get_node(v, 'color') == 'GRAY':
cycle[0] = True
if self.get_node(v, 'color') == 'WHITE':
self.set_node(v, 'parent', u)
_dfs_visit(v)
time[0] += 1
self.set_node(u, 'color', 'BLACK')
self.set_node(u, 'f_time', time[0])
for u in self.nodes():
self.reset_node(u)
for u in self.nodes():
if self.get_node(u, 'color') == 'WHITE':
_dfs_visit(u)
if cycle[0]:
return "Se ha encontrado al menos un ciclo" O(V+E)

Pseudocódigos Adicionales

Componentes Conexas

Pseudocódigos: (conexas) -> componentes_conexas(G)
para cada nodo u:
color[u] = BLANCO
componentes = 0
para cada nodo u:
si color[u] == BLANCO:
componentes += 1
DFS(u)
devolver componentes O(V+E)

Detección de Ciclos

(detectar ciclos) -> DFS(u)
marcar u GRIS
para cada vecino v:
si v es GRIS:
existe ciclo
si v es BLANCO:
DFS(v)
marcar u NEGRO O(V+E)