11 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 587d8257367417b2b2512c7d | Знайдіть мінімальну та максимальну висоту двійкового дерева пошуку | 1 | 301641 | find-the-minimum-and-maximum-height-of-a-binary-search-tree |
--description--
В останньому завданні ми описали ситуацію, коли двійкове дерево пошуку може стати незбалансованим. Щоб зрозуміти поняття балансу, розглянемо ще одну властивість дерева - його висоту. Висота дерева - це відстань від кореневого вузла до будь-якого заданого листового вузла. Різні шляхи в структурі дерева з великою кількістю гілок можуть мати неоднакову висоту. Однак для заданого дерева існує мінімальна та максимальна висота. Якщо дерево збалансоване, ці значення будуть відрізнятися максимум на одиницю. Це означає, що у збалансованому дереві всі листові вузли або існують в межах одного рівня; або, якщо це не так, відрізняються щонайбільше на один рівень.
Як властивість двійкових дерев пошуку, баланс має велике значення, оскільки він визначає ефективність операцій у дереві. Згідно з поясненням в останньому завданні, незбалансовані дерева є для нас чи не найскладнішим викликом. Самозбалансовані двійкові дерева пошуку зазвичай використовуються для розв'язання цієї проблеми в деревах з динамічними наборами даних. До таких належать АВЛ-дерева, червоно-чорні дерева та Б-дерева. Усі ці типи дерев містять додатковий внутрішній алгоритм, що перебалансовує дерево тоді, коли вставка чи вилучення елементів призводять до порушення його балансу.
**Примітка:**Окрім висоти, двійкові дерева пошуку мають подібну властивість - глибину. Вона позначає відстань від кореня до даного вузла.
--instructions--
Для нашого двійкового дерева напишіть два методи: findMinHeight and findMaxHeight. Ці методи повинні повернути ціле значення для мінімальної та максимальної висоти в заданому двійковому дереві відповідно. Якщо вузол порожній, присвоїмо йому висоту -1 (базовий випадок). І, нарешті, додайте третій метод isBalanced, який повертається як true or false в залежності від того, збалансоване дерево чи ні. Щоб це визначити, можна застосувати перші два методи, які ви щойно написали.
--hints--
Повинна існувати структура даних BinarySearchTree.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
}
return typeof test == 'object';
})()
);
Двійкове дерево пошуку повинне мати метод під назвою findMinHeight.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
return typeof test.findMinHeight == 'function';
})()
);
Двійкове дерево пошуку повинне мати метод під назвою findMaxHeight.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
return typeof test.findMaxHeight == 'function';
})()
);
Двійкове дерево пошуку повинне мати метод під назвою isBalanced.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
return typeof test.isBalanced == 'function';
})()
);
Метод під назвою findMinHeight повинен повертати мінімальну висоту дерева.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
if (typeof test.findMinHeight !== 'function') {
return false;
}
test.add(4);
test.add(1);
test.add(7);
test.add(87);
test.add(34);
test.add(45);
test.add(73);
test.add(8);
return test.findMinHeight() == 1;
})()
);
Метод findMaxHeight повинен повертати максимальну висоту дерева.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
if (typeof test.findMaxHeight !== 'function') {
return false;
}
test.add(4);
test.add(1);
test.add(7);
test.add(87);
test.add(34);
test.add(45);
test.add(73);
test.add(8);
return test.findMaxHeight() == 5;
})()
);
Порожнє дерево повинне повернути висоту -1.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
if (typeof test.findMaxHeight !== 'function') {
return false;
}
return test.findMaxHeight() == -1;
})()
);
Якщо двійкове дерево пошуку є незбалансованим, метод isBalanced повинен повернутися як false.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
if (typeof test.isBalanced !== 'function') {
return false;
}
test.add(4);
test.add(1);
test.add(7);
test.add(87);
test.add(34);
test.add(45);
test.add(73);
test.add(8);
return test.isBalanced() === false;
})()
);
Якщо двійкове дерево пошуку є збалансованим, метод isBalanced повинен повернутися як true.
assert(
(function () {
var test = false;
if (typeof BinarySearchTree !== 'undefined') {
test = new BinarySearchTree();
} else {
return false;
}
if (typeof test.isBalanced !== 'function') {
return false;
}
test.add(10);
test.add(3);
test.add(22);
test.add(1);
test.add(4);
test.add(17);
test.add(32);
return test.isBalanced() === true;
})()
);
--seed--
--after-user-code--
BinarySearchTree.prototype = Object.assign(
BinarySearchTree.prototype,
{
add: function(value) {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left);
}
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
}
} else {
return null;
}
}
var node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
return searchTree(node);
}
}
}
);
--seed-contents--
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
// Only change code below this line
// Only change code above this line
}
--solutions--
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
// Only change code below this line
// Only change code above this line
this.findMinHeight = function(root = this.root) {
// empty tree.
if (root === null) {
return -1;
}
// leaf node.
if (root.left === null && root.right === null) {
return 0;
}
if (root.left === null) {
return this.findMinHeight(root.right) + 1;
}
if (root.right === null) {
return this.findMinHeight(root.left) + 1;
}
const lHeight = this.findMinHeight(root.left);
const rHeight = this.findMinHeight(root.right);
return Math.min(lHeight, rHeight) + 1;
};
this.findMaxHeight = function(root = this.root) {
// empty tree.
if (root === null) {
return -1;
}
// leaf node.
if (root.left === null && root.right === null) {
return 0;
}
if (root.left === null) {
return this.findMaxHeight(root.right) + 1;
}
if (root.right === null) {
return this.findMaxHeight(root.left) + 1;
}
const lHeight = this.findMaxHeight(root.left);
const rHeight = this.findMaxHeight(root.right);
return Math.max(lHeight, rHeight) + 1;
};
this.isBalanced = function(root = this.root) {
if (root === null) {
return true;
}
if (root.left === null && root.right === null) {
return true;
}
if (root.left === null) {
return this.findMaxHeight(root.right) <= 0;
}
if (root.right === null) {
return this.findMaxHeight(root.left) <= 0;
}
const lHeight = this.findMaxHeight(root.left);
const rHeight = this.findMaxHeight(root.right);
if (Math.abs(lHeight - rHeight) > 1) {
return false;
}
return this.isBalanced(root.left) && this.isBalanced(root.right);
};
}