Дерево AVL в ML — повернуть влево, предупреждение: соответствие неполному

Я реализую дерево AVL в SML:

Вот мои типы данных:

datatype 'a AVLTree = Nil | Br of ((int*('a))*('a AVLTree)*('a AVLTree));
datatype Balance = RR | LR | LL | RL;
exception NotFound;
exception NullValue

Сейчас я пишу функцию Rotate-Left, и я написал ее следующим образом:

fun rotate_left Nil = Nil
     |rotate_left (Br(x,A,Br(y,B,C))) = (Br(y,Br(x,A,B),C));

Я получаю от переводчика:

Предупреждение: соответствие не является исчерпывающим

Как мне исправить это с текущими типами данных, которые у меня есть? Я пытался использовать подстановочные знаки, но безуспешно.


avl-tree sml
person genericname    schedule 24.05.2018    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я получаю от переводчика:

Warning: match nonexhaustive

Как мне исправить это с текущими типами данных, которые у меня есть? [...]

Возможно, этого предупреждения не следует избегать. Можно ведь не поворачивать все деревья.

Левое вращение будет выглядеть так:

  A              B
 / \            / \
…   B     ~>   A   C
   / \        / \ / \
  …   C      …   …   …
     / \
    …   …

Учитывая тип дерева AVL, который не отслеживает высоту,

datatype 'a AVLTree = Nil | Br of 'a * 'a AVLTree * 'a AVLTree

(круглые скобки не нужны) ваша версия rotate_left верна. Я переписал его ниже и переименовал левую и правую подветви. Во-первых, левая подветвь B становится новой правой подветвью A.

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)

Это частичная функция, и шаблоны, которым она не соответствует, следующие:

  • Nil - но левое вращение пустого дерева не определено четко.

  • Br (a, leftA, Nil) — но следующее левое вращение также не определено четко:

      A             ?
 / \           / \
…   Nil   ~>  A   …
             / \
            …   ?

Если бы вы попытались выполнить левое вращение одного из этих деревьев, не было бы осмысленного результата. Наличие Warning: match nonexhaustive тоже не удовлетворяет. Вместо этого вы можете вызвать значимое исключение, например.

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)
  | rotate_left _ = raise Fail "Invalid left-rotation"

Теперь вы так и не объяснили, почему в вашем определении типа данных есть лишний int. Может быть, это заранее вычисленная высота дерева? Это было бы здорово (вы могли бы закодировать это значение, используя псевдоним типа), поскольку тогда ваша проверка инвариантности становится дешевле. В этом случае левое вращение должно обновить высоты:

type height = int
datatype 'a AVLTree = Nil | Br of height * 'a * 'a AVLTree * 'a AVLTree

Согласно верхнему рисунку, новая высота A равна max(height(leftA), height(leftB)) + 1, а новая высота B — max(height(new A), height(rightB)). Расширение функции rotate_left для этого:

fun height Nil = 0
  | height (Br (h, _, _, _)) = h

fun rotate_left (Br (ha, a, leftA, Br (hb, b, leftB, rightB))) =
    let val ha' = Int.max (height leftA, height leftB) + 1
        val hb' = Int.max (ha', height rightB) + 1
    in Br (hb', b, Br (ha', a, leftA, rightB), rightB) end
  | rotate_left _ = raise Fail "Invalid left-rotation"

Изменить: мне приходит в голову, что дополнительный int находится во вложенном кортеже и поэтому, вероятно, превращает дерево в сопоставление некоторого целого числа с некоторым 'a. В этом случае пренебрегайте оптимизацией сохранения высоты в дереве.

person Simon Shine    schedule 28.05.2018

arrow_upward
1
arrow_downward

Ваша функция не определена для значений формы Br(x, A, NIL).

Что должно произойти в этом случае?

fun rotate_left Nil = Nil
  | rotate_left (Br(x,A,Br(y,B,C))) = (Br(y,Br(x,A,B),C))
  | rotate_left (Br(x, A, Nil)) = (* ??? *);
person tbrk    schedule 24.05.2018

arrow_upward
0
arrow_downward

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

 fun RL node =
  case node of Br(x,A,Br(y,B,C)) => (Br(y,Br(x,A,B),C))
                             | _ => node;
person genericname    schedule 24.05.2018