Структуры данных. Деревья

1class BinaryTreeNode {
2	constructor(value) {
3		this.left = null;
4		this.right = null;
5		this.parent = null;
6		this.value = value;
7	}
8
9	get height() {
10		let leftHeight = this.left ? this.left.height + 1 : 0;
11		let rightHeight = this.right ? this.right.height + 1 : 0;
12		return Math.max(leftHeight, rightHeight);
13	}
14
15	//При вставке важно обновить все затронутые ссылки: left или right для родительского узла и parent для дочернего. Если у родителя уже был потомок, его свойство parent нужно обнулить.
16
17	setLeft(node) {
18		if (this.left) {
19			this.left.parent = null;
20		}
21		if (node) {
22			this.left = node;
23			this.left.parent = this;
24		}
25	}
26
27	setRight(node) {
28		if (this.right) {
29			this.right.parent = null;
30		}
31		if (node) {
32			this.right = node;
33			this.right.parent = this;
34		}
35	}
36}
37let aNode = new BinaryTreeNode('a');
38
39let bNode = new BinaryTreeNode('b');
40aNode.setLeft(bNode);
41
42let cNode = new BinaryTreeNode('c');
43aNode.setRight(cNode);
44
45let dNode = new BinaryTreeNode('d');
46bNode.setRight(dNode);
47
48let eNode = new BinaryTreeNode('e');
49cNode.setLeft(eNode);
50
51let fNode = new BinaryTreeNode('f');
52cNode.setRight(fNode);

1class BinarySearchTreeNode extends BinaryTreeNode {
2	constructor(value, comparator) {
3		super(value);
4		this.comparator = comparator;
5	}
6
7	insert(value) {
8		if (this.comparator(value, this.value) < 0) {
9			if (this.left) return this.left.insert(value);
10			let newNode = new BinarySearchTreeNode(value, this.comparator);
11			this.setLeft(newNode);
12
13			return newNode;
14		}
15
16		if (this.comparator(value, this.value) > 0) {
17			if (this.right) return this.right.insert(value);
18			let newNode = new BinarySearchTreeNode(value, this.comparator);
19			this.setRight(newNode);
20
21			return newNode;
22		}
23		return this;
24	}
25}
26
27class BinarySearchTree {
28	constructor(value, comparator) {
29		this.root = new BinarySearchTreeNode(value, comparator);
30		this.comparator = comparator;
31	}
32
33	insert(value) {
34		if (!this.root.value) this.root.value = value;
35		else this.root.insert(value);
36	}
37}
38
39const comparator = (a, b) => a - b;
40 /*если вернётся 0, значит, числа равны;
41если отрицательное число, значит, значение меньше искомого;
42если положительное число, значит, значение больше искомого. */
43
44const tree = new BinarySearchTree(14, comparator);
45tree.insert(9);
46tree.insert(124);
47tree.insert(3);
48tree.insert(19);
49tree.insert(45);
50tree.insert(1);
51tree.insert(8);
52tree.insert(59);

1//Добавляем в class BinarySearchTreeNode вспомогательные методы
2class BinarySearchTreeNode extends BinaryTreeNode {
3	// ...
4
5	//ищет минимальный элемент в поддереве
6	findMin() {
7		if (!this.left) {
8			return this;
9		}
10
11		return this.left.findMin();
12	}
13
14	// удаляет указанный элемент, если он является дочерним для данного узла.
15	removeChild(nodeToRemove) {
16		if (this.left && this.left === nodeToRemove) {
17			this.left = null;
18			return true;
19		}
20
21		if (this.right && this.right === nodeToRemove) {
22			this.right = null;
23			return true;
24		}
25
26		return false;
27	}
28
29	// заменяет дочерний элемент на новый.
30	replaceChild(nodeToReplace, replacementNode) {
31		if (!nodeToReplace || !replacementNode) {
32			return false;
33		}
34
35		if (this.left && this.left === nodeToReplace) {
36			this.left = replacementNode;
37			return true;
38		}
39
40		if (this.right && this.right === nodeToReplace) {
41			this.right = replacementNode;
42			return true;
43		}
44
45		return false;
46	}
47}
48
49// В class BinarySearchTree добавляем метод remove
50class BinarySearchTree {
51	//...
52
53	remove(value) {
54		const nodeToRemove = this.find(value);
55
56		if (!nodeToRemove) {
57			throw new Error("Item not found");
58		}
59
60		const parent = nodeToRemove.parent;
61
62		// Нет потомков, листовой узел
63		if (!nodeToRemove.left && !nodeToRemove.right) {
64			if (parent) {
65				// Удалить у родителя указатель на удаленного потомка
66				parent.removeChild(nodeToRemove);
67			} else {
68				// Нет родителя, корневой узел
69				nodeToRemove.value = undefined;
70			}
71		}
72
73		// Есть и левый, и правый потомки
74		else if (nodeToRemove.left && nodeToRemove.right) {
75			// Ищем минимальное значение в правом поддереве
76			// И ставим его на место удаляемого узла
77			const nextBiggerNode = nodeToRemove.right.findMin();
78
79			if (this.comparator(nextBiggerNode, nodeToRemove.right) === 0) {
80				// Правый потомок одновременно является минимальным в правом дереве
81				// то есть у него нет левого поддерева
82				// можно просто заменить удаляемый узел на его правого потомка
83				nodeToRemove.value = nodeToRemove.right.value;
84				nodeToRemove.setRight(nodeToRemove.right.right);
85			} else {
86				// Удалить найденный узел (рекурсия)
87				this.remove(nextBiggerNode.value);
88				// Обновить значение удаляемого узла
89				nodeToRemove.value = nextBiggerNode.value;
90			}
91		}
92
93		// Есть только один потомок (левый или правый)
94		else {
95			// Заменить удаляемый узел на его потомка
96			const childNode = nodeToRemove.left || nodeToRemove.right;
97
98			if (parent) {
99				parent.replaceChild(nodeToRemove, childNode);
100			} else {
101				this.root = childNode;
102			}
103		}
104
105		// Удалить ссылку на родителя
106		nodeToRemove.parent = null;
107
108		return true;
109	}
110}
111