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

tree binary-tree

Question

  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 importar Data.List y luego ordenar la lista para encontrar si son iguales , pero es un poco complicado. ¿Podemos hacer esto sin importar otro módulo?

Answer 1

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 el Node y los paréntesis, le da una secuencia alterna de Null sy a s. 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 Node , recordando qué valores estamos entre ellos, y luego probarlos en cada Null . Como hay un valor Null entre cada par de valores en 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 izquierdo y derecho, podemos extender cualquier pedido con Top elementos Bottom y Top , 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 los 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 binario es un árbol que está en orden y entre Bot y Top .

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

Calcular los valores extremos reales en cada subárbol, burbujearlos hacia afuera, le brinda más información de la que necesita, y es complicado 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.

Answer 2

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

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

donde BSTResult a se 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 14 y isBSTree'' right = NonEmptyBST 21 45 , entonces isBSTree'' tree debe ser NonEmptyBST 1 45 .

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

Convertir el resultado a Bool es trivial.

Answer 3

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 el gopher John McCarthy .

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.

Answer 4

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 evaluar la lista ordenada toma 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 binaria con:

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

Creo que se puede afirmar que Null sí mismo es 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 .