Дерево AVL в ML- Повернуть влево, Внимание: совпадение не исчерпывающее

Question

Я реализую дерево 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));

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

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

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

Answer 1

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

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

Answer 2

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

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) - но следующее вращение влево также не очень хорошо-defined:

    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

Согласно верхнему рисунку, новая высота А равна max(height(leftA), height(leftB)) + 1, а новая высота Б 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 .В этом случае не обращайте внимания на оптимизацию сохранения высоты в дереве.

Answer 3

Ваша функция не определена для значений с формой 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)) = (* ??? *);