Translator: sea_ljf

The original link

Many data structures, such as maps, sets, etc., have a Tree as their underlying data structure. Also, a quick search of the database uses trees. HTML DOM nodes are also represented by a tree. These are just a few examples of trees. In this article, we will explore different types of trees, such as binary trees, binary search trees, and how to implement them.

In the last article, we looked at data structures: graphs, which are tree generalizations. Let’s start learning about trees!

This is part of the following tutorial:

Data Structures and Algorithms (DSA) for Beginners

  1. Time complexity of algorithms and large O notation
  2. Eight time complexities every Programmer should know
  3. Data structures beginners should know: Array, HashMap, and List
  4. Data structure that beginners should know: Graph
  5. Data structures beginners should know: Tree 👈 is this article
  6. Self-balanced binary search tree
  7. Appendix I: Analysis of recursive algorithms

Basic concepts of trees

In a tree, each node can have zero or more child nodes, each containing a value. As with graphs, the connections between nodes are called edges. Trees are a kind of graph, but not all graphs are trees (only acyclic undirected graphs are trees).

This data type is called a tree because it looks like an (inverted) tree 🌳. It starts at the root, its children are its branches, and nodes without any children are the leaves of the tree.

Here are some properties of the tree:

  • The topmost node is called the root node.
  • A node without any children is called a leaf node or terminal node.
  • Of the treeThe degree ofHeight is the distance between the deepest leaf node and the root node (i.e. the number of edges).
    • ATheta is 3.
    • IThe degree of I is 0.
  • The depth of the(Depth) orlevel(level) is the distance between a node and the root node.
    • HThe level of theta is 2.
    • BThe level of theta is 1.

A simple implementation of a tree

As we saw earlier, the node of the tree has a value and holds references to each of its children.

Here is an example of a node:

class TreeNode { constructor(value) { this.value = value; this.descendents = []; }}Copy the code

We can create a tree with three leaf nodes:

// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');
// associate root with is descendents
abe.descendents.push(homer);
homer.descendents.push(bart, lisa, maggie);
Copy the code

And there we are, we have a tree!

! [] (p0.ssl.qhimg.com/t01516921af… “”Simpson tree data structure””)

Abe is the root node, while Bart, Lisa, and Maggie are the leaves of the tree. Note that a tree node can have any number of children, whether zero, one, three, or more.

Binary tree

A node in a tree can have zero or more child nodes. However, when a tree can have at most two children, such a tree is called a binary tree.

Binary tree is one of the most common forms of trees. It is widely used, such as:

  • Maps
  • Sets
  • The database
  • Priority queue
  • Query corresponding information in Lightweight Directory Access Protocol (LDAP).
  • In XML/HTML files, search is performed using the Document Object Model (DOM) interface.

Perfect binary tree, perfect binary tree, perfect binary tree

Depending on how the nodes of a binary tree are organized, a binary tree can be a perfect binary tree, a perfect binary tree or a perfect binary tree.

  • Full binary tree: Excluding leaf nodes, each node has two child nodes.
  • Complete binary tree: All nodes except the deepest layer must have two child nodes.
  • Perfect binary tree: A tree with all the leaves in the last layer (i.e. forming a Perfect triangle).

(Translator’s note: The definition is different at home and abroad, and it is modified according to the original text and the source of the search, using the foreign standard)

Here is an example of the above concepts:

! [] (p0.ssl.qhimg.com/t01b0d1575b… “”Full vs. Complete vs. Perfect Binary Tree””)

Perfect binomial trees, perfect binomial trees and perfect binomial trees are not always mutually exclusive:

  • Perfect binary treenecessarilyIt’s a perfect binary tree and a perfect binary tree.
    • A perfect binary tree has exactly 2 to the k minus 1 node, where K is the deepest level of the tree (starting at 1). .
  • A perfect binary tree is not always a perfect binary tree.
    • As in the complete binary tree example above, the gray node on the far right is the only child node of its parent point. If you remove it, this tree is both a perfect binary tree and a perfect binary tree. (Translator’s note: The tree is not a complete binary tree with the gray node, because a complete binary tree requires left alignment.)
  • Perfect binomial trees are not necessarily perfect and perfect binomial trees.

