1. Binary search tree (BST)

  • Binary Search Tree: The left Tree of any node is smaller than it and the right Tree is larger than it.

Benefits:

  • When inserting or reading, only one node in each layer is compared
  • The complexity of a query depends entirely on the depth of the tree
  • Both read and write are order logn.

When you think of order logn, a lot of people probably think of binary search

Contrast with binary lookup:

  • Binary search: In an ordered array, search for the middle value first. If the current value is larger than the middle value, search for the right part of it. If the current value is smaller than the left value, search for the left part.
  • The idea is similar to BST, but ordered arrays are logn at worst, and BST is reduced to n at worst.
  • So, why in many cases do we use BST instead of binary lookup of ordered arrays?
  • Because binary search is a bit of a chore to insert, we insert a number, and when we find its position, we move all the numbers behind it one bit back. The complexity of insertion is O(n);

The bad:

  • When the data is continuously increasing or decreasing, the whole tree becomes a line, and the depth of the tree becomes O(n).
  • Query and insert complexity becomes O(n)

2. Self-balanced binary tree (AVL tree)

  • Adelson-velsky and Landis Tree: Firstly, it is a BST itself, and the depth difference between the left and right subtrees of any node is less than or equal to 1.
  • The read and write complexity of self-balanced binary trees is O(logn), and in the worst case, O(logn).
  • His better optimization of BST.

3. A red-black tree

  • Red – black tree:
  1. Each node has to be red or black
  2. The root node must be black
  3. Leaf nodes must be black (including null nodes)
  4. Children of red nodes must be black nodes
  5. The newly inserted node must be red
  6. All simple paths from any node to the leaf must have the same number of black nodes
  • It can be seen that most of the nodes are black, and the survival conditions of the red nodes are very bad
  • Leaf nodes must be black nodes to ensure that the number of black nodes reaches more than half
  • If the null node is also a leaf node, our binary tree is guaranteed to be a full binary tree

What is the purpose of defining so many conditions?

  • Some people say that a red-black tree is also a self-balanced binary tree, but the “balance” criteria for a red-black tree is different from AVL.
  • The AVL tree is balanced to ensure that the depth difference between the left and right subtrees is 1. This is a harsh balancing condition.
  • The equilibrium condition of red-black tree is the same number of black nodes on two paths.

If the number of black nodes on both paths is the same, what is the upper bound and the lower bound?

  • Upper bound: If both paths are black nodes, the same number of black nodes on the two paths means the same number of nodes on the two paths. The depth difference is 0;

  • Lower bound: The worst case is that there are no red nodes on one path, and a large number of red nodes on the other path. The children of the red node must be black nodes. The maximum number of red nodes is red and black, and the difference of nodes is twice.

  • The lower bound of the AVL tree is the left and right depth difference 1,

  • The difference between the left and right depth of a red-black tree is less than 1 times that of a red-black tree.

Why should red-black trees achieve such a balance?

  • The balance condition of AVL tree is the left and right depth difference of 1. This condition is quite harsh, which will lead to the failure to meet the balance condition in many cases. If the condition is not met, some changes need to be made, which will take some time. But red-black trees have a looser equilibrium in mind, so that when we insert data, the tree changes less, so red-black trees write better.

In Java8, the implementation of HashMap is an array plus a list. When the list length reaches 8 and the array length is greater than 64, the list will be converted to a red-black tree. Why choose red-black tree instead of BST or AVL tree? HashMap JDk1.7/1.8

If the depth difference is twice as bad, can you keep order logn?

  • Search and query book time complexity is completely dependent on the depth of the tree, completely covering the red node is O(logn), the worst case is red and black O(2logn), or O(logn).

Red-black tree insertion process:



Video: https://www.bilibili.com/video/BV1Pp4y1D7u1