Data structures and algorithms - tree structure

1. Tree structure

Tree structure is divided into binary tree and multi-fork tree, binary tree is each node is 2, multi-fork tree is each node is greater than 2;
Node, root node, parent node, child node, sibling node
A tree can have no nodes, called an empty tree
A tree can have only one node, which is the root node
Subtree, left subtree, right subtree
Defree: The number of subtrees
Degree of tree: the maximum degree of all nodes
Leaf node: node with degree 0
Non-leaf node: a node whose degree is not 0
Level: The root node is at layer 1, the children of the root node are at layer 2, and so on
Node depth: The total number of nodes on a unique path from the root node to the current node
Height: The total number of nodes along the path from the current node to the farthest leaf node
Tree depth: the maximum depth of all nodes
Tree height: The maximum of all node heights
The height of the tree equals the depth of the tree

Ordered tree, disordered tree, forest

1. The ordered tree
- There is a sequential relationship between the children of any node in the tree
2. The unordered trees
- There is no sequential relationship between the children of any node in the book
- Also known as the freedom tree
3. The forest
- A collection of m trees that do not intersect each other

Binary Tree

1. Characteristics of binary trees
- Each node has a maximum degree of 2 (at most 2 subtrees)
- The left subtree follows the right subtree in some order
- Even if a node has only one subtree, distinguish between the left and right subtrees
- A binary tree is an ordered tree

2. Properties of binary trees
- The i-th layer of a nonempty binary tree with at most 2^(i-1) nodes (I >=1)
- At most 2^(h-1) nodes in a binary tree of height H) (h>=1)
- For any non-empty binary tree, if the number of leaf nodes is N0 and the number of nodes with degree 2 is N2, then: n0=n2 + 1
- Assuming that the number of nodes with degree 1 is N1, then the total number of nodes in the binary tree is n = N0 + N1 + n2
- The binary tree variable T=n1 + 2 * n2 = n-1 = N0 + N1 + n2-1

Proper Binary Tree

1. True binary tree: degree of all nodes is either 0 or 2 (degree 1 cannot appear)

Binary Tree Full Binary Tree

1. Full binary tree: The degree of all nodes is either 0 or 2, and all leaf nodes are in the last layer
2. Among the binary trees of the same height, the full binary tree has the largest number of leaf nodes and the largest number of total nodes
3. A full binary tree must be a true binary tree, and a true binary tree may not be a full binary tree
4. A full binary tree must be a complete binary element, and a complete binary tree is not necessarily a full binary tree
5. Assume that the height of the full binary tree is h (h>=1), then
- Total number of nodes at layer I: 2^(h-1)
- Total number of leaf nodes: 2^(h-1)
- The total number of nodes is n = 2^0 + 2^1 + 2^2 +… + 2^(h-1) = 2^h -1

5. Complete binary trees

1. The concept
Complete binary tree: leaves appear only at the last 2 levels, and the leaves at the last 1 level are aligned to the left
A complete binary tree is a full binary tree from the root node to the penultimate level 2
A full binary tree is a complete binary tree, and a complete binary tree is not necessarily a full binary tree

