347 lines
11 KiB
Markdown
347 lines
11 KiB
Markdown
---
|
||
id: 587d8257367417b2b2512c7d
|
||
title: Знайдіть мінімальну та максимальну висоту двійкового дерева пошуку
|
||
challengeType: 1
|
||
forumTopicId: 301641
|
||
dashedName: find-the-minimum-and-maximum-height-of-a-binary-search-tree
|
||
---
|
||
|
||
# --description--
|
||
|
||
В останньому завданні ми описали ситуацію, коли двійкове дерево пошуку може стати незбалансованим. Щоб зрозуміти поняття балансу, розглянемо ще одну властивість дерева - його висоту. Висота дерева - це відстань від кореневого вузла до будь-якого заданого листового вузла. Різні шляхи в структурі дерева з великою кількістю гілок можуть мати неоднакову висоту. Однак для заданого дерева існує мінімальна та максимальна висота. Якщо дерево збалансоване, ці значення будуть відрізнятися максимум на одиницю. Це означає, що у збалансованому дереві всі листові вузли або існують в межах одного рівня; або, якщо це не так, відрізняються щонайбільше на один рівень.
|
||
|
||
Як властивість двійкових дерев пошуку, баланс має велике значення, оскільки він визначає ефективність операцій у дереві. Згідно з поясненням в останньому завданні, незбалансовані дерева є для нас чи не найскладнішим викликом. Самозбалансовані двійкові дерева пошуку зазвичай використовуються для розв'язання цієї проблеми в деревах з динамічними наборами даних. До таких належать АВЛ-дерева, червоно-чорні дерева та Б-дерева. Усі ці типи дерев містять додатковий внутрішній алгоритм, що перебалансовує дерево тоді, коли вставка чи вилучення елементів призводять до порушення його балансу.
|
||
|
||
**Примітка:**Окрім висоти, двійкові дерева пошуку мають подібну властивість - глибину. Вона позначає відстань від кореня до даного вузла.
|
||
|
||
# --instructions--
|
||
|
||
Для нашого двійкового дерева напишіть два методи: `findMinHeight` and `findMaxHeight`. Ці методи повинні повернути ціле значення для мінімальної та максимальної висоти в заданому двійковому дереві відповідно. Якщо вузол порожній, присвоїмо йому висоту `-1` (базовий випадок). І, нарешті, додайте третій метод `isBalanced`, який повертається як `true` or `false` в залежності від того, збалансоване дерево чи ні. Щоб це визначити, можна застосувати перші два методи, які ви щойно написали.
|
||
|
||
# --hints--
|
||
|
||
Повинна існувати структура даних `BinarySearchTree`.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof BinarySearchTree !== 'undefined') {
|
||
test = new BinarySearchTree();
|
||
}
|
||
return typeof test == 'object';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Двійкове дерево пошуку повинне мати метод під назвою `findMinHeight`.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof BinarySearchTree !== 'undefined') {
|
||
test = new BinarySearchTree();
|
||
} else {
|
||
return false;
|
||
}
|
||
return typeof test.findMinHeight == 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Двійкове дерево пошуку повинне мати метод під назвою `findMaxHeight`.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof BinarySearchTree !== 'undefined') {
|
||
test = new BinarySearchTree();
|
||
} else {
|
||
return false;
|
||
}
|
||
return typeof test.findMaxHeight == 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Двійкове дерево пошуку повинне мати метод під назвою `isBalanced`.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof BinarySearchTree !== 'undefined') {
|
||
test = new BinarySearchTree();
|
||
} else {
|
||
return false;
|
||
}
|
||
return typeof test.isBalanced == 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Метод під назвою `findMinHeight` повинен повертати мінімальну висоту дерева.
|
||
|
||
```js
|
||
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` повинен повертати максимальну висоту дерева.
|
||
|
||
```js
|
||
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`.
|
||
|
||
```js
|
||
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`.
|
||
|
||
```js
|
||
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`.
|
||
|
||
```js
|
||
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--
|
||
|
||
```js
|
||
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--
|
||
|
||
```js
|
||
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--
|
||
|
||
```js
|
||
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);
|
||
};
|
||
}
|
||
```
|