Red Black Tree

10 Key excerpts on "Red Black Tree"

• 

  eBook - ePub

  A Textbook of Data Structures and Algorithms, Volume 2

  Mastering Nonlinear Data Structures

  • G. A. Vijayalakshmi Pai(Author)
  • 2022(Publication Date)
  • Wiley-ISTE

    (Publisher)

  12.3. Applications

  Red-black trees which are derived from B trees of order 4 are only a variant of binary search trees. Hence, any application that calls for binary search trees can also call for red-black trees.

  On the other hand, splay trees which are typical binary search trees undergo splaying to favor retrievals, which are efficient with regard to their amortized complexity. They are suitable for applications with the characteristic that information that is recently retrieved is highly likely to be retrieved in the near future. For example, in the case of a university information system, at the beginning of the admission season, those records pertaining to newly admitted students are highly likely to be accessed over and over again in the first few weeks of their entry. In such a case, it would be a good move to store the records as a splay tree rather than a binary search tree. A splay tree pushes the recently retrieved records to stay closer to the root and in due course those records that were remotely used to move farther and farther away from the root and occupy positions close to the fringe of the tree. Maintenance of patient records in a hospital information system and maintenance of records pertaining to seasonal items in a supermarket information system are some examples where splay trees find ideal applications.

  Splay trees have also found applications in data compression, lexicographic search trees and dynamic Huffman coding.

  Summary

  • Red-black trees are derived from B trees of order 4 and are variants of binary search trees. Red-black trees need to satisfy the red condition, which entails no two red nodes can occur consecutively on a path in the tree, and the black condition that insists that the number of black nodes on all root-to-external node paths must be the same.
  • A search operation on a red-black tree is undertaken the same way as that on a binary search tree. The insertion of a key in a red-black tree is similar to the one in a binary search tree. However, the inserted node is set to red initially to avoid violation of the black condition. If this results in a violation of the red condition as well, then the tree is said to be unbalanced. The imbalance is classified as XYr or XYb where X, Y may represent an L or R. All XYr imbalances call for a mere color change to set right the imbalance. On the other hand, all XYb

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Open Data Structures

  • Pat Morin(Author)
  • 2013(Publication Date)
  • AU Press

    (Publisher)

  Chapter 9 Red-Black Trees In this chapter, we present red-black trees, a version of binary search trees with logarithmic height. Red-black trees are one of the most widely used data structures. They appear as the primary search structure in many library implementations, including the Java Collections Framework and several implementations of the C++ Standard Template Library. They are also used within the Linux operating system kernel. There are several reasons for the popularity of red-black trees: 1. A red-black tree storing n values has height at most 2 log n . 2. The add ( x ) and remove ( x ) operations on a red-black tree run in O (log n ) worst-case time. 3. The amortized number of rotations performed during an add ( x ) or remove ( x ) operation is constant. The first two of these properties already put red-black trees ahead of skiplists, treaps, and scapegoat trees. Skiplists and treaps rely on ran-domization and their O (log n ) running times are only expected. Scapegoat trees have a guaranteed bound on their height, but add ( x ) and remove ( x ) only run in O (log n ) amortized time. The third property is just icing on the cake. It tells us that that the time needed to add or remove an element x is dwarfed by the time it takes to find x . 1 However, the nice properties of red-black trees come with a price: im-plementation complexity. Maintaining a bound of 2 log n on the height 1 Note that skiplists and treaps also have this property in the expected sense. See Exer-cises 4.6 and 7.5 . 185 §9.1 Red-Black Trees Figure 9.1: A 2-4 tree of height 3. is not easy. It requires a careful analysis of a number of cases. We must ensure that the implementation does exactly the right thing in each case. One misplaced rotation or change of colour produces a bug that can be very di ffi cult to understand and track down. Rather than jumping directly into the implementation of red-black trees, we will first provide some background on a related data structure: 2-4 trees.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Java

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  For instance, AVL trees may require many restructure operations (rotations) to be performed after a deletion, and (2, 4) trees may require many split or fusing operations to be performed after an insertion or removal. The data structure we discuss in this section, the red-black tree, does not have these drawbacks; it uses O(1) structural changes after an update in order to stay balanced. Formally, a red-black tree is a binary search tree (see Section 11.1) with nodes colored red and black in a way that satisfies the following properties: Root Property: The root is black. External Property: Every external node is black. Red Property: The children of a red node are black. Depth Property: All external nodes have the same black depth, defined as the number of proper ancestors that are black. An example of a red-black tree is shown in Figure 11.22. 14 13 17 15 12 5 3 4 8 6 7 11 10 Figure 11.22: An example of a red-black tree, with “red” nodes drawn in white. The common black depth for this tree is 3. We can make the red-black tree definition more intuitive by noting an inter- esting correspondence between red-black trees and (2, 4) trees. Namely, given a red-black tree, we can construct a corresponding (2, 4) tree by merging every red node w into its parent, storing the entry from w at its parent, and with the chil- dren of w becoming ordered children of the parent. For example, the red-black tree in Figure 11.22 corresponds to the (2, 4) tree from Figure 11.16, as illustrated in Figure 11.23. The depth property of the red-black tree corresponds to the depth property of the (2, 4) tree since exactly one black node of the red-black tree con- tributes to each node of the corresponding (2, 4) tree. 11.5. Red-Black Trees 463 12 15 11 17 7 5 6 13 8 3 4 14 10 Figure 11.23: An illustration of the correspondance between the red-black tree of Figure 11.22 and the (2, 4) tree of Figure 11.16, based on the highlighted grouping of red nodes with their black parents.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Practical Guide to Data Structures and Algorithms using Java

  • Sally. A Goldman, Kenneth. J Goldman(Authors)
  • 2007(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Critical Mutators: none Competing Data Structures: If the ordered collection will be filled initially and further mutations are very rare, consider ordering the data by means of a red-black tree (or other ordered collection), or sorting a positional collection, and then copying the elements into a sorted array (Chapter 30) for faster search times. Also a sorted array is a good choice if space usage is to be minimized, or if constant time access is needed for retrieving the element at rank i . If mutations are common, and minimum , maximum , successor , predecessor , retreat , and advance are frequently called, then consider instead using a skip list (Chapter 38). If it is important that recently accessed elements need to be efficiently retrieved at the expense of increasing the search time for other elements, then a splay tree (Chapter 35) should be considered. Finally, if the data structure is large enough to require secondary storage then either a B-tree (Chapter 36) or a B+-tree (Chapter 37) should be considered. 513 514 A Practical Guide to Data Structures and Algorithms Using Java t t r n o s c a a b i Figure 34.1 A populated example of a red-black tree for the ordered collection a, a, b, c, i, n, o, r, s, t, t . We use the convention that a filled node is black and an unfilled node is red. 34.1 Internal Representation A red-black tree is an extension of a binary search tree that introduces a color (red or black) for each tree node. It uses this color to determine when to perform operations that balance the search tree to ensure that it has a worst-case height of 2 log 2 ( n + 1) . All properties of the binary search tree are maintained. Instance Variables and Constants: All of the instance variables and constants for RedBlackTree are inherited from BinarySearchTree. The RBNode inner class extends the TreeNode class, adding a boolean instance variable for the color of the node, which is either red ( true ) or black ( false ).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Science with Semantic Technologies

  Theory, Practice and Application

  • Archana Patel, Narayan C. Debnath, Bharat Bhusan(Authors)
  • 2022(Publication Date)
  • Wiley-Scrivener

    (Publisher)

  Keywords: Data structures, algorithms, balanced binary search trees, AVL-trees, Red-Black trees, partitioning *Email: [email protected] 140 Data Science with Semantic Technologies 6.1 Introduction Binary trees are hierarchical data structures to represent collections of items. They are now employed in a variety of computer science fields: memory management, compilers, mathematics, etc. Among the advanced data structures on binary trees, we can cite binary search trees, tries and balanced trees. These structures are more complex and permit to represent large sets. Binary search trees are hierarchical and dynamic data structures. They denote sets in which the members are arranged in a linear order. All values stored in the left subtree of any node x are fewer than the one stored at x, and all values stored in the right subtree of x are higher than the one stored at x, and that is an important property of a binary search tree. This is true for each node in a binary search tree (binary search tree property). Most books about data structures and algorithms contain an important part on binary search trees. The most referenced books are certainly the ones of Knuth and Aho & co. [1, 2]. Many other books have more practical aspects. We can retain as examples: [3] offer various examples of binary tree operations using Pascal language [4]; explore binary search tree imple- mentations in ML and Prolog, among other languages [5]; outlines binary search trees’ basic structure and operations [6–8]; contain more program- ming of binary search trees in C and C++. A delicate part of algorithms on binary search trees consists in main- taining them balanced or balancing them from time to time to keep good performance of operations. Recall that balancing the tree makes the cost of finding any key in lg (n). There are many variations of balanced binary search trees.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Advanced Data Structures

  • Peter Brass(Author)
  • 2008(Publication Date)
  • Cambridge University Press

    (Publisher)

  We will describe now the red-black tree with its standard bottom-up re- balancing method because it is classical textbook material, and in Section 3.5 an alternative top-down rebalancing method. Both work on exactly the same structure. The node of a red-black tree contains as rebalancing information just that color entry. typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; enum {red, black} color; /* possibly other information */ } tree_node_t; We have to maintain the following balancedness properties: (1) each path from the root to a leaf contains the same number of black nodes, and (2) if a red node has lower neighbors, they are black. It is also convenient to add the condition – the root is black. 94 3 Balanced Search Trees This is no restriction because we can always color the root black without affecting the other conditions; but this assumption guarantees that each red node has an upper neighbor that is black, so we can conceptually collapse all red nodes into their upper neighbors to get the isomorphism with (2, 4)-trees. The rebalancing operations are different for insert and delete operations. For insert, we perform the basic insert and color both new leaves red. This possibly violates condition (2), but preserves condition (1); so the rebalancing after the insert starts with a red node with red lower neighbors and moves this color conflict up along the path to the root till it disappears. For delete, we perform the basic delete but retain the colors of the nodes; if the deleted leaves were black, this violates condition (1) but preserves condition (2); again we will move this violation up along the path to the root till it disappears. The insert-rebalance method works as follows: If the violation of (2) occurs in the root, we color the root black. Else let *upper be a node with lower neighbors *current and *other, where *current is the upper node of a pair of red nodes violating (2).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Objects, Abstraction, Data Structures and Design

  Using C++

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  (We have one color in this textbook other than black, so we will use that color to indicate a red node.) 11.3 Red-Black Trees 643 F I G U R E 1 1 . 2 1 Red-Black Tree 644 Chapter 11 Self-Balancing Search Trees Insertion into a Red-Black Tree The algorithm for insertion follows the same recursive search process used for all binary search trees to reach the insertion point. When a leaf is found, the new item is inserted, and it is initially given the color red, so invariant 4 will be maintained. If the parent is black, we are done. However, if the parent is also red, then invariant 3 has been violated. Figure 11.22(a) shows the insertion of 35 as a red child of 30. If the parent’s sibling is also red, then we can change the grandparent’s color to red and change both the parent and parent’s sibling to black. This restores invariant 3 but does not violate invari- ant 4. (See Figure 11.22(b).) If the root of the overall tree is now red, we can change it to black to restore invariant 2, and still maintain invariant 4 (the heights of all paths to a leaf are increased by 1). (See Figure 11.22(c).) If we insert a value with a red parent, but that parent does not have a red sibling (see Figure 11.23(a)), then we change the color of the grandparent to red and the parent to black (see Figure 11.23(b)). Now we have violated invariant 4, as there are more black nodes on the side of the parent. We correct this by rotating about the grandparent so that the parent moves into the position where the grandparent was, thus restoring invariant 4 (see Figure 11.23(c)). F I G U R E 1 1 . 2 2 Insertion into a Red-Black Tree, Case 1 F I G U R E 1 1 . 2 3 Insertion into a Red-Black Tree, Case 2 2 8 5 14 11 7 1 35 30 10 20 20 35 10 30 20 35 10 30 (a) (b) (c) 35 30 20 20 35 30 20 35 30 (a) (b) (c) F I G U R E 1 1 . 2 4 Insertion into a Red-Black Tree, Case 3 (Single Rotation Doesn’t Work) F I G U R E 1 1 .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in C++

  • Michael T. Goodrich, Roberto Tamassia, David M. Mount(Authors)
  • 2011(Publication Date)
  • Wiley

    (Publisher)

  The correspondence between (2, 4) trees and red-black trees provides important intuition that we use in our discussion of how to perform updates in red-black trees. In fact, the update algorithms for red-black trees are mysteriously complex without this intuition. 10.5. Red-Black Trees 475 Proposition 10.9: The height of a red-black tree storing n entries is O(log n). Justification: Let T be a red-black tree storing n entries, and let h be the height of T . We justify this proposition by establishing the following fact log(n + 1) ≤ h ≤ 2 log(n + 1). Let d be the common black depth of all the external nodes of T . Let T ′ be the (2, 4) tree associated with T , and let h ′ be the height of T ′ . Because of the corre- spondence between red-black trees and (2, 4) trees, we know that h ′ = d . Hence, by Proposition 10.8, d = h ′ ≤ log(n + 1). By the internal node property, h ≤ 2d . Thus, we obtain h ≤ 2 log(n + 1). The other inequality, log(n + 1) ≤ h, follows from Proposition 7.10 and the fact that T has n internal nodes. We assume that a red-black tree is realized with a linked structure for binary trees (Section 7.3.4), in which we store a map entry and a color indicator at each node. Thus, the space requirement for storing n keys is O(n). The algorithm for searching in a red-black tree T is the same as that for a standard binary search tree (Section 10.1). Thus, searching in a red-black tree takes O(log n) time. 10.5.1 Update Operations Performing the update operations in a red-black tree is similar to that of a binary search tree, except that we must additionally restore the color properties. Insertion Now consider the insertion of an entry with key k into a red-black tree T , keeping in mind the correspondence between T and its associated (2, 4) tree T ′ and the insertion algorithm for T ′ . The algorithm initially proceeds as in a binary search tree (Section 10.1.2).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Python

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2013(Publication Date)
  • Wiley

    (Publisher)

  A dashed edge in those figures, such as to the right of 7 in part (c), represents a branch with a black deficiency that has not yet been resolved. We illustrate a Case 1 restructuring in parts (c) and (d). We illustrate a Case 2 recoloring in parts (f) and (g). Finally, we show an example of a Case 3 rotation between parts (i) and (j), concluding with a Case 2 recoloring in part (k). 11.6. Red-Black Trees 523 12 7 16 17 15 3 4 5 14 18 7 5 16 18 14 17 15 12 4 (a) (b) 4 16 18 14 17 15 7 5 7 16 18 14 17 15 5 4 (c) (d) 14 16 15 18 7 4 5 16 15 14 7 4 5 5 15 14 7 4 16 (e) (f) (g) 16 14 7 4 5 14 7 4 5 4 7 5 14 14 7 5 4 (h) (i) (j) (k) Figure 11.41: A sequence of deletions from a red-black tree: (a) initial tree; (b) re- moval of 3; (c) removal of 12, causing a black deficit to the right of 7 (handled by restructuring); (d) after restructuring; (e) removal of 17; (f) removal of 18, causing a black deficit to the right of 16 (handled by recoloring); (g) after recoloring; (h) re- moval of 15; (i) removal of 16, causing a black deficit to the right of 14 (handled initially by a rotation); (j) after the rotation the black deficit needs to be handled by a recoloring; (k) after the recoloring. 524 Chapter 11. Search Trees Performance of Red-Black Trees The asymptotic performance of a red-black tree is identical to that of an AVL tree or a (2, 4) tree in terms of the sorted map ADT, with guaranteed logarithmic time bounds for most operations. (See Table 11.2 for a summary of the AVL perfor- mance.) The primary advantage of a red-black tree is that an insertion or deletion requires only a constant number of restructuring operations. (This is in contrast to AVL trees and (2, 4) trees, both of which require a logarithmic number of struc- tural changes per map operation in the worst case.) That is, an insertion or deletion in a red-black tree requires logarithmic time for a search, and may require a loga- rithmic number of recoloring operations that cascade upward.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures

  Abstraction and Design Using Java

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2021(Publication Date)
  • Wiley

    (Publisher)

  If the item is greater than root.data, the process is symmetric and is left as an exercise (Step 23 and Programming Exercise 1). Removal from a Red–Black Tree Removal follows the algorithm for a binary search tree that was described in Chapter 6. Recall that we remove a node only if it is a leaf or if it has only one child. Otherwise, the node that contains the inorder predecessor of the value being removed is the one that is removed. If the node that is removed is red, nothing further must be done because red nodes do not affect a Red–Black tree’s balance. If the node to be removed is black and has a red child, then the red child takes its place, and we color it black. However, if we remove a black leaf, then the black height is now out of balance. There are several cases that must be considered. We will describe them in Programming Project 6 at the end of this chapter. Performance of a Red–Black Tree It can be shown that the upper limit in the height for a Red–Black tree is 2 log 2 n + 2, which is still O(log n). As with the AVL tree, the average performance is significantly better than the worst-case performance. Empirical studies (see Robert Sedgewick, Algorithms in C++, 3rd ed. [Addison-Wesley, 1998], p. 570) show that the average cost of a search in a Red–Black tree built from random values is 1.002 log - n. Thus, both the AVL and Red–Black trees give performance that is close to that of a complete binary search tree. 9.3 Red–Black Trees 463 The TreeMap and TreeSet Classes The Java API has a TreeMap class (part of the package java.util) that implements a Red– Black tree. The TreeMap class implements the SortedMap interface, so it defines methods get, put (a tree insertion), remove, and containsKey, among others. Because a Red–Black tree is used, these are all O(log n) operations. There is also a TreeSet class (introduced in Sec- tion 7.5) that implements the SortedSet interface.

  Sign up to read

  Learn more about book