One 、 Binary tree

Binary tree （Binary tree） Each node most There are only two branches （ That is, there is no branching degree greater than 2 The node of ） The tree structure of the .
Binary trees are also divided into full binary trees , Perfect binary tree , Balanced binary trees .

1、 Full binary tree

A binary tree , If the number of nodes in each layer reaches the maximum , Then the binary tree is Full binary tree . Suppose the number of levels of the binary tree is k

• Sum of nodes of full binary tree ：2^k - 1
• The maximum number of nodes in each layer ：2^k-1
  

2、 Perfect binary tree

In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer . Suppose the number of levels of the binary tree is k

• The number of nodes at the bottom of a complete binary tree ranges from ：1 ~ 2^k-1-1
  

3、 Binary search tree

Binary search tree There are values , And it's a Orderly Trees .

1. If its left subtree is not empty , Then the value of all nodes in the left subtree is less than the value of its root node ;
2. If its right subtree is not empty , Then the value of all nodes in the right subtree is greater than the value of its root node ;
3. Its left 、 The right subtree is also a binary sort tree
   

4、 Balanced binary trees

Balanced binary search tree （AVL Trees ）： Balanced binary tree for short . The properties are as follows ：

1. It can be an empty tree
2. If it's not an empty tree , The absolute value of the height difference between its left and right subtrees shall not exceed 1, And both the left and right subtrees are a balanced binary tree .
   

5、 reference

1. Basic theory of binary tree , The species of binary trees 、 Storage 、 Traverse 、 Program definition .
2. Trees , Explained the classification of binary tree 、 Storage 、 Traverse .
3. What is a balanced binary tree （AVL）, Explains why there is a binary balanced tree ,AVL The imbalance and adjustment of tree insertion ,AVL Four ways to insert nodes into a tree ,AVL Four ways to delete nodes in a tree .

Two 、 Pile up

The value of each node in the heap is greater than or equal to （ Or less than or equal to ） The values of all nodes in the subtree . Or say , The value of any node is greater than or equal to （ Or less than or equal to ） Values of all child nodes .

1、 reference

1. Pile up , Explained the definition of heap 、 purpose 、 classification 、 Storage 、 operation 、 Sort .

3、 ... and 、 Be careful

1、 Balanced binary search trees （AVL Trees ） Is it right? Binary search tree and Balanced binary trees The combination of ？
Yes , It is the combination of binary search tree and balanced binary tree .

2、 Balanced binary trees And Perfect binary tree The difference lies in the location of the underlying nodes ？
Yes , The bottom layer of a complete binary tree must be continuous from left to right , And the sub bottom is full .
And the balanced binary tree is orderly , There are values , A complete binary tree can have no values .

3、 Pile up yes Perfect binary tree Combination with sorting , instead of Balanced binary search trees ？
Heap approximation can be regarded as a complete binary tree , At the same time, ensure the order of the parent-child nodes （ Orderly ）.
The sort of heap is that the parent node is greater than the child node , The parent node of the search tree is larger than the left child , Smaller than the right child , So the heap is not a balanced binary search tree .