Tree Basics

【 notes 】 Refer to the textbook 「 Introduction to algorithms 」.

1. Free tree

1.1 Definition

Free tree Is a connected 、 Acyclic undirected graph , abbreviation Trees .

【 notes 】 A possibly disconnected 、 An acyclic undirected graph is called The forest .

1.2 Concept

• The degree of node ： The degree of a node in a free tree is the same as that in an undirected graph , That is, the number of adjacent nodes .

1.3 nature

• Make G=(V,E) It's an undirected graph , Then the following description is equivalent ：

1. G Is a free tree .
2. G Any two nodes are connected by a unique simple path .
3. G It's connected , But the graph obtained by removing any edge from the graph is not connected .
4. G It's connected , And ∣E∣=∣V∣−1 .
5. G It's acyclic , And ∣E∣=∣V∣−1.
6. G It's acyclic , But if to EEE Add any edge to the , Will cause the graph to contain a ring .

2. Rooting tree & Yes / Disordered trees

2.1 Definition

• Rooting tree Is a free tree , There is a root node in the node （ It's called root ）.
• Ordered trees It's a tree with roots , The children of each node are orderly （ That is, the left-right positional relationship between the children of a node in the tree is influential ）.

2.2 Concept

• The ancestors & Progeny ： Consider the r For rooted trees T One of the nodes in x

1. from r To x Any node on the only simple path y be called x One of the The ancestors . If y yes x The ancestors of the , be x yes y Of Progeny .
2. Each node is both its own ancestor and its own offspring .
3. If y yes x Our ancestors and x \ne y, be y yes x One of the True ancestors , And x yes One of the True offspring .

• Parents & children & brother ： Consider from the tree T The root of the r To the node x The last edge on the simple path of is (y,x)

1. y yes x Of Parents ,x yes y Of children .
2. If two nodes have the same parents , Then they are brother .
3. The root node is the only node in the tree that has no parents .

• leaf & Internal nodes

1. A node without children is called leaf （ or External nodes ）.
2. A non leaf node is called Internal nodes .

• The degree of node ： The degree of a node in a rooted tree refers to the number of children of the node , Parents of nodes are not included （ Different from the definition of free tree ）.
• The degree of a tree ： The degree of the largest node in a tree is called the degree of the tree .
• The depth of the node ： From the root r To the node x The length of a simple path of is the node x stay T The depth of the . The depth of the root is 0 .
• The height of the node ： The number of edges on the longest simple path from this node to the leaf node in the subtree with this node as the root node . The height of all leaf nodes is 0 .
• Depth of tree / Height ： Equal to the maximum node depth in the tree / Maximum node height . Depth of tree = The height of the tree .
• Internal path length ： Sum of depths of all internal nodes .
• External path length ： Sum of the depths of all leaf nodes .

3. Binary tree & Location tree

【 notes 】 The definition of binary tree can be extended to k Fork tree .

3.1 Definition

• Binary tree T Is a structure defined on a finite set of nodes , It may or may not contain any nodes , Or contain three disjoint node sets ：

1. A root node .
2. One is called The left subtree Two fork tree .
3. One is called Right subtree Two fork tree .

• Location tree A tree in which children of nodes are marked as different positive integers . If no child is marked as an integer i , Then the... Of the node i Children are missing .

3.2 Concept

• Empty tree & Zero tree ： A binary tree that contains no nodes , Sometimes symbols are used NIL Express .
• Left the child & The right child ： If left / The right subtree is not empty , Then its root is called the left of the root of the whole tree / The right child .
• Full binary tree ： Each node is a leaf node or has a degree of 2 The binary tree of is a full binary tree （ That is, a full binary tree has no degree 1 The node of ）.
• Perfect binary tree ： In a binary tree , If all the layers except the last one are full , And the last floor is either full , Or there are several consecutive nodes missing on the right , Then this binary tree is a complete binary tree .
• Perfect binary tree ： All leaf nodes have the same depth , And all internal node degrees are 2 Two fork tree .
• Balanced binary trees （AVL Trees ）： The height difference between two subtrees of any node is not greater than 1 Two fork tree .

3.3 nature

• A binary tree is a position tree , For each node , All tags are greater than 2 Of the children are missing .
• In any non empty binary tree 2 The number of degree nodes is less than that of leaf nodes 1 .

inference

1. The number of leaf nodes is l The number of node elements of the full binary tree of is n=2l−1 .
2. The number of node elements is n The number of leaf nodes of a perfect binary tree l = {(n+1) \over 2}​, The number of non leaf nodes is n - l = l - 1 = {(n+1) \over 2} - 1.

• One has n The height of a non empty binary tree with nodes is at least \lfloor \lg n \rfloor.
• One height is h Full binary tree , The number of node elements n Satisfy 2h + 1 \leq n \leq 2^{h+1} - 1 .