Binary search tree (BST)

Binary Search Tree (BST) is a specific application of Binary Tree. Each node of a BST, like a binary tree, can have at most two child nodes. However, the value of the left child of the BST must be less than the value of the parent, and the value of the right child must be greater than the value of the parent.

To emphasize: some BST nodes do not allow duplicates to be added to the tree. If allowed, the duplicates are used as right child nodes. Some implementations of binary search trees record duplicates (which is what we need to implement next).

Let’s realize binary search tree!

The realization of the BST

The BST implementation is similar to the tree implementation above, but differs in two ways:

  • A node can have a maximum of two child nodes.
  • The value of the node satisfies the following relation:Left child < parent < right child.

Here is the tree node implementation, similar to the previous tree implementation, but with getters and setters for the left and right child nodes. Note that references to the parent node are kept in the instance and updated when new child nodes are added.

const LEFT = 0; const RIGHT = 1; class TreeNode { constructor(value) { this.value = value; this.descendents = []; this.parent = null; / / that the original is not the following two attributes, but does not add to the realization of the words below complains enclosing newNode. IsParentLeftChild = false; this.meta = {}; } get left() { return this.descendents[LEFT]; } set left(node) { this.descendents[LEFT] = node; if (node) { node.parent = this; } } get right() { return this.descendents[RIGHT]; } set right(node) { this.descendents[RIGHT] = node; if (node) { node.parent = this; }}}Copy the code

OK, now you are ready to add the left and right child nodes. Next, you write the BST class so that it satisfies the left child < parent < right child.

