Averigüe si un árbol es un árbol de búsqueda binaria en Haskell

  type BSTree a = BinaryTree a

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
                      deriving Show

  flattenTree :: BinaryTree a -> [a]
  flattenTree  tree = case tree of
      Null -> []
      Node left val right -> (flattenTree left) ++ [val] ++ (flattenTree right)

  isBSTree :: (Ord a) => BinaryTree a -> Bool
  isBSTree btree = case btree of
      Null -> False
      tree -> (flattenTree tree) == sort (flattenTree tree)

Lo que quiero hacer es escribir una función para determinar si el árbol dado es un árbol de búsqueda binario, mi método es agrupar todos los valores en una lista e importarlos Data.Listy luego ordenar la lista para encontrar si son iguales, pero Es un poco complicado. ¿Podemos hacer esto sin importar otro módulo?

Aquí hay una manera de hacerlo sin aplanar el árbol.

De la definición, aquí,

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
     deriving Show

Uno puede ver que atravesar el árbol de izquierda a derecha, ignorando Nodey entre paréntesis, le da una secuencia alterna de Nullsy as. Es decir, entre cada dos valores, hay un Null.

Mi plan es verificar que cada subárbol satisfaga los requisitos adecuados : podemos refinar los requisitos en cada uno Node, recordando qué valores estamos entre ellos, y luego probarlos en cada uno Null. Como hay un Nullpar de valores entre cada orden, habremos probado que todos los pares en orden (de izquierda a derecha) no disminuyen.

¿Qué es un requisito? Es un límite inferior y superior suelto en los valores del árbol. Para expresar los requisitos, incluidos los que se encuentran en los extremos más a la izquierda y a la derecha, podemos extender cualquier pedido con Bottom y Topelementos, de la siguiente manera:

data TopBot a = Bot | Val a | Top deriving (Show, Eq, Ord)

Ahora, verifiquemos que un árbol determinado cumpla con los requisitos de estar en orden y entre límites dados.

ordBetween :: Ord a => TopBot a -> TopBot a -> BinaryTree a -> Bool
  -- tighten the demanded bounds, left and right of any Node
ordBetween lo hi (Node l x r) = ordBetween lo (Val x) l && ordBetween (Val x) hi r
  -- check that the demanded bounds are in order when we reach Null
ordBetween lo hi Null         = lo <= hi

Un árbol de búsqueda binaria es un árbol que está en orden y entre Boty Top.

isBSTree :: Ord a => BinaryTree a -> Bool
isBSTree = ordBetween Bot Top

El cálculo de los actuales valores extremales en cada sub-árbol, burbujeando ellos hacia el exterior, le da más información que usted necesita, y es más incómoda en los casos extremos donde un subárbol izquierdo o derecho está vacío. Mantener y verificar los requisitos , empujándolos hacia adentro, es bastante más uniforme.

Aquí hay una pista: hacer una función auxiliar

isBSTree' :: (Ord a) => BinaryTree a -> BSTResult a

donde BSTResult ase define como

data BSTResult a
   = NotBST             -- not a BST
   | EmptyBST           -- empty tree (hence a BST)
   | NonEmptyBST a a    -- nonempty BST with provided minimum and maximum

Debería poder proceder de manera recursiva, explotando los resultados en subárboles para impulsar el cálculo, en particular el mínimo y el máximo.

Por ejemplo, si tiene tree = Node left 20 right, con isBSTree' left = NonEmptyBST 1 14y isBSTree' right = NonEmptyBST 21 45, entonces isBSTree' treedebería ser NonEmptyBST 1 45.

En el mismo caso, excepto tree = Node left 24 right, deberíamos tener isBSTree' tree = NotBST.

Convertir el resultado a Booles trivial.

Sí , no necesita ordenar la lista. Puede verificar si cada elemento es menor o igual que el siguiente elemento. Esto es más eficiente ya que podemos hacer esto en O (n) , mientras que la evaluación de la lista ordenada requiere completamente O (n log n) .

Así podemos verificar esto con:

ordered :: Ord a => [a] -> Bool
ordered [] = True
ordered xa@(_:xs) = and (zipWith (<=) xa xs)

Entonces podemos verificar si el árbol binario es un árbol de búsqueda binario con:

isBSTree :: Ord a => BinaryTree a -> Bool
isBSTree = ordered . flattenTree

Creo que se puede afirmar que Nulles un árbol de búsqueda binario, ya que es un árbol vacío. Esto significa que para cada nodo (no hay nodos) los elementos en el subárbol izquierdo son menores o iguales al valor en el nodo, y los elementos en el subárbol derecho son todos mayores o iguales al valor en el nodo .

Podemos proceder de izquierda a derecha sobre el árbol de esta manera:

isBSTtreeG :: Ord a => BinaryTree a -> Bool
isBSTtreeG t = gopher Nothing [Right t]
    where
    gopher  _   []                        =  True
    gopher  x   (Right Null:ts)           =  gopher x ts
    gopher  x   (Right (Node lt v rt):ts) =  gopher x (Right lt:Left v:Right rt:ts)
    gopher Nothing   (Left v:ts)          =  gopher (Just v) ts
    gopher (Just y)  (Left v:ts)          =  y <= v && gopher (Just v) ts

Inspirado por John McCarthy'sgopher .

La lista desplegable explícita se puede eliminar con el paso de continuación,

isBSTtreeC :: Ord a => BinaryTree a -> Bool
isBSTtreeC t = gopher Nothing t (const True)
    where
    gopher  x   Null           g  =  g x 
    gopher  x   (Node lt v rt) g  =  gopher x lt (\case
                                       Nothing -> gopher (Just v) rt g
                                       Just y  -> y <= v && gopher (Just v) rt g)

Mantener solo uno, el elemento más grande hasta ahora , es suficiente.