0x01 Basics

Trees VS subtree

We have been talking about one-to-one linear structures, but in reality, there are many one-to-many cases to deal with, so we need to study this one-to-many data structure — “tree”.

A Tree is a finite set of n (n≥0) nodes. N =0 is called an empty tree. In any non-empty tree: a. There is only one specific node called Root; B. When n > 1, the other nodes can be divided into M (m > 0) finite sets T1, T2…… Tm, where each set is itself a tree and is called a SubTree of the root.

It should be emphasized that:

  1. If n is greater than 0, the root is unique. You can’t have multiple roots

  2. When m is greater than 0, there is no limit to the number of subtrees, but they must be disjoint.

Node classification

A node of a tree contains a data element and branches that point to its children. The number of subtrees a node has is called its Degree.

1. Leaf node: node with degree 0, also called terminal node. 2. Branch node: node with degree 0, also called non-terminal node. Root node B. Internal node 3. Tree degree: the maximum degree of each node in the tree

The relationship between nodes

Children VS parents VS brothers VS ancestors VS descendants

1. The root of the subtree of the node, which is correspondingly called the parent of the child 2. Children of the same parent are called brothers. 3. The ancestor of a node is all nodes on the branch from the root to the node. Any node in a subtree rooted in a node is called a descendant of that node

The level of nodes VS the height of the tree (also called depth)

The Level of a node is defined from the root, which is the first layer and the child of the root is the second layer.

The maximum level of nodes in a tree is called the Depth or height of the tree

Storage structure of the 0x02 tree

Parent notation (sequential storage structure)

A contiguous set of storage Spaces is used to store the nodes of the tree, with an indicator (integer field) attached to each node to indicate the location of the parent node (subscript value).

“Data refers to the data domain, which stores the data information of nodes. And parent is the pointer field that stores the subscripts of the node’s parents in the array.”

In such a storage structure, we can easily find the parent node according to the parent pointer of the node, and the time complexity is O(1). When the parent is -1, it means that the root of the tree node is found. However, finding the children of a node requires scanning the entire array. This is also the advantage and disadvantage of this storage structure.

Child notation

Each node in the tree has multiple pointer fields, and each pointer points to the root of one of its subtrees.

Plan a

The number of pointer fields is equal to the degree of the tree

This method is obviously a waste of space when the degree of each node in the tree is very different, because there are many nodes, its pointer field is empty.

Scheme 2

In the second scheme, the number of pointer fields of each node is equal to the degree of the node. We select a special location to store the number of pointer fields of the node

This method overcomes the disadvantage of wasting space, and the utilization rate of space is very high, but because the linked list of each node is not the same structure, plus the value of the degree to maintain the node, it will bring time loss in the operation.

Plan 3

For each node in the tree, its children are represented by a singly linked list of leading nodes

The structure of the table node and the header node is shown below:

So if we want to find a child of a node, or a sibling of a node, we just need to find a singly linked list of children of that node. It’s also handy to iterate through the entire tree, just loop through an array of head nodes.

Child brother notation (binary tree notation)

Two pointer fields: respectively point to the first child node and the next sibling node of the node, as shown in the figure below:

Application of 0x03 tree

Virtual DOM tree

As we know, the so-called Virtual DOM algorithm mainly includes the following steps:

  1. Using JavaScript object structure to represent the DOM tree structure; Then use this tree to build a real DOM tree and insert it into the document github.com/vuejs/vue/b…

  2. When the state changes, a new object tree is rebuilt. Then compare the new tree with the old tree and record the difference between the two trees – diff

  3. Applying the differences recorded in Step 2 to the actual DOM tree built in Step 1, the view updates -patch