search

Kovalevskyi-Academy / Zeus

Other
2 stars 4 forks source link

AWJ W2 D0 Некорректно работают 2 теста: addNodeWithOneLeftNode() и addNodeWithOneRightNode() #139

Open irekminn opened 2 years ago

irekminn commented 2 years ago

Всем привет. Необходимо поправить 2 теста:

  1. public void addNodeWithOneLeftNode()
  2. public void addNodeWithOneRightNode()

Оба теста, после добавления node к root, требуют изменение полей:

Truth.assertWithMessage("checking addNode has correct newMaxDepth").that(node.maxDepth()).isEqualTo(2); Truth.assertWithMessage("checking addNode has correct newMinDepth").that(node.minDepth()).isEqualTo(2);

Эти поля у node должны остаться по умолчанию, а вот у root maxDepth должно меняться. Предлагаю поправить так: root:

Truth.assertWithMessage("checking addNode has correct newMaxDepth").that(root.maxDepth()).isEqualTo(2); Truth.assertWithMessage("checking addNode has correct newMinDepth").that(root.minDepth()).isEqualTo(1);

node:

Truth.assertWithMessage("checking addNode has correct newMaxDepth").that(node.maxDepth()).isEqualTo(1); Truth.assertWithMessage("checking addNode has correct newMinDepth").that(node.minDepth()).isEqualTo(1);

Т.е. при добавлении ноды меняется поле maxDepth или minDepth, в зависимости в какую ветку добавляем, только у той ноды к которой добавляем, в данном случае у ноды root. Проверка на изменение полей реализована в каждом тесте в двух местах. В обоих случаях проверка содержит ошибку.

irekminn commented 2 years ago

В связи с разногласиями по поводу необходимости изменения логики проверки приведу один, на мой взгляд, "убийственный" пример-аргумент в пользу необходимости поменять логику:

  1. Создаем root ноду со значением 10. Значение maxDepth и minDepth по умолчанию: 1. Тут вопросов нет.
  2. Принимаем новое значение 12.
  3. Добавляем его в правое поддерево, изменяем maxDepth и minDepth у ноды root, в соответствии с существующим вариантом, каждое на значение 2, т.е. maxDepth 2 и minDepth 2. Все еще нет никаких вопросов.
  4. Бах....принимаем новое значение 15...чувствуете к чему все идет? Если нет то продолжим. Приняли значение 15
  5. Повторим все шаги с 2 по 3. Далее принимаем 20..24...55..70....235...1086... Через некоторое время.... Принимаем значение 1000_000 . Добавляем его в правое поддерево. Изменяем maxDepth и minDepth у root на 1000_000

Радуемся жизни и думаем что у нас сбалансированное дерево. Ведь метод, который проверяет дерево на баланс ( needBalancing(IntTreeNode root)) не видит ничего странного. Конечно, куда ему..У нас же maxDepth и minDepth одинаковые: по 1000_000 В реальности же наше дерево выродилось в простой список из 1000_000 элементов, каждый из которых больше значения ноды root (10).

Немного картинок. Для простоты понимания:

image

А теперь как должно быть:

image