Sprawdź, czy drzewo jest drzewem do wyszukiwania binarnego w 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)

Chcę napisać funkcję określającą, czy dane drzewo jest drzewem wyszukiwania binarnego, moja metoda polega na zgrupowaniu wszystkich wartości na liście i zaimportowaniu, Data.Lista następnie posortowaniu listy, aby sprawdzić, czy są one równe, ale to jest trochę skomplikowane. Czy możemy to zrobić bez importowania innego modułu?

Oto sposób na zrobienie tego bez spłaszczania drzewa.

Z definicji tutaj

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

widać, że przemierzanie drzewa od lewej do prawej, ignorowanie Nodei nawiasy, daje naprzemienną sekwencję Nulls i as. Oznacza to, że między każdymi dwiema wartościami jest Null.

Moim planem jest sprawdzenie, czy każde poddrzewo spełnia odpowiednie wymagania : możemy uszczegółowić wymagania dla każdego z nich Node, pamiętając, które wartości są pomiędzy, a następnie przetestować je dla każdego z nich Null. Ponieważ istnieje Nullpara wartości między kolejnymi wartościami, sprawdzimy, czy wszystkie pary w kolejności (od lewej do prawej) nie maleją.

Co jest wymagane? Jest to luźna dolna i górna granica wartości w drzewie. Aby wyrazić wymagania, w tym te na skraju lewej i skrajnej prawej strony, możemy rozszerzyć dowolne zamówienie o Bottom i Topelementy w następujący sposób:

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

Sprawdźmy teraz, czy dane drzewo spełnia wymagania bycia zarówno w porządku, jak i między podanymi granicami.

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

Drzewo wyszukiwania binarnego to drzewo, które jest w porządku oraz między Boti Top.

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

Obliczanie rzeczywistych wartości ekstremalnych w każdym poddrzewie, propagowanie ich na zewnątrz, daje więcej informacji, niż potrzebujesz, i jest kłopotliwe w skrajnych przypadkach, w których lewe lub prawe poddrzewo jest puste. Utrzymywanie i sprawdzanie wymagań , popychanie ich do wewnątrz, jest raczej bardziej jednolite.

Oto podpowiedź: wykonaj funkcję pomocniczą

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

gdzie BSTResult ajest zdefiniowany jako

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

Powinieneś być w stanie kontynuować rekurencyjnie, wykorzystując wyniki w poddrzewach do kierowania obliczeniami, w szczególności minimum i maksimum.

Na przykład, jeśli masz tree = Node left 20 right, przy pomocy isBSTree' left = NonEmptyBST 1 14i isBSTree' right = NonEmptyBST 21 45, to isBSTree' treepowinno być NonEmptyBST 1 45.

W tym samym przypadku, z wyjątkiem tree = Node left 24 right, powinniśmy zamiast tego isBSTree' tree = NotBST.

Konwersja wyniku Booljest wtedy trywialna.

Tak , nie musisz sortować listy. Możesz sprawdzić, czy każdy element jest mniejszy lub równy następnemu elementowi. Jest to bardziej wydajne, ponieważ możemy to zrobić w O (n) , podczas gdy ocena posortowanej listy całkowicie zajmuje O (n log n) .

Możemy to sprawdzić za pomocą:

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

Możemy więc sprawdzić, czy drzewo binarne jest drzewem wyszukiwania binarnego za pomocą:

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

Myślę, że można twierdzić, że Nullsamo jest drzewem wyszukiwania binarnego, ponieważ jest to puste drzewo. Oznacza to zatem, że dla każdego węzła (nie ma węzłów) elementy w lewym poddrzewie są mniejsze lub równe wartości w węźle, a elementy w prawym poddrzewie są większe lub równe wartości w węźle .

Możemy przejść od lewej do prawej nad drzewem w następujący sposób:

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

Inspirowany przez Johna McCarthy'egogopher .

Wyraźną listę rozwijaną można wyeliminować poprzez przekazywanie kontynuacji,

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)

Wystarczy tylko jeden, jak dotąd największy element.