Shulou(Shulou.com)06/02 Report--

This article focuses on "analyzing Java data structures and algorithms". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "analyzing Java data structures and algorithms".

1. What is a binary tree?

Binary tree: a tree structure in which each node can only have two child nodes, commonly known as "big underpants", a special image.

Subtrees are usually called "left subtrees" (left subtree) and "right subtrees" (right subtree).

You can understand the following picture as soon as you see it.

two。 Binary tree traversal mode

2.1 there are three main types of traversal of binary trees:

1) first (root) order traversal (root left and right)

2) traversal of the middle (root) order (left root right)

3) traversal of post (root) order (left and right roots)

2.2 preorder traversal (around the root)

I'll start with the first preorder traversal, and the main traversal order is as follows:

1) access the root node first

2) then traverse the left subtree in order

3) then traverse the right subtree in order

Or as an example, first step through the following figure.

If you traverse in the first order (around the root), the result will be: ABDFECGHI

2.3 Central order traversal (left root right)

1) traverse the left subtree in the first middle order

2) then the root node

3) then traverse the right subtree in the middle order

Or give an example of traversing the same binary tree in the middle order.

Traverse in the middle order (left root, right), and the result is: DBEFAGHCI

2.4 Post-order traversal

1) traverse the left subtree in post-order

2) traverse the right subtree in post-order

3) then access the root node

Or an example of traversing the same binary tree in post-order.

Traversing (left and right roots) in the following order: DEFBHGICA

3. Types of binary trees

It basically includes:

Full binary tree

Complete binary tree

Binary search tree

Balanced AVL tree

Red and black trees also belong to AVL trees.

Let me start with the full binary tree.

3.1 full binary tree

1) full binary tree

A tree with a depth of k, a tree with 2 ^ k-1 nodes is a full binary tree.

2) the shape of full binary tree

3) the characteristics of full binary tree

All internal nodes have two child nodes, and the bottom layer is the leaf node.

If the depth of a tree is h, the maximum number of layers is k, and the depth is the same as the maximum number of layers, that is, k

The number of nodes in the k layer is: 2 ^ (kMel 1)

The total number of points is: 2 ^ k-1 (2 to the k power minus one)

The total number of nodes must be odd.

Tree height: h=log2 (nasty 1)

3.2. Complete binary tree

1) complete binary tree

If the depth of the binary tree is h, except for the h layer, the number of nodes in the other layers (1~h-1) reaches the maximum, and all the nodes in the h layer are continuously concentrated on the far left, which is the complete binary tree.

2) the morphology of complete binary tree

3) the characteristics of complete binary tree

A complete binary tree with a depth of k has at least 2 ^ (kmur1) nodes and at most 2 ^ k-1 nodes.

Tree height h=log2n + 1

A full binary tree must be a complete binary tree, and a complete binary tree is not necessarily a full binary tree.

3.3. Binary search / search / sort tree-BST

1) binary search tree

Binary search tree BST (Binary Search/ Sort Tree), also known as binary search tree, binary sort tree

Note: I'll call it binary search tree, but you should know that binary search tree, binary search tree and binary sort tree are actually the same kind of tree.

2) the characteristics of binary search tree

The value of all nodes on the left subtree is less than or equal to the value of its root node.

The value of all nodes on the right subtree is greater than or equal to the value of its root node.

3) advantages and disadvantages of binary search tree

Advantages: fast search speed, binary search tree is faster than ordinary tree search.

Disadvantages: balance problem

After many insertions and deletions, the binary search tree may lead to the structure of the following figure:

Search performance is already linear, so using a binary search tree should also consider maintaining the structure of the left image above as much as possible and avoiding the structure of the right image above, which is the so-called "balance" problem.

4) time complexity of binary search tree

Time complexity

Binary search tree is faster than ordinary tree search, and the time complexity of searching, inserting and deleting is O (logN).

Shortcoming

Binary search tree has an extreme situation, that is, it will become a linear linked list-like structure, and the time complexity will change O (N). In order to solve this situation, there is a binary balanced tree that I will talk about below.

Remarks: time complexity

O (1): the lowest time and space complexity, that is, the time consumption has nothing to do with the size of the input data, no matter how many times the input data is increased, the time / space consumption remains the same. Hash algorithm is a typical O (1) time complexity. No matter how large the data is, the target can be found after a calculation.

O (n): it means that the amount of data is increased several times and the time consuming is also increased several times. For example, the common traversal algorithm.

O (logn): when the data is increased by n times, the time is increased by logn times (here the log is based on 2, for example, when the data is increased by 256x, the time is only increased by 8 times, which is lower than the time complexity of linearity). Binary search is the algorithm of O (logn). Each search excludes half of the possibility, and the target can be found only 8 times out of 256 data.

3.4. Balanced binary tree (AVL tree)

1) balanced binary tree

Balanced binary tree the full name of balanced binary search tree, also known as AVL tree, is a self-balanced tree, upgraded from the upper binary search tree, the focus is to improve the balance problem.

2) the characteristics of balanced binary tree

The AVL tree also stipulates that the left node is smaller than the root node and the right node is larger than the root node.

It also stipulates that the height difference between the left subtree and the right subtree should not exceed 1, which ensures that it will not become a linear linked list.

3) how to solve the balance of AVL tree

It is mainly solved through left-handed and right-handed rotation to prevent the following linear structure from appearing in special cases.

Therefore, the balance problem above is solved by the left-handed and right-handed rotation of the image below.

However, there are corresponding shortcomings, in order to maintain their own balance, so when inserting and deleting nodes, the nodes need to be rotated frequently.

At this point, I believe you have a deeper understanding of "analyzing Java data structures and algorithms". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.