BST – Двоичные деревья поиска

Задача

Разработать класс, реализующий функциональность дерева двоичного поиска.

Ссылка на условие http://java.mazurok.com/word-of-week/bst

Тесты

input output
put S 11.11 Ok
put E 22.22 Ok
put A 33.33 Ok
put R 44.44 Ok
put H 55.55 Ok
put C 66.66 Ok
put X 77.77 Ok
put M 88.88 Ok
size 8
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/8
.L1: (E->22.22)/6
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/3
…L3: (H->55.55)/2
….L4: (M->88.88)/1
.L1: (X->77.77)/1
delete E Ok
size 7
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/7
.L1: (H->55.55)/5
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/2
…L3: (M->88.88)/1
.L1: (X->77.77)/1
exit N/A

Критерий тестирования

В ходе тестирования мы добавляем 8 ключей с уникальными значениями. Затем мы определяем размер, минимальный и максимальный узлы, а также распечатываем все дерево, чтобы убедится, что оно имеет ожидаемою конфигурацию. Затем мы удаляем 1 ключ с серединным значением и повторяем вышеперечисленные операции, чтобы увидеть ожидаемые изменения в дереве.

Формат вывода:

Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов

Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
  2. Класс CountingBSTTestApp, реализующий тестовое приложение

Класс CountingBST

Все методы разделены на пары — один метод пары приватный, а другой — публичный. Это необходимо для того, чтобы передавать первым аргументом корень дерева, начиная с которого выполняются все операции. Каждый приватный метод содержит первым аргументом узел, начиная с которого будет выполнятся операция. Публичный метод вызывает приватный и передает ему в качестве первого аргумента корень дерева. Это относится к основным операциям на дереве:

  1. put — помещает ключ и значение в дерево
  2. get — извлекает значение по клчу
  3. size — возвращает количество узлов дерева
  4. min — находит узел с минимальным ключом
  5. max — находит узел с максимальным ключом
  6. delete — удаление по Хиббарду ( Coursera presentation )
  7. print — печать дерева

Помимо основных полей, необходимых для BST, узел содержит поле count, в котором содержится количество все узлов поддерева, корнем которого является данный узел, включая сам узел.

Класс CountingBSTTestApp

Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.

Ссылка на Ideone: https://ideone.com/b0xrPX

 

BinarySearchTree

Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.

Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.

Описание методов, реализованных в классе BinarySearchTree:

  • метод add():
    • если дерево пустое, то говорим, что корень — это наш узел;
    • сравниваем поступивший ключ с ключом узла:
      • если ключ меньше, то идём в левое поддерево;
      • если ключ равен, то задаём узлу новое поступившее значение;
      • если ключ больше, то идём в правое поддерево;
  • методы minKey() и maxKey():
    • по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
  • метод delete():
    • сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
    • если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
    • иначе находим в правом поддереве узел с минимальным ключом:
      • если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
      • если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;

Код программы (http://ideone.com/Z2hbBv):