287 lines
7.0 KiB
Markdown
287 lines
7.0 KiB
Markdown
---
|
|
id: 587d8258367417b2b2512c81
|
|
title: Eliminare un nodo con un figlio in un albero binario di ricerca
|
|
challengeType: 1
|
|
forumTopicId: 301638
|
|
dashedName: delete-a-node-with-one-child-in-a-binary-search-tree
|
|
---
|
|
|
|
# --description--
|
|
|
|
Ora che sappiamo eliminare i nodi foglia, passiamo al secondo caso: eliminare un nodo con un figlio. Per questo caso, supponiamo di avere un albero con i seguenti nodi 1 — 2 — 3 dove 1 è la radice. Per eliminare il 2, dobbiamo semplicemente far puntare il riferimento destro in 1 a 3. Più in generale per eliminare un nodo con un solo figlio, facciamo in modo che il genitore di quel nodo faccia riferimento al nodo successivo nell'albero.
|
|
|
|
# --instructions--
|
|
|
|
Abbiamo messo nel nostro metodo `remove` del codice che esegue le attività dall'ultima sfida. Troviamo l'obiettivo da eliminare e il suo genitore e determiniamo il numero di figli che ha il nodo di destinazione. Aggiungiamo qui il caso successivo per i nodi con un solo figlio. Qui dovremo determinare se il singolo figlio è un ramo sinistro o destro nell'albero e quindi impostare il riferimento corretto nel genitore in modo che punti a questo nodo. Inoltre, teniamo conto del caso in cui l'obiettivo è il nodo radice (questo significa che il nodo padre sarà `null`). Sentiti libero di sostituire tutto il codice iniziale con il tuo purché superi i test.
|
|
|
|
# --hints--
|
|
|
|
La struttura dati `BinarySearchTree` dovrebbe esistere.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
}
|
|
return typeof test == 'object';
|
|
})()
|
|
);
|
|
```
|
|
|
|
L'albero binario di ricerca dovrebbe avere un metodo chiamato `remove`.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
return typeof test.remove == 'function';
|
|
})()
|
|
);
|
|
```
|
|
|
|
Tentare di rimuovere un elemento che non esiste dovrebbe restituire `null`.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.remove !== 'function') {
|
|
return false;
|
|
}
|
|
return test.remove(100) == null;
|
|
})()
|
|
);
|
|
```
|
|
|
|
Se il nodo radice non ha figli, l'eliminazione dovrebbe impostare la radice a `null`.
|
|
|
|
```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(500);
|
|
test.remove(500);
|
|
return test.inorder() == null;
|
|
})()
|
|
);
|
|
```
|
|
|
|
Il metodo `remove` dovrebbe rimuovere i nodi foglia dall'albero.
|
|
|
|
```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(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 test.inorder().join('') == '567';
|
|
})()
|
|
);
|
|
```
|
|
|
|
Il metodo `remove` dovrebbe rimuovere i nodi con un figlio.
|
|
|
|
```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(2);
|
|
test.add(6);
|
|
test.add(8);
|
|
test.remove(6);
|
|
test.remove(3);
|
|
return test.inorder().join('') == '1248';
|
|
})()
|
|
);
|
|
```
|
|
|
|
Rimuovere la radice in un albero con due nodi dovrebbe impostare il secondo come radice.
|
|
|
|
```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';
|
|
})()
|
|
);
|
|
```
|
|
|
|
# --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;
|
|
}
|
|
}
|
|
}
|
|
);
|
|
```
|
|
|
|
## --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
|
|
// Only change code below this line
|
|
};
|
|
}
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
// solution required
|
|
```
|