Двоичное дерево поиска SML - PullRequest
Новая
       13

Двоичное дерево поиска SML

0 голосов
/ 30 сентября 2018

Итак, у меня есть определение типа данных для Двоичного дерева поиска в SML: 

datatype tree = Void | Node of tree * int * tree;

И у меня также есть эта функция: 

fun sub_tree a b Void = 
  | sub_tree a b (Node (t1, x, t2)) =
    if (a <= x) andalso (x < b) then
      Node ((sub_tree a b t1), x, (sub_tree a b t2))
    else
      sub_tree a b t2;

, которая предназначена для прохождения дереваи вывести другое дерево, чьи теги (x в функции) больше или равны a и меньше b (a <= x <b). </p>

Теперь у меня также есть этот пример дерева: 

val ex1 = Node(Node(Node(Void, 0, Node(Void, 2, Void)), 3, Node(Void, 5, Void)), 6, Node(Void, 7, Node(Void, 8, Node(Void, 9, Node(Node(Void, 10, Void), 12, Node(Void, 15, Node(Void, 19, Void)))))))

Итак, функция работает в случае, например: 

sub_tree 5 8 ex1;
val it =  Node (Node (Void, 5, Void), 6, Node (Void, 7, Void)): tree

Но когда она не работает, если a = 0 & b = 1, потому что: 

sub_tree 0 1 ex1;
val it = Void: tree

И он должен вернуть: Node (Void, 0, Void)

Так что мне нужна помощь, чтобы указать мне на ошибку, которую я сделал в функции, заранее спасибо!

1 Ответ

0 голосов
/ 30 сентября 2018

Вам необходимо решить три случая в sub_tree a b (Node (t1, x, t2)):

  • a <= x andalso x < b: включить подветвление
  • x < a: проверить правый подветвление
  • b <= x: отметьте левую ветвь

Итак, чтобы завершить свою функцию, используйте: 

if (a <= x) andalso (x < b) then
  Node ((sub_tree a b t1), x, (sub_tree a b t2))
else if x < a then
  sub_tree a b t2;
else
  sub_tree a b t1;

Визуализация трех случаев sub_tree a b (Node (t1, x, t2))

       a, b <= x       |  a <= x andalso x < b  |       x < a, b
-----------------------+------------------------+----------------------
  x and t2 are to      |                        |  t1 and x are to
  the right of [a, b[  |  x lies within [a, b[  |  the left of [a, b[
  -> check t1          |  -> check t1 and t2    |  -> check t2
...