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

This article mainly explains "how to thoroughly understand the red-black tree". Interested friends might as well take a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "how to thoroughly understand the red-black tree"!

Binary tree

A tree that meets the following two conditions is a binary tree:

The tree itself is an ordered tree (if the subtrees of each node in the tree are regarded as ordered from left to right (that is, they are not interchangeable), the tree is called an ordered tree (Ordered Tree).

The degree of each node contained in the tree cannot exceed 2, that is, it can only be 0, 1, or 2.

To put it simply, a binary tree (Binary tree) is a tree structure in which each node has at most two branches (that is, there are no nodes with a branching degree greater than 2). Branches are usually called "left subtrees" or "right subtrees".

Binary search tree

Before you understand the red-black tree, you can't help but look at what the binary search tree is.

Wikipedia definition: binary search tree (English: Binary Search Tree), also known as binary search tree, ordered binary tree (ordered binary tree) or ordered binary tree (sorted binary tree), refers to an empty tree or a binary tree with the following properties.

If the left subtree of any node is not empty, the value of all nodes on the left subtree is less than the value of its root node; if the right subtree of any node is not empty, the value of all nodes on the right subtree is greater than or equal to the value of its root node; the left and right subtrees of any node are also binary search trees, respectively.

Illustration understanding:

The image above shows finding a node with a value of 29, with the following steps:

View the root node 41.

Because 41 > 29, check the left child 20 of 41.

Because 20

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.