2 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14 * its contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #ifndef RedBlackTree_h
30 #define RedBlackTree_h
32 #include <wtf/Assertions.h>
33 #include <wtf/Noncopyable.h>
37 // This implements a red-black tree with the following properties:
38 // - The allocation of nodes in the tree is entirely up to the user.
39 // - If you are in possession of a pointer to a node, you can delete
40 // it from the tree. The tree will subsequently no longer have a
41 // reference to this node.
42 // - The key type must implement operator< and ==.
44 template<class NodeType, typename KeyType>
46 WTF_MAKE_NONCOPYABLE(RedBlackTree);
55 friend class RedBlackTree;
58 const NodeType* successor() const
62 return treeMinimum(x->right());
63 const NodeType* y = x->parent();
64 while (y && x == y->right()) {
71 const NodeType* predecessor() const
75 return treeMaximum(x->left());
76 const NodeType* y = x->parent();
77 while (y && x == y->left()) {
86 return const_cast<NodeType*>(const_cast<const Node*>(this)->successor());
89 NodeType* predecessor()
91 return const_cast<NodeType*>(const_cast<const Node*>(this)->predecessor());
99 m_parentAndRed = 1; // initialize to red
102 // NOTE: these methods should pack the parent and red into a single
103 // word. But doing so appears to reveal a bug in the compiler.
104 NodeType* parent() const
106 return reinterpret_cast<NodeType*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
109 void setParent(NodeType* newParent)
111 m_parentAndRed = reinterpret_cast<uintptr_t>(newParent) | (m_parentAndRed & 1);
114 NodeType* left() const
119 void setLeft(NodeType* node)
124 NodeType* right() const
129 void setRight(NodeType* node)
136 if (m_parentAndRed & 1)
141 void setColor(Color value)
146 m_parentAndRed &= ~static_cast<uintptr_t>(1);
151 uintptr_t m_parentAndRed;
159 void insert(NodeType* x)
165 while (x != m_root && x->parent()->color() == Red) {
166 if (x->parent() == x->parent()->parent()->left()) {
167 NodeType* y = x->parent()->parent()->right();
168 if (y && y->color() == Red) {
170 x->parent()->setColor(Black);
172 x->parent()->parent()->setColor(Red);
173 x = x->parent()->parent();
175 if (x == x->parent()->right()) {
181 x->parent()->setColor(Black);
182 x->parent()->parent()->setColor(Red);
183 rightRotate(x->parent()->parent());
186 // Same as "then" clause with "right" and "left" exchanged.
187 NodeType* y = x->parent()->parent()->left();
188 if (y && y->color() == Red) {
190 x->parent()->setColor(Black);
192 x->parent()->parent()->setColor(Red);
193 x = x->parent()->parent();
195 if (x == x->parent()->left()) {
201 x->parent()->setColor(Black);
202 x->parent()->parent()->setColor(Red);
203 leftRotate(x->parent()->parent());
208 m_root->setColor(Black);
211 NodeType* remove(NodeType* z)
214 ASSERT(z->parent() || z == m_root);
216 // Y is the node to be unlinked from the tree.
218 if (!z->left() || !z->right())
223 // Y is guaranteed to be non-null at this point.
230 // X is the child of y which might potentially replace y in
231 // the tree. X might be null at this point.
234 x->setParent(y->parent());
235 xParent = x->parent();
237 xParent = y->parent();
241 if (y == y->parent()->left())
242 y->parent()->setLeft(x);
244 y->parent()->setRight(x);
248 if (y->color() == Black)
249 removeFixup(x, xParent);
251 y->setParent(z->parent());
252 y->setColor(z->color());
253 y->setLeft(z->left());
254 y->setRight(z->right());
257 z->left()->setParent(y);
259 z->right()->setParent(y);
261 if (z->parent()->left() == z)
262 z->parent()->setLeft(y);
264 z->parent()->setRight(y);
269 } else if (y->color() == Black)
270 removeFixup(x, xParent);
275 NodeType* remove(const KeyType& key)
277 NodeType* result = findExact(key);
280 return remove(result);
283 NodeType* findExact(const KeyType& key) const
285 for (NodeType* current = m_root; current;) {
286 if (current->key() == key)
288 if (key < current->key())
289 current = current->left();
291 current = current->right();
296 NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const
299 for (NodeType* current = m_root; current;) {
300 if (current->key() == key)
302 if (current->key() < key)
303 current = current->right();
306 current = current->left();
312 NodeType* findGreatestLessThanOrEqual(const KeyType& key) const
315 for (NodeType* current = m_root; current;) {
316 if (current->key() == key)
318 if (current->key() > key)
319 current = current->left();
322 current = current->right();
328 NodeType* first() const
332 return treeMinimum(m_root);
335 NodeType* last() const
339 return treeMaximum(m_root);
342 // This is an O(n) operation.
346 for (NodeType* current = first(); current; current = current->successor())
351 // This is an O(1) operation.
358 // Finds the minimum element in the sub-tree rooted at the given
360 static NodeType* treeMinimum(NodeType* x)
367 static NodeType* treeMaximum(NodeType* x)
374 static const NodeType* treeMinimum(const NodeType* x)
381 static const NodeType* treeMaximum(const NodeType* x)
388 void treeInsert(NodeType* z)
392 ASSERT(!z->parent());
393 ASSERT(z->color() == Red);
396 NodeType* x = m_root;
399 if (z->key() < x->key())
408 if (z->key() < y->key())
415 //----------------------------------------------------------------------
416 // Red-Black tree operations
419 // Left-rotates the subtree rooted at x.
420 // Returns the new root of the subtree (x's right child).
421 NodeType* leftRotate(NodeType* x)
424 NodeType* y = x->right();
426 // Turn y's left subtree into x's right subtree.
427 x->setRight(y->left());
429 y->left()->setParent(x);
431 // Link x's parent to y.
432 y->setParent(x->parent());
436 if (x == x->parent()->left())
437 x->parent()->setLeft(y);
439 x->parent()->setRight(y);
442 // Put x on y's left.
449 // Right-rotates the subtree rooted at y.
450 // Returns the new root of the subtree (y's left child).
451 NodeType* rightRotate(NodeType* y)
454 NodeType* x = y->left();
456 // Turn x's right subtree into y's left subtree.
457 y->setLeft(x->right());
459 x->right()->setParent(y);
461 // Link y's parent to x.
462 x->setParent(y->parent());
466 if (y == y->parent()->left())
467 y->parent()->setLeft(x);
469 y->parent()->setRight(x);
472 // Put y on x's right.
479 // Restores the red-black property to the tree after splicing out
480 // a node. Note that x may be null, which is why xParent must be
482 void removeFixup(NodeType* x, NodeType* xParent)
484 while (x != m_root && (!x || x->color() == Black)) {
485 if (x == xParent->left()) {
486 // Note: the text points out that w can not be null.
487 // The reason is not obvious from simply looking at
488 // the code; it comes about from the properties of the
490 NodeType* w = xParent->right();
491 ASSERT(w); // x's sibling should not be null.
492 if (w->color() == Red) {
495 xParent->setColor(Red);
497 w = xParent->right();
499 if ((!w->left() || w->left()->color() == Black)
500 && (!w->right() || w->right()->color() == Black)) {
504 xParent = x->parent();
506 if (!w->right() || w->right()->color() == Black) {
508 w->left()->setColor(Black);
511 w = xParent->right();
514 w->setColor(xParent->color());
515 xParent->setColor(Black);
517 w->right()->setColor(Black);
520 xParent = x->parent();
523 // Same as "then" clause with "right" and "left"
526 // Note: the text points out that w can not be null.
527 // The reason is not obvious from simply looking at
528 // the code; it comes about from the properties of the
530 NodeType* w = xParent->left();
531 ASSERT(w); // x's sibling should not be null.
532 if (w->color() == Red) {
535 xParent->setColor(Red);
536 rightRotate(xParent);
539 if ((!w->right() || w->right()->color() == Black)
540 && (!w->left() || w->left()->color() == Black)) {
544 xParent = x->parent();
546 if (!w->left() || w->left()->color() == Black) {
548 w->right()->setColor(Black);
554 w->setColor(xParent->color());
555 xParent->setColor(Black);
557 w->left()->setColor(Black);
558 rightRotate(xParent);
560 xParent = x->parent();