preface

0.1 Binary Search Tree (BST)

  • The rule that the value of a root node is greater than any node in its left subtree and less than any node in its right subtree applies to every node in a binary search tree.

0.2 Binary search tree search efficiency is based on binary search treeThe depth of the.

The binary tree node is inserted according to the value of the root node, judging the size of the current inserted value, small to the left, large to the right; If there are left and right nodes, repeat the search for left and right nodes. Insert until the left/right node of a node is empty.

For example, if you want to insert 11, 5 -> 7 -> 8 -> 9, 9 is greater than 9, and the right subtree of 9 is null, so insert the right subtree of 9.

0.3 Extreme Cases

In extreme cases, the tree becomes a linked list, in which case the search time becomes O(n).

Balanced search binary trees are designed to solve this situation

A, the AVL tree

    1. Inventors G. M. Adelson-Velsky and Evgenii Landis(AVL).
    1. Balance Factor: is the height of its left subtree minus the height of its right subtree (sometimes the reverse). Balance factor = {-1, 0, 1}.
    1. Balance by rotation operation (four types)

1.1 Basic rotation operation of AVL

When the height difference between the left and right subtrees of a node is outside the Balance Factor, AVL will rotate the subtrees to achieve Balance.

1.1.1 Right-right subtree – > left-turn

1.1.2 Left-left subtree – > right-handed

1.1.3 Left and right subtree — > Left and right rotation

I’m going to be left left subtree

Right hand rotation

1.1.4 Right-left subtree – > right-left rotation

It’s going to be a right-right subtree

Turn left again

1.2 AVL rotation operation

AVL if there is a subtree, the left/right rotation should also bring the subtree to another node

1.2.1 Left rotation of AVL band tree

1.2.2 Dextral rotation of AVL ribbon trees

1.2.3 summary

Red black tree

The AVL tree mentioned above can ensure that the left and right subtree heights of each node can be balanced. But then you have to check each insertion to see if the node is in balance, and sometimes you don’t need this very strict balancing mechanism, you just need to be relatively balanced. So we have data structures that are approximately balanced binary trees, which reduce the resource consumption of balancing binary trees.

2.1 Definition of red-black tree

Red-black Tree is an approximately balanced Binary Search Tree, which can ensure that the height difference between the left and right subtrees of any node is less than twice.

2.2 Properties of red-black trees

  • Every node is either red or black
  • The root is black
  • Every leaf node (NIL node, null node) is black.
  • You can’t have two red nodes next to each other
  • All paths from any node to each of its leaves contain the same number of black nodes.

The last two properties, in particular, guarantee that the height difference between the left and right subtrees of a red-black tree will not be more than double.

3. Comparison between AVL and red-black tree

AVL Red and black tree note
The query efficiency higher The lower AVL is perfectly balanced, whereas red-black trees are twice as tall at worst
Add or delete efficiency The lower higher AVL has to keep the left and right subtrees in absolute balance at all times. Red-black trees are less strict
The storage space higher The lower AVL stores an integer for each node to record the balance factor. Red-black trees only need one bit to identify red/black
Commonly used in The database Language library Database relatively more queries, add and delete less. With a language library, such as Java’s HashMap, the chances of adding, deleting and checking are roughly 50-50