Summary of tree, binary tree and search algorithm

preface

So far, we have learned the basic concepts and common algorithms of tree and binary tree, and found that the tree has great use in searching. Here we make some summary and records.

1, Connecting knowledge points in series with mind map

2, Concept elaboration

1. Trees

a. Basic concepts of tree

Basic knowledge of tree:
Explain the relevant nodes of the tree

1. Root: the top node; Leaves: nodes without child nodes; A tree with only one node, which is both root and leaf.

2. If the number of nodes of the tree is n, there are n-1 child nodes after removing the root node, that is, n-1 edges;

3. If the degree of this tree is k, it has kn pointers, of which n-1 are used and the remaining (k-1)n+1 null pointers;

4. Since a tree with n nodes has at most n-1 nodes, i.e. n-1 edges, it is necessary to cut off at least m-n+1 edges in order to turn the graph with n nodes and m edges into a tree

5. If the degree of the tree is k and ni represents the number of nodes with degree i, then n0+n1 +... + nk = 1+n1+2n2+3n3 +... knk

b. Logical representation of tree

There are venturi diagram representation, concave representation and bracket representation
And the tree representation method will be introduced
It is characterized by:
① Each node has zero or more child nodes;
② A node without a parent node is called a root node;
③ Each non root node has only one parent node;
④ In addition to the root node, each child node can be divided into multiple disjoint subtrees;

c. Basic operation of tree

Establish the definition of the tree

