algorithm - avl - tree structure architecture

Seudocódigo para comparar dos árboles.

Question

Este es un problema que me he encontrado algunas veces y no me he convencido de haber usado la lógica más eficiente.

Como ejemplo, supongamos que tengo dos árboles: uno es una estructura de carpetas, el otro es un "modelo" en memoria de esa estructura de carpetas. Deseo comparar los dos árboles y generar una lista de nodos presentes en un árbol y no en el otro, y viceversa.

¿Hay un algoritmo aceptado para manejar esto?

Answer 1

Parece que solo quieres hacer un recorrido previo al pedido, esencialmente. Donde "visitar" un nodo significa verificar si hay hijos que están en una versión pero no en la otra.

Más precisamente: empezar en la raíz. En cada nodo, obtenga un conjunto de elementos en cada una de las dos versiones del nodo. La diferencia simétrica de los dos conjuntos contiene los elementos en uno pero no el otro. Imprimir / salida esos. La intersección contiene los elementos que son comunes a ambos. Para cada elemento en la intersección (supongo que no se va a mirar más a fondo en los elementos que faltan en un árbol), llame "visita" recursivamente a ese nodo para verificar su contenido. Es una operación O (n), con una pequeña sobrecarga de recursión.

Answer 2

Si usa un árbol de clasificación, como un árbol AVL, también puede atravesar su árbol de manera eficiente en orden. Eso devolverá sus rutas en orden ordenado de "bajo" a "alto". Luego, puede ordenar su matriz de directorios (por ejemplo, usando quicksort) usando el mismo método de comparación que usa en su algoritmo de árbol.

Luego comience a comparar los dos lado a lado, avanzando al siguiente elemento atravesando su árbol en orden y verificando el siguiente elemento en la matriz de directorios ordenada.

Esto debería ser más eficiente en la práctica, pero solo la evaluación comparativa puede indicar.

Answer 3

Un código de ejemplo simple en python.

class Node(object):
  def __init__(self, val):
    self.val = val
    self.child = {}

  def get_left(self):
    #if left is not in the child dictionary that means the element does not have a left child
    if ''left'' in self.child:
      return self.child[''left'']
    else:
      return None

  def get_right(self):
    #if right is not in the child dictionary that means the element does not have a rigth child
    if ''right'' in self.child:
      return self.child[''right'']
    else:
      return None


def traverse_tree(a):
  if a is not None:
    print ''current_node : %s'' % a.val
    if ''left'' in a.child:
      traverse_tree(a.child[''left''])

    if ''right'' in a.child:
      traverse_tree(a.child[''right''])



def compare_tree(a, b):
  if (a is not None and b is None) or (a is None and b is not None):
    return 0
  elif a is not None and b is not None:
    print a.val, b.val
    #print ''currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s'' % (a.val, b.val, a.child[''left''].val, b.child[''left''].val, a.child[''right''].val, b.child[''right''].val)
    if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()):
      return 1
    else:
      return 0
  else:
    return 1

#Example
a = Node(1)
b = Node(0)
a.child[''left''] = Node(2)
a.child[''right''] = Node(3)
a.child[''left''].child[''left''] = Node(4)
a.child[''left''].child[''right''] = Node(5)
a.child[''right''].child[''left''] = Node(6)
a.child[''right''].child[''right''] = Node(7)
b.child[''left''] = Node(2)
b.child[''right''] = Node(3)
b.child[''left''].child[''left''] = Node(4)
#b.child[''left''].child[''right''] = Node(5)
b.child[''right''].child[''left''] = Node(6)
b.child[''right''].child[''right''] = Node(7)
if compare_tree(a, b):
  print ''trees are equal''
else:
  print ''trees are unequal''
#DFS traversal
traverse_tree(a)

También pegó un ejemplo que puede ejecutar.

Answer 4

public boolean compareTrees(TreeNode root1, TreeNode root2) {
  if ((root1 == null && root2 != null) || 
      (root1 != null && root2 == null)) {
    return false;
  }

  if (root1 == null && root2 == null) {
    return true;
  }

  if (root1.data != root2.data) {
    return false;
  }

  return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right);
}