Is there a better option to query an array efficiently but add and delete things inefficiently, or add and delete things in a linked list efficiently but query things inefficiently? That’s where the binary tree comes in.

Binary tree

1 Related Concepts

  ​ Binary tree: A tree with only two nodes for each child node, each node has at most two subtrees (that is, there is no node whose degree is greater than 2 in the binary tree), and the subtrees of the binary tree are divided into left and right, and their order cannot be arbitrarily reversed. Binary search treeIt is also called ordered binary search tree, which meets the general properties of binary search tree. It means that an empty tree has the following properties:

  1. If the left subtree of any node is not empty, the value of the left subtree is less than that of the root node

  2. If the right subtree of any node is not empty, the value of the right subtree is greater than the value of the root node

  3. The left and right subtrees of any node are also binary search trees respectively

  4. There are no nodes with equal keys

The binary tree is divided into perfect binary tree, perfect binary tree and perfect binary tree

Perfect binary tree: also known as perfect binary treeFull binary tree, each node except the leaf node has two child nodes, and each layer is completely filledComplete binary tree: Every layer except the last is completely filled and all nodes remain aligned to the left

Perfect binary tree: Every node except the leaf node has two child nodes.

2 Traversal operation

There are three traversal rules in binary trees:

Middle-order traversal: The so-called middle-order traversal is to visit the left node first, then the root node, and finally the right node, that is, left-root-right traversal

Pre-order traversal: The so-called pre-order traversal is to visit the root node, then visit the left node, and finally visit the right node, namely root-left-right traversal (pre-order)

After the sequence traversalThe so-called back-order traversal is to visit the left node first, then the right node, and finally the root node. Left-right-root traversalFind minimum: Search all the way down the left subtree of the root node until the last non-empty node, which is the smallest node of the current tree

Find the maximum: Find the maximum along the right subtree of the root node until the last non-empty node is the largest node in the current tree

Find the precursor node: less than the maximum value of the current node

Find the successor node: Greater than the minimum value of the current node

3 Deleting a Node

Delete node in binary tree: essentially find precursor node or successor node to replace

  • The leaf node is deleted directly
  • If there is only one child node, it is replaced by the child node (essentially, it is to find the precursor node or the successor node, the left node is the precursor node, and the right node is the successor node).
  • If there are two child nodes, you need to find a replacement node (the replacement node is the precursor node or successor node).

4 Finding Limitations

A binary search tree is randomly composed of n nodes, so for some cases, the binary search tree will degenerate into a linear chain with n nodes. The following figure

AVL

The problem of BST is that the tree will tilt when it is inserted, and different insertion sequences will lead to different heights of numbers, which directly affects the search efficiency of the tree. The worst case is that all the nodes are on a diagonal line, so the height of the tree is N. Based on the problems of BST, Balanced BST is generated. Tree inserts and deletions are balanced by rotation to keep the height at LogN. Two typical balancing techniques are AVL trees (highly balanced trees with all the characteristics of binary search trees and the height difference between left and right subtrees is no more than 1) and red-black trees.

How is the AVL tree balanced? “Is achieved by left or right rotation. The details are as follows:

Although AVL can solve the problems existing in binary trees, the requirements of AVL trees are too strict, and the overhead of left and right rotation will be relatively large. At this time, red-black trees appear, and only the balance of black nodes is required. Next we introduce red black trees!