In an interview, we usually talk about red black trees when we talk about HashMap, but if you go further, do you know what the features of red black trees are? If you haven’t sorted them out yet, you can read the following, which will be updated.
If you have no idea about binomial trees, first look at: Introduction to binomial trees
Tips: Leaf nodes, nodes with no children. Nil is equivalent to NULL in Java.
According to feature 4, there can be no consecutive red nodes. Feature 5 also says that the left and right paths from any node to each leaf node contain the same number of black nodes. It follows that the longest path is one black and one Red Cross, and the shortest path is all black. So the longest path is never more than twice the shortest path, so a red-black tree is approximately balanced, not strictly balanced. For kids who need to know about balanced binary trees, Comics: Getting to know binary trees.
It takes order log n to find, add, and delete a red-black tree, and we’ll talk about how it does that next time.
The article is short, I hope you can learn in a simple and relaxed atmosphere, xiaobian updated content is not much, but I hope that each article can be helpful to you, continue to work hard.
This article is formatted using MDNICE