class BinarySearchTree { constructor() { this.root = null; this.size = 0; } add(value) { /* ... */ } find(value) { /* ... */ } remove(value) { /* ... */ } getMax() { /* ... */ } getMin() { /* ... * /}}Copy the code

Let’s start with the code that inserts the new node.

Insert the BST node

To insert a new node into the binary search tree, we need the following three steps:

  1. If there are no nodes in the tree, the first node becomes the root node.
  2. Compare (the value of the newly inserted node) with the root node or tree node in the tree, ifA biggerIs placed in the right subtree (for the next comparison), or in the left subtree (for comparison). If the values are the same, they are added repeatedly. You can increase the number of repeated nodes.
  3. Repeat the second step until a space is found to insert a new node.

Let’s use the following example to illustrate that 30, 40, 10, 15, 12, 50 will be inserted in the tree:

! [] (p0.ssl.qhimg.com/t011df4b16e… “”Inserting nodes on a Binary Search Tree (BST)””)

The code implementation is as follows:

add(value) { const newNode = new TreeNode(value); if (this.root) { const { found, parent } = this.findNodeAndParent(value); if (found) { // duplicated: value already exist on the tree found.meta.multiplicity = (found.meta.multiplicity || 1) + 1; } else if (value < parent.value) { parent.left = newNode; / / that the original is not the line of code, but don't add to below complains newNode. IsParentLeftChild = true; } else { parent.right = newNode; } } else { this.root = newNode; } this.size += 1; return newNode; }Copy the code

We used a helper function called findNodeAndParent. If the node (with the same value as the newly inserted node) already exists in the tree, increment the count of duplicate nodes by one. Let’s see how this helper function is implemented:

findNodeAndParent(value) {
  let node = this.root;
  let parent;
  while (node) {
    if (node.value === value) {
      break;
    }
    parent = node;
    node = ( value >= node.value) ? node.right : node.left;
  }
  return { found: node, parent };
}
Copy the code

FindNodeAndParent searches for values along the structure of the tree. It starts at the root node and searches left or right, depending on the value of the node. If a node with the same value already exists, the function returns the found node (that is, the node with the same value) and its parent node. If there are no nodes with the same value, the last node found (the node that will become the parent of the newly inserted node) is returned.

The BST node is deleted

Now that we know how to insert and find values (in binary search trees), we will implement deletion. This is a little more complicated than inserting, so let’s use the following example:

Remove leaf nodes (that is, nodes without any children)

    30                             30
 /     \         remove(12)     /     \
10      40       --------->    10      40
  \    /  \                      \    /  \
  15  35   50                    15  35   50
  /
12*
Copy the code

Simply remove the reference to node #12 that is held in the parent node (node #15).

Deletes a node that has a child node

    30                              30
 /     \         remove(10)      /     \
10*     40       --------->     15      40
  \    /  \                            /  \
  15  35   50                         35   50
Copy the code

In this case, we replace the reference to child node #10 held in parent node #30 with a reference to child node #15.

Delete a node with two child nodes

   30                              30
 /     \         remove(40)      /     \
15      40*      --------->     15      50
       /  \                            /
      35   50                         35
Copy the code

Node #40 to be deleted has two children (#35 and #50). We replace the node to be deleted with node #50. The left child node #35 to be deleted will remain in place, but its parent has been replaced.

Another way to remove node #40 is to move the left child node #35 to the position of node #40, leaving the right child unchanged.

30 / \ 15 35\50Copy the code

Both forms work because they follow the binary search tree rule: left child < parent < right child.

Deleting a root Node

   30*                            50
 /     \       remove(30)      /     \
15      50     --------->     15      35
       /
      35
Copy the code

Removing the root node is similar to the mechanism discussed earlier. The only difference is that the reference to the root node in the binary search tree instance needs to be updated.

The following animation shows the above operation in detail:

! [] (p0.ssl.qhimg.com/t01ae013251… “”Removing a node with 0, 1, 2 children from a binary search tree””)

In the animation, the node being moved is the left child or the left subtree, and the right child or the right subtree remains the same.

Now that we have an idea about deleting nodes, let’s implement it:

remove(value) { const nodeToRemove = this.find(value); if (! nodeToRemove) return false; // Combine left and right children into one subtree without nodeToRemove const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove); if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) { nodeToRemove.meta.multiplicity -= 1; // handle duplicated } else if (nodeToRemove === this.root) { // Replace (root) node to delete with the combined subtree. this.root = nodeToRemoveChildren; this.root.parent = null; // clearing up old parent } else { const side = nodeToRemove.isParentLeftChild ? 'left' : 'right'; const { parent } = nodeToRemove; // get parent // Replace node to delete with the combined subtree. parent[side] = nodeToRemoveChildren; } this.size -= 1; return true; }Copy the code

Here are a few things to look out for in the implementation:

  • First, search for whether the node to be deleted exists. If it does not exist, returnfalse.
  • If the node to be deleted exists, merge its left subtree into the right subtree to form a new subtree.
  • Replace the node to be deleted with the combined subtree.

The function to combine left subtrees into right subtrees is as follows:

CombineLeftIntoRightSubtree (node) {if (node. Right) {/ /, Const leftLeast = this.getLeftleast (node.right); const leftLeast = this.getLeftleast (node.right); leftLeast.left = node.left; return node.right; } return node.left; }Copy the code

As shown in the following example, we want to delete node #30 and merge the left subtree of the node to be deleted into the right subtree. The result is as follows:

   30*                             40
 /     \                          /  \
10      40    combine(30)       35   50
  \    /  \   ----------->      /
  15  35   50                  10
                                \
                                 15
Copy the code

Now make the root of the new subtree the root of the entire binary tree, and node #30 will no longer exist!

Traversal of binary trees

According to the order of traversal, there are several forms of traversal of binary tree: middle-order traversal, pre-order traversal and post-order traversal. We can also use the DFS or BFS we learned in Graph, a Data structure Beginners should know, to traverse the entire tree. Here is the concrete implementation:

In-order Traversal

The middle order traversal accesses nodes in the following order: left child node, node itself, and right child node.

* inOrderTraversal(node = this.root) { if (node.left) { yield* this.inOrderTraversal(node.left); } yield node; if (node.right) { yield* this.inOrderTraversal(node.right); }}Copy the code

Take this tree as an example:

10 / \ 5 30 / / \ 4 15 40/3Copy the code

A middle-order traversal outputs the corresponding values in the following order: 3, 4, 5, 10, 15, 30, 40. That is, if the tree to be traversed is a binary search tree, the output values will be in ascending order.

Post-order Traversal

The nodes are accessed in the following order: left child node, right child node, and node itself.

* postOrderTraversal(node = this.root) {
    if (node.left) { yield* this.postOrderTraversal(node.left); }
    if (node.right) { yield* this.postOrderTraversal(node.right); }
    yield node;
  }
Copy the code

The subsequent traversal outputs the corresponding values in the following order: 3, 4, 5, 15, 40, 30, 10.

Pre-order Traversal and DFS

Nodes are accessed in the order of the node itself, the left child node, and the right child node.

* preOrderTraversal(node = this.root) { yield node; if (node.left) { yield* this.preOrderTraversal(node.left); } if (node.right) { yield* this.preOrderTraversal(node.right); }}Copy the code

Preemptive traversal outputs the corresponding values in the following order: 10, 5, 4, 3, 30, 15, 40. The order is consistent with depth-first search (DPS).

Breadth First Search (BFS)

Tree BFS can be implemented via queues:

* bfs() {
    const queue = new Queue();
    queue.add(this.root);
    while (!queue.isEmpty()) {
      const node = queue.remove();
      yield node;
      node.descendents.forEach(child => queue.add(child));
    }
  }
Copy the code

BFS prints the corresponding values in the following order: 10, 5, 30, 4, 15, 40, 3.

Balanced trees vs. non-balanced trees

So far, we’ve discussed how to add, delete, and find elements. However, without talking about time complexity, let’s consider the worst-case scenario.

Suppose you add numbers in ascending order:

! [] (p0.ssl.qhimg.com/t014b63aee4… “”Inserting values in ascending order in a Binary Search Tree””)

There are no nodes on the left side of the tree! Finding elements in this non-balanced Tree takes no less time than using a linked list, all O(n). 😱

Looking up an element in an unbalanced tree is like looking for a word in a dictionary page by page. But if the tree were balanced, it would be akin to turning over a dictionary in half and continuing to look up either the left or right half, depending on the letters on the page.

You need to find a way to make the tree balanced!

If the tree is balanced and you no longer need to traverse all the elements to find them, the time is order log n. Let’s explore the meaning of a balanced tree.

! [] (p0.ssl.qhimg.com/t01348a324b… “”Balanced vs unbalanced Tree””)

If you are looking for a node with a value of 7 in an unbalanced tree, you have to go down from node #1 to node #7. However, in the balanced tree, after we visit #4, #6, the next node will reach #7. As the size of the tree increases, the performance gets worse and worse. If there are millions of nodes in the tree, finding an element that doesn’t exist takes millions of visits, compared to just 20 in a balanced tree! That’s a world of difference!

We will tackle this problem with self-balancing trees in the next article.

conclusion

We’ve talked a lot about tree basics, and here’s a summary:

  • A tree is a data structure whose nodes have zero or more child nodes.
  • Trees do not exist rings, graphs exist.
  • In a binary tree, each node has at most two child nodes.
  • A binary tree is called a binary search tree when the value of the left child is less than the value of the node and the value of the right child is greater than the value of the node.
  • You can access a tree in pre-order, follow-up, and mid-order.
  • The time complexity of finding in an unbalanced tree is zeroO(n). 🤦 🏻
  • The time complexity of finding in the equilibrium tree is zeroO(log n). 🎉