2. Properties of complete binary trees
Nodes of degree 1 have only left subtrees
There are either zero or one nodes with degree 1
A complete binary tree with the same number of nodes has the smallest height
Assuming that the height of the complete binary tree is H (h>=1), then
- At least 2^(h-1) nodes (2^0 + 2^1 + 2^2 +… + 2^(h-2) + 1)
- A maximum of 2^h – 1 nodes (2^0 + 2^1 + 2^2 +… + 2^(h-1) + 2^(h-1)
- The total number of nodes is n = 2^(h-1) <= n <= 2^h
A complete binary tree with n nodes (n > 0), numbered from top to bottom and left to right starting from 1, for any ith node
- If I =1, it’s the root node
- If I >1, its parent is numbered floor (I /2)
- If 2 * I <= n, its left child is numbered 2 * I
- If 2 * I + 1 <= n, its right child node is numbered 2 * I + 1
- If 2 times I plus 1 >= n, it has no right child
A complete binary tree with n nodes (n > 0), numbered from top to bottom and left to right starting from 0, for any ith node
- If I =0, it’s the root node
- If I >0, its parent is numbered floor ((i-1)/2)
- If 2 * I + 1 <= n – 1, its left child is numbered 2 * I + 1
- If 2 times I + 2 <= n – 1, its right child node is numbered 2 times I + 2
- If 2 times I plus 1 is greater than n minus 1, it has no left child

3. Exercise – complete binary tree leaf node count

The summary is as follows:

So the final answer is:

For binary trees, the following statements are given abroad:

4. Binary tree search

1. Suppose you have a requirement to search for an integer among n dynamic integers. (Check whether it exists)
Let’s say we use a dynamic array to store elements, and we start at position 0, and the average time is O(n).

If maintaining an ordered dynamic array, using binary search, the worst time complexity is O(logn), but the average time complexity of adding and removing is O(n).

For this requirement, a binary search tree can be used, whose worst time complexity of adding, deleting and searching can be optimized as O(logn).

Binary Search Tree

1. Binary search tree concept
- Binary search tree is a kind of binary tree, is a very widely used binary tree, English abbreviation for BST, also known as binary search tree, binary sorting tree
- The value of any node is greater than the value of all nodes in its left subtree
- The value of any node is less than the value of all nodes in its right subtree
- Its left and right subtrees are also binary search trees
Binary search tree can greatly improve the efficiency of search
The data stored in binary search trees must be comparable,
- Like an int double or something
- If the type is user-defined, you need to specify the comparison mode
- Null is not allowed

2. Interface design of binary search tree

For today’s binary search tree, its elements have no concept of index
3.add

4. Binary tree traversal
According to the node access order, there are four common traversal methods of binary tree
- Preorder Traversal root left and right
- Inorder Traversal left root right
- Postorder Traversal of the left and right roots
- Level Order Traversal

The following traversal loops are described in this binary tree

5. Exercise – Calculate the height of binary tree
6. Exercise – Judge complete binary trees

Sequence traversal Idea 1:

Idea 2:

7. Exercise – Flipping binary trees

Flip: Swaps the left and right subtrees of all nodes

Preorder traversal method

Order traversal method

1. The binary tree is reconstructed from the traversal results

9. Predecessor nodes

10 Succeeded Nodes

11. Delete the node – leaf node

12. Delete the node whose degree is 1

13. Delete the node whose degree is 2

14. Time complexity of binary search trees
The time complexity of insert, delete and search of binary search tree is as follows. If it is converted to a linked list, it is the same as the time complexity of linked list. When n is larger, the time complexity of binary search tree is smaller, and the time complexity of linked list is larger

Balanced binary search tree

1. Balance: When the number of nodes is fixed, the closer the height of the left and right subtrees are, the more balanced the binary tree will be (the lower the height is).

2. Ideal balance
Complete and full binary trees are close to ideal equilibrium

3. Improved binary search tree?
You can’t control the size of the added and removed elements, but you can delete them. After adding, try to adjust the binary tree to a balanced binary tree

4. Balanced binary search tree

7. AVL tree

Balance Factor: the height difference between the left and right subtrees of a node
1. The concept of AVL tree
Balanced binary search tree
The balance factor of each node of AVL tree can only be: 1/0/-1 (absolute value <= 1, if more than 1 is called “unbalanced”)
The height difference between the left and right subtrees of each node is no more than 1
Search, add, delete time order logn

2. The inheritance relationship among binary tree, binary search tree, AVL tree and red-black tree is as follows:

3. Imbalance caused by adding

3.1LL- Right rotation (single rotation) – one of the ways to solve the imbalance

3.2RR- Left rotation (single spin) – Solution to imbalance 2

3.3LR-RR left rotation, LL right rotation (double rotation) – solution of imbalance 3

3.4RL-LL right rotation, RR left rotation (double rotation) – solution to imbalance four ways

3.5 Unified Rotation Operation

4. Delete the resulting imbalance

4.1 LL- Right rotation (single rotation)

4.2 RR- Left rotation (single rotation)

4.3 LR-RR Left Rotation, LL Right Rotation (double rotation)

4.4 RL-LL right rotation, RR left rotation (double rotation)

If the green node does not exist, the ancestor nodes at higher levels may also be out of balance and need to be re-balanced, which in turn may cause the ancestor nodes at higher levels to be out of balance. In extreme cases, all ancestor nodes need to be restored to balance, which is a total of (logn) adjustments.

5 AVL tree summary

For ordinary binary tree search, AVL tree is the most efficient

B tree B tree

1. B tree concept
- Is a balanced multi-path search tree, used for file system, database implementation
- A node can store more than 2 elements and can have more than 2 child nodes
- It has some properties of binary search trees
- Balanced, all subtrees of each node are the same height
- shorter

2. Properties of M-order B-trees (M >=2)

3.B tree vs. binary search tree

The binary search tree can be transformed into a B-tree by merging some parent and child nodes. The above result is as follows:

4. B tree search

5. Add

Nodes store elements in a binary tree of order m,

6. Add a solution to the benefits

7. Delete – non-leaf node/leaf node

8. Delete – underflow solution

Red Black Tree

1. Red-black tree concept
- A self-balanced Binary search tree, also called a Symmetric Binary B-tree, does not rely on the balance factor to maintain balance. The balance is maintained in the following five cases
2. Red-black tree properties
- The node is Red or Black
- The root node must be Black
- The leaf nodes (outer nodes, empty nodes) are Black
- The children of the Red node are blocks
- All paths from the root node to the leaf node and that cannot have 2 consecutive Red nodes
- All paths from any node to the leaf contain the same number of Black nodes