typedef char ElemType;
typedef struct BiTNode { 
    ElemType   data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

(the complete tree operation implementation refers to the implementation of various functions in the binary tree)

2. Binary tree

Definition and logical representation of binary tree

Binary tree
Each node has a tree structure divided into left and right. There are at most two child nodes and at least no child nodes under each node
Complete binary tree:
All child nodes are on the left
Full binary tree:
Terminal nodes (leaf nodes) are at the bottom, and there are two child nodes under each parent node

c. Basic operation and implementation of binary tree

Insertion of binary tree nodes

void InsertBST(BSTree* &t,int key)
{
        BSTree *p,*parent,*head;
        p = new BSTree;
        p->data = key;
        p->lchild = p->rchild = NULL;
        head = t;

        while(head)
        {
                parent = head;
                if(key < head->data)
                 head = head->lchild;
                else
                 head = head->rchild;
        }

        if(key < parent->data)
         parent->lchild = p;
        else
         parent->rchild = p;

}

Create a binary tree

void createBST(BSTree *t)
{
	cout<<"Number of nodes in the input tree: ";
	int n;
	int data[Maxsize];
	cin>>n;
	for(int a=0;a<n;a++)
	{
		cin>>data[a];
	}
        int i;
        t->data = data[0];
        t->lchild = t->rchild = NULL;
        for(i=1;i<n;i++)
        InsertBST(t,data[i]);
}

For the output of binary tree, see the traversal implementation of binary tree below
For the implementation of binary tree search and deletion, see the search content below

d. Traversal of binary tree (emphasis)

Preorder traversal

void PreOrder(BiTree t)
{
	if(t)
	{
		cout<<t->data;
		PreOrder(t->lchild);
		PreOrder(t->rchild);
	}
}

Middle order traversal
(it is characterized by realizing the output order of nodes, such as from small to large)

void InOrder(BiTree t)
{
	if(t)
	{
		InOrder(t->lchild);
		cout<<t->data;
		InOrder(t->rchild);
	}
}

Postorder traversal

void PostOrder(BiTree t)
{
	if(t)
	{
		PostOrder(t->lchild);
		PostOrder(t->rchild);
		cout<<t->data;
	}
}

3. Binary tree - Advanced

a. Clue binary tree

As shown in the figure:
The dotted line is the clue pointer, and the solid line points to the real child. Because the ltag and rtag flag bits of A are 0, A has left and right child nodes, and left and right point to its real children; Node B is similar to node A; Both flag bits of node D are 1, so its left and right should point to its predecessor and successor, but D is the first in the middle order sequence, there is no precursor, so left is NULL, and right points to B; ltag of node E = 0, so it points to the child node; rtag=1, so it points to the successor
and so on

/* Definition of binary clue storage structure of binary tree*/
typedef enum{Link, Thread}PointerTag;    //Link = 0 indicates the pointer pointing to the left and right children; Thread = 1 indicates a clue to a precursor or successor
 
typedef struct BitNode
{
       char data;                                      //Node data
       struct BitNode *lchild, *rchild;                //Left and right child pointers
       PointerTag  Ltag;                               //Left and right signs
       PointerTag  rtal;
}BitNode, *BiTree;

b. Huffman tree

Using Huffman coding for communication can greatly improve the channel utilization, shorten the information transmission time and reduce the transmission cost. When constructing Huffman tree, firstly, n leaf nodes formed by n characters are stored in the first n components of HuffNode array. Then, according to the basic idea of Huffman method, two smaller subtrees are continuously combined into a larger subtree, and the root nodes of the new subtree are placed behind the first n components of HuffNode array in order.

In terms of information transmission, framan tree can be widely used for framan tree coding

Huffman tree can also be understood as the minimum binary tree and the optimal binary tree.

3, Search (difficulty)

a. Lookup of linear table

It mainly includes sequential search and half search. The content is relatively simple. See the relevant contents in 9.2 of the fifth edition of data structure tutorial for details. The following focuses on the contents related to tree table lookup.

b. Tree table lookup

Concise concept description
The tree structure of binary tree makes it very suitable to play the role of index: binary search tree, which is mainly used for search operation; Binary search tree adds the following conditions on the basis of binary tree:

(1) If the left subtree is not empty, the values of all nodes on the left subtree are less than the values of the root node
(2) If the right subtree is not empty, the values of all nodes on the right subtree are greater than those of the root node
(3) , left and right subtrees are also binary search trees

[specific steps are shown as follows]:
The following figure is a standard binary search tree:

For example, to find a node with a value of 4, the steps are as follows:

1. Visit root node 6 and find 4 < 6;

2. Visit the left child node 3 of node 6 and find that 4 > 3;

3. Visit the right child node 4 of node 3 and find that 4 = 4, which is the node to be found

For a binary search tree with relatively balanced node distribution, if the total number of nodes is n, the time complexity of searching nodes is O(logn), which is the same as the depth of the tree.

[specifically, recursive algorithm can be used to find node elements]

BSTree *SearchBST(BSTree *t,int key)
{
        if(!t || t->data == key)
        return t;
        else if(key >t->data)
                return (SearchBST(t->rchild,key));
        else
                return (SearchBST(t->lchild,key));
}

Binary sort tree

[supplementary B-tree]

definition:
B-tree is a balanced multitree, which is mainly used for query. m-order B-tree (there are at most m child nodes under each node) meets the following conditions:

The root node has at least two children, and the number of keywords contained in each root node j Meet:( m/2)-1 < j < m-1；
The degree of all nodes except the root node (excluding leaf nodes) is exactly the total number of keywords plus 1 and the number of ancient internal subtrees k Meet:( m/2)<= k <= m；
All leaf nodes are located on the same layer.

Properties of B-tree

The path length from all leaf nodes to root nodes is the same, that is, it has the same height;
Each non leaf and non root node (i.e. internal node) has at least m-1 A child node; Root at least 2 children; Each node has a maximum of 2 nodes m A child node.
The keys in each node are incremented, and the children of each node are smaller than key More than 1

How to use B-tree
When searching for data, take out the keywords in all non root nodes, and then find out whether there are root nodes that meet the range, and then compare them one by one.

B + tree
Definition: B + tree is an improved structure of B tree. Under the requirements of B tree, it also meets the following requirements:

have K The middle node of the subtree contains K Elements( B Tree species are K-1 Each element does not save data, but is only used for indexing. All data exists in the leaf node;
All leaf nodes contain the information of all elements and pointers to records containing these elements, and the leaf nodes themselves are linked from small to large according to the size of keywords;
All intermediate node elements exist in child nodes at the same time, and are the largest (or smallest) element in child nodes
 contrast B Advantages of tree: fast search, simple storage structure and stable query;

Difficult problems and Solutions

(PTA exercise lecture)

The idea of judging whether a tree is a complete binary tree:
1. If the tree is empty, an error is returned directly.
2. If the tree is not empty: traverse the binary tree.
3. If the left and right children of a node are not empty, put their left and right children in the queue;
4. If a node is encountered, the left child is empty and the right child is not empty, the tree must not be a complete binary tree;
5. If a node is encountered, the left child is not empty and the right child is empty; Or left and right children are empty; Then all nodes in the queue after the node are leaf nodes; The tree is a complete binary tree, otherwise it is not a complete binary tree;

In short, all child nodes are required to go left to right. When a node with a degree less than 2 is encountered, the following nodes must be all leaves.
(the specific code implementation is complex, just remember the idea)