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

 

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

  1. Очень качественно реализованная структура двоичного дерева поиска, хорошая структуризация программы, засчитано, 20 баллов.

  2. Уважаемый Александр Сергеевич, простите что пишу в комментариях, ноя сегодня посмотрел на таблицу оценок на сайте, и там у меня выставлено 91, хотя вы уже мне поставили 85. Я просто не понял ситуацию, какая у меня действительно выходит оценка?

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *