Data Structures. Trees

27 ноября 2023 г.

This is a short expanded summary of the section about trees in the book Computer Science Guide by William Springer.

Basic information

A tree is simply a connected graph with no cycles. One vertex is designated as the root, and all other vertices are defined by their relationship to the root.

An example of a tree is the DOM tree.

The following definitions are equivalent for a tree:

an acyclic graph in which adding any edge creates a simple cycle (a cycle with no repeated vertices);
a connected graph that becomes disconnected if any edge is removed;
a graph in which any two vertices are connected by a unique simple path.

Types of nodes

A tree has two types of nodes:

internal nodes — nodes with at least one child
leaves — nodes with no children

Below is an example of a tree with ten vertices and one internal node.

Besides binary trees, trees with four nodes (quadtrees) are also widely used in practice. They are used in game development to organize grids. Each node in such a tree represents one direction (northwest, southeast, and so on).

Basic operations

add a node (add)
remove a node by value (remove)
find a node by value (find)
traverse all elements (traverse)

If needed, this list can be extended with more complex algorithms:

insert/remove subtree
insert/remove branch
insert element at a specific position
find lowest common ancestor of two nodes

JavaScript implementation

Array-based representation

(Example taken from a reference site)

[3, 2, [3, 8], [[8], 3]];

Where:

the entire array is the root
elements are children
a non-array child is a leaf
an array child is an internal node with its own children

Node-based representation (linked structure)

(Example taken from this website)

JavaScript

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	// When inserting, it is important to update all affected references: left or right for the parent node and parent for the child node. If the parent already had a child, its parent property should be set to null.
16
17
18	setLeft(node) {
19		if (this.left) {
20			this.left.parent = null;
21		}
22		if (node) {
23			this.left = node;
24			this.left.parent = this;
25		}
26	}
27
28	setRight(node) {
29		if (this.right) {
30			this.right.parent = null;
31		}
32		if (node) {
33			this.right = node;
34			this.right.parent = this;
35		}
36	}
37}
38let aNode = new BinaryTreeNode('a');
39
40let bNode = new BinaryTreeNode('b');
41aNode.setLeft(bNode);
42
43let cNode = new BinaryTreeNode('c');
44aNode.setRight(cNode);
45
46let dNode = new BinaryTreeNode('d');
47bNode.setRight(dNode);
48
49let eNode = new BinaryTreeNode('e');
50cNode.setLeft(eNode);
51
52let fNode = new BinaryTreeNode('f');
53cNode.setRight(fNode);

Binary Search Trees (BST)

A Binary Search Tree (BST) is a rooted binary tree where each node has at most two children.

It is defined recursively:

the root key is greater than or equal to the left child key (if it exists)
the right child key is always greater than or equal to the root key

This ordering makes searching efficient because half of the tree can be ignored at each step.

Time complexity is proportional to tree height — the length of the longest path from root to leaf.

In the general case, this is Θ(lg n).

The Θ notation means that the execution time is bounded both from above and below; the height of the tree must be at least lg n.

In the worst case (when each node has only one child, which essentially turns the tree into a linked list — an unbalanced binary search tree), the complexity is O(n).

Below is an example of an unbalanced binary tree.

A binary search tree can be implemented as a collection of linked nodes — each node contains a key and pointers to the left and right child nodes, as well as to the parent node.

JavaScript implementation

The examples are taken from this website.

The first added node becomes the root of the tree.

Next, we compare the value of the new element with the value of the parent node. If it is greater, we place the element in the left branch; if it is smaller, we place it in the right branch.

Adding an element

We build the tree in the same way as in the previous example, but this time we add a new method for inserting elements. This method compares values and places the element into the appropriate branch.

JavaScript

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/*
41If 0 is returned, it means that the numbers are equal;
42if a negative number is returned, it means the value is less than the target value;
43if a positive number is returned, it means the value is greater than the target value.
44*/
45
46const tree = new BinarySearchTree(14, comparator);
47tree.insert(9);
48tree.insert(124);
49tree.insert(3);
50tree.insert(19);
51tree.insert(45);
52tree.insert(1);
53tree.insert(8);
54tree.insert(59);

All new values greater than the root go to the left branch, while smaller values go to the right branch. Therefore, the tree in the example above should look like this:

Deleting an element

To delete a node d, we need to find it in the tree and then perform the following steps:

If d has no children — set the pointer of the parent node that currently references d to null.
If d has one child — the child takes the place of d.
If d has two children — find the next node in order (the minimum node in the right subtree of the node being deleted) and replace d with it.

JavaScript

1// Add helper methods to the BinarySearchTreeNode class
2class BinarySearchTreeNode extends BinaryTreeNode {
3	// ...
4
5	// Find the minimum element in the subtree
6	findMin() {
7		if (!this.left) {
8			return this;
9		}
10
11		return this.left.findMin();
12	}
13
14	// Remove the specified element if it is a child of this node.
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	// Replace a child element with a new one.
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// Add the remove method to the BinarySearchTree class
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		// No children, leaf node
63		if (!nodeToRemove.left && !nodeToRemove.right) {
64			if (parent) {
65				// Remove the pointer to the deleted child from the parent node
66				parent.removeChild(nodeToRemove);
67			} else {
68				// No parent, root node
69				nodeToRemove.value = undefined;
70			}
71		}
72
73		// Has both left and right children
74		else if (nodeToRemove.left && nodeToRemove.right) {
75			// Find the minimum value in the right subtree
76            // And place it in the position of the deleted node
77			const nextBiggerNode = nodeToRemove.right.findMin();
78
79			if (this.comparator(nextBiggerNode, nodeToRemove.right) === 0) {
80				// The right child is also the minimum value in the right subtree,
81                // meaning it has no left subtree.
82                // We can simply replace the deleted node with its right child.
83
84				nodeToRemove.value = nodeToRemove.right.value;
85				nodeToRemove.setRight(nodeToRemove.right.right);
86			} else {
87				// Delete the found node (recursion)
88				this.remove(nextBiggerNode.value);
89				// Update the value of the node being deleted
90				nodeToRemove.value = nextBiggerNode.value;
91			}
92		}
93
94		// Has only one child (left or right)
95		else {
96			// Replace the deleted node with its child
97			const childNode = nodeToRemove.left || nodeToRemove.right;
98
99			if (parent) {
100				parent.replaceChild(nodeToRemove, childNode);
101			} else {
102				this.root = childNode;
103			}
104		}
105
106		// Remove the reference to the parent
107		nodeToRemove.parent = null;
108
109		return true;
110	}
111}
112

Balanced Binary Search Trees

A self-balancing binary search tree is a tree that automatically maintains a small height (compared to the number of required levels), regardless of adding or deleting nodes.

Its height can be greater than the minimum possible height, but it will still be Θ(lg n).

Red-Black Tree — All keys are stored in internal nodes, while the leaves are null (NIL) nodes. Each node is either red or black: the root and all leaves are black, and the children of a red node must be black. Every path from a node to any leaf must contain the same number of black nodes. The path from the root to the farthest leaf is at most twice as long as the path from the root to the nearest leaf. This is because the shortest possible path consists entirely of black nodes, while the longest possible path alternates between red and black nodes. As a result, no path can be more than twice as long as any other.
Splay Tree
Treap (Cartesian Tree)