Last time on the book section, we went on to talk about binary trees, N-fork trees, and tree storage.
01Full binary tree
A binary tree is full binary if the number of nodes in each layer, except the last layer of nodes, is maximized, i.e., each node has two children, while all leaf nodes are in the last layer.
Thus it can be obtained that a full binary tree has the following properties:
(1) The maximum number of layers of the tree is k(k>=0, i.e., the number of layers starts from 0),then the total number of nodes in the i-th layer is 2i, the total number of leaf nodes of the tree is 2k , the total number of nodes in the tree is 2 ^(k+1) - 1;
(2) If the total number of nodes of a known number is n, the maximum number of layers of the tree is k = log2(n+1) - 1 (k>=0, i.e., the number of layers starts at 0);
(3) Number each node sequentially from top to bottom, left to right, starting at the top of the tree, with the root node being 1 as the start;
a.For node i, if it has a parent node, the parent node number is i/2 rounded down;
b. For node i, if there is a left node, the left node is numbered 2i, and if there is a right node, the right node is numbered 2i+1.
02Complete Bifurcation Tree
If a tree, leaf nodes can only appear in the last two levels, and the nodes in the last level are concentrated on the left side and are consecutive from left to right.
From this we get that complete binary trees have the following properties:
(1) Leaf nodes can only appear in the penultimate and penultimate layers;
(2) All leaf nodes in the penultimate layer are centralized in the leftmost continuous position of this layer;
(3) The penultimate layer if leaf nodes exist then all leaf nodes of the layer are concentrated in the rightmost consecutive position of this layer;
(4) If there exists a node among all nodes that has only one child, this node must be in the penultimate level and this child must be a left node;
(5) Full binary tree a special kind of complete binary tree;
(6) The full binary tree property (3) also applies to complete binary trees;
(7) If the complete binary tree is not a full binary tree, it is a full binary tree except for the last layer, and all the properties of a full binary tree apply;
(8) If the total number of nodes is n and i<=n/2, the ith node is a non-leaf node;
(9) If the total number of nodes is n, the number of leaf nodes is n/2 if n is even; the number of leaf nodes is (n+1)/2 if n is odd;
(10) If the number of layers of the tree is k(k>=0),the access to the total number of nodes of the tree number is [2k,2(k+1) - 1)]；
(11) If the total number of nodes of a known number is n, then the maximum number of layers of the tree is k = log2(n+1) (k>=0, i.e., the number of layers starts at 0) and k is rounded down;
03Binary Search Tree
A binary search tree is a special kind of binary tree, also called a binary lookup tree, binary sort tree, you can say that this is a kind of binary tree for query.
A binary search tree has the following properties:
(1) Each node value must be unique and cannot have duplicate values;
(2) Each node has at most two children;
(3) For any node, if it exists in the left subtree then all the nodes in the left subtree are less than the value of that node and if it exists in the right subtree then all the nodes in the right subtree are greater than the value of that node;
(3) The left and right subtrees are themselves each binary search trees;
04Balanced Bifurcation Tree
Balanced binary tree as the name suggests is to make the binary tree balanced in a certain state, a certain state specifically refers to any node in the tree left and right subtree height difference is less than or equal to the absolute value of 1, and its left and right subtrees are also balanced binary tree.
Balanced binary trees are used to optimize the average operation time of a binary search tree by controlling the depth of the tree.
AVL trees are a special case of balanced binary trees, strictly enforcing the definition of a balanced binary tree, and were the first self-balancing binary search trees invented.
Red-black tree is also a self-balancing binary search tree, but it does not strictly enforce the definition of balanced binary tree, balancing conditions are relatively loose, allowing the left and right subtree height difference in absolute value greater than 1.
We'll find a chance to talk about these two trees in detail separately later.
In addition there are Huffman trees, line trees, stretching trees, scapegoat trees and other binary trees are not introduced here, later we take out a separate explanation.
05N-tree
B-tree, B+-tree, 2-3-4 tree, R-tree, Trie tree and other multinomial trees we will find an opportunity later to take out a separate detail.
06Storage structure
1. Sequential storage
Sequential storage stores the entire tree using only a contiguous set of address spaces.
Of course not all trees are suitable for sequential storage, remember the property of full binary trees (3) stated above? If you take a full binary tree from top to bottom and left to right, the left and right child node numbers can be represented by the parent node number. If the parent node is numbered i, then its left child node is numbered 2i, and its right child node is numbered 2i+1. And the root node, being a known starting value of 1, means that all of its descendant nodes can be represented either directly or indirectly by the root node.
And the numbering not infrequently makes us think of array subscripts, which means we can fit the entire full binary tree into an array. Since full binary trees also satisfy property (3) for full binary trees, full binary trees can also fit into arrays. This is shown in the following figure.
What if it's a non-complete binary tree? Can be put into an array, the answer is certainly yes. We just need to imagine the non-complete binary tree as a full binary tree, the missing nodes virtual complement, and then its number, and finally loaded into the array, into the figure below:
But we will find that the number 4, 5, 7 bits are null, of course, the number 7 can be removed, even so, it is still a waste of array space, so the sequential storage is more suitable for complete binary tree storage, and other types of binary tree is not very suitable.
2. Chained storage
Sequential storage has its limitations, so most trees use chained storage. The core idea of chained storage is that each node is designed as two parts, one for the data domain to store element values, and the second for the pointer domain to store pointers to child nodes, the node has as many child nodes pointer domain has as many pointers.
Let's stick with the example of a binary tree with the following chained storage structure:
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner