400 lines
12 KiB
Markdown
400 lines
12 KiB
Markdown
|
---
|
|||
|
|
id: 587d8258367417b2b2512c82
|
|||
|
|
title: Видалення вузла з двома дочірніми елементами у двійковому дереві пошуку
|
|||
|
|
challengeType: 1
|
|||
|
|
forumTopicId: 301639
|
|||
|
|
dashedName: delete-a-node-with-two-children-in-a-binary-search-tree
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Найважчим для реалізації є видалення вузлів, що мають два дочірні елементи. При видаленні такого вузла утворюються два піддерева, які більше не з'єднані з вихідною структурою дерева. Як можна відновити їх з'єднання? Один з методів полягає у тому, аби знайти найменше значення у правому піддереві цільового вузла та замінити цільовий вузол саме цим значенням. Вибір заміни таким чином гарантує, що цей вузол буде більшим за кожен вузол лівого піддерева, новим батьківським вузлом якого він стає; але водночас він буде меншим за кожен вузол правого піддерева, новим батьківським вузлом якого він стає. Як тільки така заміна виконана, замінений вузол повинен потрібно вилучити з правого піддерева. Та навіть ця операція є підступною, оскільки заміна може бути листовим вузлом або ж і навіть батьківським елементом правого піддерева. Якщо це кінцевий вузол, ми повинні видалити посилання на нього у батьківському елементі. В іншому випадку він повинен бути правим дочірнім елементом цільового вузла видалення. У цьому разі ми повинні замінити цільове значення значенням заміни та зробити так, щоб цільовий вузол посилався на правий дочірній елемент заміни.
|
|||
|
|
|
|||
|
|
# --instructions--
|
|||
|
|
|
|||
|
|
Завершімо наш метод `remove` розглядом третього варіанту. Ми знову задали код для перших двох випадків. А тепер додайте код для обробки цільових вузлів з двома дочірніми елементами. Чи є граничні випадки, на які слід звернути увагу? А що робити, якщо дерево складається лише з трьох вузлів? Після завершення роботи наша операція видалення для двійкових дерев пошуку буде виконана. Чудово впоралися! Це досить складне завдання!
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
Повинна існувати структура даних `BinarySearchTree`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
}
|
|||
|
|
return typeof test == 'object';
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Двійкове дерево пошуку повинне мати метод `remove`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
return typeof test.remove == 'function';
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Спроба видалити відсутній елемент повинна повернути `null`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
return typeof test.remove == 'function' ? test.remove(100) == null : false;
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Якщо кореневий вузол не має дочірніх елементів, його видалення має встановити кореневе значення `null`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(500);
|
|||
|
|
test.remove(500);
|
|||
|
|
return typeof test.remove == 'function' ? test.inorder() == null : false;
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Метод `remove` повинен видалити з дерева листові вузли.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(5);
|
|||
|
|
test.add(3);
|
|||
|
|
test.add(7);
|
|||
|
|
test.add(6);
|
|||
|
|
test.add(10);
|
|||
|
|
test.add(12);
|
|||
|
|
test.remove(3);
|
|||
|
|
test.remove(12);
|
|||
|
|
test.remove(10);
|
|||
|
|
return typeof test.remove == 'function'
|
|||
|
|
? test.inorder().join('') == '567'
|
|||
|
|
: false;
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Метод `remove` повинен видалити вузли з одним дочірнім елементом.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
if (typeof test.remove !== 'function') {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(-1);
|
|||
|
|
test.add(3);
|
|||
|
|
test.add(7);
|
|||
|
|
test.add(16);
|
|||
|
|
test.remove(16);
|
|||
|
|
test.remove(7);
|
|||
|
|
test.remove(3);
|
|||
|
|
return test.inorder().join('') == '-1';
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Спроба видалити корінь з дерева, що складається з двох вузлів, має встановити коренем другий вузол.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
if (typeof test.remove !== 'function') {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(15);
|
|||
|
|
test.add(27);
|
|||
|
|
test.remove(15);
|
|||
|
|
return test.inorder().join('') == '27';
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Метод `remove` повинен видалити вузли з двома дочірніми елементами, зберігаючи при цьому структуру двійкового дерева пошуку.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
if (typeof test.remove !== 'function') {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(1);
|
|||
|
|
test.add(4);
|
|||
|
|
test.add(3);
|
|||
|
|
test.add(7);
|
|||
|
|
test.add(9);
|
|||
|
|
test.add(11);
|
|||
|
|
test.add(14);
|
|||
|
|
test.add(15);
|
|||
|
|
test.add(19);
|
|||
|
|
test.add(50);
|
|||
|
|
test.remove(9);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(11);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(14);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(19);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(3);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(50);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.remove(15);
|
|||
|
|
if (!test.isBinarySearchTree()) {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
return test.inorder().join('') == '147';
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Корінь слід видаляти з дерева, що містить три вузли.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(
|
|||
|
|
(function () {
|
|||
|
|
var test = false;
|
|||
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|||
|
|
test = new BinarySearchTree();
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
if (typeof test.remove !== 'function') {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
test.add(100);
|
|||
|
|
test.add(50);
|
|||
|
|
test.add(300);
|
|||
|
|
test.remove(100);
|
|||
|
|
return test.inorder().join('') == 50300;
|
|||
|
|
})()
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --after-user-code--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
BinarySearchTree.prototype = Object.assign(
|
|||
|
|
BinarySearchTree.prototype,
|
|||
|
|
{
|
|||
|
|
add: function(value) {
|
|||
|
|
var node = this.root;
|
|||
|
|
if (node == null) {
|
|||
|
|
this.root = new Node(value);
|
|||
|
|
return;
|
|||
|
|
} else {
|
|||
|
|
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;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return searchTree(node);
|
|||
|
|
}
|
|||
|
|
},
|
|||
|
|
inorder: function() {
|
|||
|
|
if (this.root == null) {
|
|||
|
|
return null;
|
|||
|
|
} else {
|
|||
|
|
var result = new Array();
|
|||
|
|
function traverseInOrder(node) {
|
|||
|
|
if (node.left != null) {
|
|||
|
|
traverseInOrder(node.left);
|
|||
|
|
}
|
|||
|
|
result.push(node.value);
|
|||
|
|
if (node.right != null) {
|
|||
|
|
traverseInOrder(node.right);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
traverseInOrder(this.root);
|
|||
|
|
return result;
|
|||
|
|
}
|
|||
|
|
},
|
|||
|
|
isBinarySearchTree() {
|
|||
|
|
if (this.root == null) {
|
|||
|
|
return null;
|
|||
|
|
} else {
|
|||
|
|
var check = true;
|
|||
|
|
function checkTree(node) {
|
|||
|
|
if (node.left != null) {
|
|||
|
|
var left = node.left;
|
|||
|
|
if (left.value > node.value) {
|
|||
|
|
check = false;
|
|||
|
|
} else {
|
|||
|
|
checkTree(left);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
if (node.right != null) {
|
|||
|
|
var right = node.right;
|
|||
|
|
if (right.value < node.value) {
|
|||
|
|
check = false;
|
|||
|
|
} else {
|
|||
|
|
checkTree(right);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
checkTree(this.root);
|
|||
|
|
return check;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## --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;
|
|||
|
|
this.remove = function(value) {
|
|||
|
|
if (this.root === null) {
|
|||
|
|
return null;
|
|||
|
|
}
|
|||
|
|
var target;
|
|||
|
|
var parent = null;
|
|||
|
|
// Find the target value and its parent
|
|||
|
|
(function findValue(node = this.root) {
|
|||
|
|
if (value == node.value) {
|
|||
|
|
target = node;
|
|||
|
|
} else if (value < node.value && node.left !== null) {
|
|||
|
|
parent = node;
|
|||
|
|
return findValue(node.left);
|
|||
|
|
} else if (value < node.value && node.left === null) {
|
|||
|
|
return null;
|
|||
|
|
} else if (value > node.value && node.right !== null) {
|
|||
|
|
parent = node;
|
|||
|
|
return findValue(node.right);
|
|||
|
|
} else {
|
|||
|
|
return null;
|
|||
|
|
}
|
|||
|
|
}.bind(this)());
|
|||
|
|
if (target === null) {
|
|||
|
|
return null;
|
|||
|
|
}
|
|||
|
|
// Count the children of the target to delete
|
|||
|
|
var children =
|
|||
|
|
(target.left !== null ? 1 : 0) + (target.right !== null ? 1 : 0);
|
|||
|
|
// Case 1: Target has no children
|
|||
|
|
if (children === 0) {
|
|||
|
|
if (target == this.root) {
|
|||
|
|
this.root = null;
|
|||
|
|
} else {
|
|||
|
|
if (parent.left == target) {
|
|||
|
|
parent.left = null;
|
|||
|
|
} else {
|
|||
|
|
parent.right = null;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
// Case 2: Target has one child
|
|||
|
|
else if (children == 1) {
|
|||
|
|
var newChild = target.left !== null ? target.left : target.right;
|
|||
|
|
if (parent === null) {
|
|||
|
|
target.value = newChild.value;
|
|||
|
|
target.left = null;
|
|||
|
|
target.right = null;
|
|||
|
|
} else if (newChild.value < parent.value) {
|
|||
|
|
parent.left = newChild;
|
|||
|
|
} else {
|
|||
|
|
parent.right = newChild;
|
|||
|
|
}
|
|||
|
|
target = null;
|
|||
|
|
}
|
|||
|
|
// Case 3: Target has two children
|
|||
|
|
// Only change code below this line
|
|||
|
|
};
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|