Red and black tree is a very interesting balanced tree. Its statistically better than balance binary tree (some books according to the author's name, ADELSON-VELSKII and LANDIS, it is called AVL-tree), so the red black tree has an application in many places. In C STL, many parts (currently including SET, MULTISET, MAP, MULTIMAP) apply a variant of the red-hared tree (the red and black trees in SGI STL have some changes, and these modifications provide better performance, as well as SET Support for operations). The definition of the red and black tree is as follows:
The binary search tree that meets the following conditions is a red black tree
Each node is either "red" or "black" (later will explain) All leaf nodes are empty, and if a node is "red", then its The two sub-nodes are "black". Nonpart to each simple path of its descendants, each simple path of the same number of "black" nodes is always "black", the reason for the red-hanging tree is that each of its nodes is "Coloring" is red or black. These node colors are used to detect the balance of the tree. However, it should be noted that the red-haircut is not a balanced binary tree. On the contrary, the red black tree relaxes some of the requirements of balance the binary tree. Due to certain "imbalances", the performance of the red-haircut is improved. The number of black nodes from the root node to the leaf node is called the "Black-height" of the tree. The nature of the red black tree is guaranteed to be twice the path length from the root node to the leaf node. Let's explain this conclusion. Considering a black height of 3 red black: from root node to the shortest path length is obviously 2 (black - black - black), the longest path is 4 (black - red - black - red - black ). Due to nature 4, it is impossible to add more black nodes in the longest path. In addition, according to the nature 3, the son node of the red node must be black, so two consecutive paths are not allowed in the same simple path. Red node. In summary, the longest path we can build will be a red black path. From this, we can conclude that the shortest length of the simple path from the root to the leaf node is N-1 for a red-black tree having a given black height N, the shortest length of the simple path of the leaf junction. The maximum length is 2 (N-1). Insert and delete operations, the node may be rotated to keep the balance of the tree. The average and worst search time of the red-hahead is O (log2 n). Cormen [2001] gives the proof of this conclusion. In practical applications, the statistical performance of the red-black tree is better than balanced binary tree, but extreme performance is slightly poor. The process of insertion of nodes in the red-black tree is:
Searching in the tree will replace an empty joint point that already exists, and will have two new nodes that have two empty nodes as a sub-node to be red, the color of its father-node according to the red black tree Definition determination; if necessary, adjustment of the tree adjustment to the null node and NULL pointers are different. In a simple implementation, the common nodes that are "monitored" can be used as the black-mentioned vacancies as the previously mentioned hollow joint. Give a red node to add two empty sub-nodes to match the properties 4, and must ensure that the two sub-nodes of the red node are black (depending on nature 3). Nevertheless, when the new node is red, the red subjunction that is inserted into the red will be defined. There are two situations at this time. The brother node of the red father's node is also red, for example, the following case (X is the node that I want to insert, this example will refer to this article) Simply reload the collision to the superior node will resolve conflicts. When the knot B is reatched, the color of the greater in the greater range of the tree should be re-examined to ensure the entire tree meets the defined requirements. At the end, the root node should be black. If it is originally red, the black height of the red black tree tree will increase 1. The brothers of the red father's node are complicated in this case, as shown below: Rear pair of colors will turn node a into black, so the balance of the tree will be destroyed because the black height of the left subtree It will increase, while the black height of the right subtree is not changed accordingly. If we put the node B on red, the height of the left and right subtroes will be reduced, and the tree is still unbalanced. At this time, the coloring of the node C will result in worse cases, and the height of the left subtree increases, and the black height of the right man tree is reduced. In order to solve the problem, you need to rotate and reload the tree nodes. At this time, the algorithm will end properly because the root node (a) of the subtree is colored as black, and the new red-red conflict will not be introduced. When the insertion process is inserted into the node, it may need to reload, or rotate to keep the nature of the red black tree. If the rotation is complete, the algorithm is over. For re-colors, we will leave a red node on the root of the subtree, so we need to continue to trim to keep the tree to keep the nature of the red black tree. Under the worst case, we will have to process all the paths of the root. The inserted time complexity is O (log2 n). The time complexity of the delete node is similar to this. The node deletion of the red-haircut is more complicated than insertion. We can divide the actual deletion operation into three cases (no color), which is deleted with purple markers, blue indicates the nodes of any color, may be red, or black: situation A: Deleted nodes No sub-node (two sub-nodes are empty nodes) The idle nodes that are originally X-based are "inherited". If the deleted node is a black node, it may cause a black height of the tree. Case B: There is a sub-node B node replaces the position of the original X node. If the deleted node is a black node, it may cause a black height of the tree to change; if B is a red node, it is also necessary to reload. Case C: There are two sub-nodes that are more complicated. It is necessary to exchange the maximum node of the key value in the left subtree. This usually results in researchers, changes in the black height of the tree, and the rotation of the followed. It should be noted that only delete nodes are not enough, because it is likely to reload the tree later. If you delete a red node, then there is no relationship, because this will not affect the black height of the tree; if deleted is a black node, things are not that simple. The node that is affected (mobile or exchange) is needed to be black. If it is already black, you need to mark "Double Black" (double black, or double-black is a concept mentioned in many English materials. Simply put, marked "double black" means "wipes" processing on the surrounding red node).
The "double black" node is clearly not in line with the red black tree, so this must be eliminated. There is a "double black" situation can be divided into 4: 1, the brothers of the double black nodes are red 2, the brothers of the double black nodes are black, and its brothers have two black s nuts. 3, the brothers of the double black nodes are black, and its brothers left, the right boutique is red and black 4, the brothers of the double black nodes are black, and its brothers' right son The point is that it is clear that the above four cases include possible all conditions. The basic idea of handling double black nodes is to conduct "color compensation". In other words, the adjacent red node is made black, and the double black node is also "reduced" as black. Summarizing the red black tree into the concept of "color". The introduction of "color" is to make the balance condition of the red-haircuts simplify. As the famous cryptography expert Bruce Schneier said, "Being Partly Balanced Can Be Good Enough", the red-black tree does not pursue "full balance" - it only requires partially to meet the balance requirements, reducing the requirements for rotation Thereby improving performance. The red black tree can search, insert, and delete operations with time complexity of O (Log2 N). In addition, due to its design, any imbalance will be resolved within three rotations. Of course, there are some better, but achieve more complex data structures can be balanced within one step, but the red black tree can give us a relatively "cheap" solution. The algorithm time complexity of the red-hahead is the same, but the statistical performance is higher than the AVL tree. Of course, the red and black tree does not adapt to all fields of all application trees. If the data is basically static, let them have better performance when they can insert and do not affect the balance. If the data is completely static, for example, make a hash table, performance may be better. In the actual system, for example, a firewall system that requires a dynamic rule is required, and the red black tree is used instead of the hash table, it has been proved to have better scalability. Reference AVL Search Tree - Introduction and ANSI C Reference Implence, http://www.purists.org/georg/avltree/ AVL Tree Applet [Source Code], http://www.seanet.com/USERS/Arsen/avltree .html Introduction to Algorithms (Mit Electrical Engineering and Computer Science), by Thomas H. Cormen (Author), et al, 2001. http://www.amazon.com/exec/obidos/tg/detail/-/0262031418/ ref = ase_none01A / 103-4588028-6419015? v = glance & s = books NIST Dictionary of Algorithms and Data Structures, http://www.nist.gov/dads/ Red-Black Trees, http://epaperpress.com/sortsearch/ Rbt.html Situ Youth South August 16, 2002 First Edition CST August 17, 2002 10:00:00 First release Situ Youth April 2002 Amendment --------- ----------------------------------- More from http://www.cyut.edu.tw/~ Ckhung / b / al / bst.shtml
Red and black tree is another Balanced Tree. Definitions are as follows: it is basically a binary search tree, but each Node is also painted on color - can be red or black. All Leaves is empty (not included) ), And are black. Red Node must have two Children, and two Children are black. From a Node X, go down, each black nodes encountered on the path to Leaf This fixed number is called x Black-height. Intuitive explanation: I hope to define a (black) Full Binary Tree (the depth of each Leaf), but this condition is obviously too strict, it is impossible (NODES number It can only be 2 ^ k - 1). So there is a red Nodes to be inserted. In addition, the red Nodes can not be too much, so as not to make the tree too unbalanced. Ninternal Nodes's red black tree (can store N-note information) It is Theta (LG N), so it is a balanced tree. The query information is simple; deleting information is more troubles, but the principle is the same as the new increase. A basic action that needs to be used when you add or delete information: Rotation. YX
/ / / /
X c <==> a y
/ / / /
A B B C
X and Y Nodes; A, B, C is a string Subtrees Note: This action carefully maintains the characteristics of Binary Search Tree - the rotation is satisfied before and after: (all elements in A) <= x < = (All elements in B) <= y <= (all elements in C). Aunt, refer to this action as "XY is the axis, rotating to the left / right". How to keep Red-Black Tree when new information Characteristics? First, Dirgas, I found the fall of the new information x, and put X red, and then put it all the way to the whole way: if the father is black, it is too perfect, no need Renewal. End. Otherwise, x father is both red, X 's grandfather must be black. Let Y Women X's uncle. There are three situations to consider:
Y is also red: let the ancestors / father "red color". Now x is no problem, but grandfather may become red, thus generating problems. So let the grandfather play X's role, continue to renovate. Y is black No turned on the road of X to Grandfather: Rotate "Grandfather - Father" is axis, and adjusts the color. Y is black, there is a turn on the road to grandfather: Rotate "Father-X" is axis The situation is handled according to the situation. Note: The second / three conditions indicate that the grandfather can also accommodate new Red Node, so don't need to be renovated again. Conclusion: Whether it is to delete and change, the time required for O (lg (n)).
