Red and black trees give up the pursuit of complete balance and pursue approximate balance. When the time complexity is not much different from that of the balanced binary tree, it is easier to achieve balance by only three rotations at most each time. Balanced binary tree pursues absolute balance, with harsh conditions and troublesome implementation, and the number of rotations required after inserting new nodes is unpredictable.

Red and black trees

Red-black tree is a specific type of binary tree and a data structure used in computer science. Its typical use is to realize associative arrays. It was invented by RudolfBayer in 1972, and he called it "symmetric binary B-tree". Its modern name was obtained in a paper written by Leo. Guibas and RobertSedgewick of 1978. It is complex, but its operation has good worst-case running time and is efficient in practice. It can be found, inserted and deleted in O(logn) time, where n is the number of elements in the tree.

balanced binary tree

Self-self-balancing binary search tree, also called AVL tree (different from AVL algorithm), has the following properties: it is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and the left and right subtrees are balanced binary trees. Common implementation methods of balanced binary tree include red-black tree, AVL, scapegoat tree, Treap, extended tree and so on. The formula of the total number of nodes in the minimum binary balanced tree is as follows: f (n) = f (n-1)+f (n-2)+1,which is similar to recursive sequence, and you can refer to Fibonacci sequence, where1is the root node and F(n-65438+).