The insertion algorithm for 2-3 trees just described is not difficult to understand; now, we will see that it is also not difficult to implement. We will consider a simple representation known as a red-black BST that leads to a natural implementation.
Encoding 3-nodes. The basic idea behind red-black BSTs is to encode 2-3 trees by starting with standard BSTs (which are made up of 2-nodes) and adding extra information to encode 3-nodes. We think of the links as being of two different types: red links, which bind together two 2-nodes to represent 3-nodes, and black links, which bind together the 2-3 tree. Specifically, we represent 3-nodes as two 2-nodes connected by a single red link that leans left (one of the 2-nodes is the left child of the other). One advantage of using such a representation is that it allows us to use our get() code for standard BST search without modification. Given any 2-3 tree, we can immediately derive a corresponding BST, just by converting each node as specified. We refer to BSTs that represent 2-3 trees in this way as red-black BSTs.
An equivalent definition. Another way to proceed is to define red-black BSTs as BSTs having red and black links and satisfying the following three restrictions:
■ Red links lean left.
■ No node has two red links connected to it.
■ The tree has perfect black balance : every path from the root to a null link has the
same number of black links.
There is a 1-1 correspondence between red-black BSTs defined in this way and 2-3 trees.
Color representation. For convenience, since each node is pointed to by precisely one link (from its parent), we encode the color of links in nodes, by adding a boolean instance variable color to our Node data type, which is true if the link from the parent is red and false if tit is black. By convention, null links are black. For clarity in our code, we define constants RED and BLACK for use in setting and testing this variable. We use a private method isRed() to test the color of a node’s link to its parent. When we refer to the color of a node, we are referring to the color of the link pointing to it, and vice versa.
Rotations. The implementation that we will consider might allow right-leaning red links or two red links in a row during an operation, but it always corrects these conditions before completion, through judicious use of an operation called rotation that switches the orientation of red links. First, suppose that we have a right-leaning red link that needs to be rotated to lean to the left (see the diagram at left). This operation is called a left rotation. We organize the computation as a method that takes a link to a red-black BST as argument and, assuming that link to be to a Node h whose right link is red, makes the necessary adjustments and returns a link to a node that is the root of a red-black BST for the same set of keys whose left link is red. If you check each of the lines of code against the before/after drawings in the diagram, you will find this operation is easy to understand: we are switching from having the smaller of the two keys at the root to having the larger of the two keys at the root. Implementing a right rotation that converts a left-leaning red link to a right-leaning one amounts to the same code, with left and right interchanged.
Resetting the link in the parent after a rotation. Whether left or right, every rotation leaves us with a link. We always use the link returned by rotateRight() or rotateLeft() to reset the appropriate link in the parent (or the root of the tree). That may be a right or a left link, but we can always use it to reset the link in the parent. This link may be red or black—both rotateLeft() and rotateRight() preserve its color by setting x.color to h.color. This might allow two red links in a row to occur within the tree, but our algorithms will also use rotations to correct this condition when it arises.
We can use rotations to help maintain the 1-1 correspondence between 2-3 trees and red-black BSTs as new keys are inserted because they pre- serve the two defining properties of red-black BSTs: order and perfect black balance. That is, we can use rotations on a red-black BST without having to worry about losing its order or its perfect black balance. Next, we see how to use rotations to preserve the other two defining properties of red- black BSTs (no consecutive red links on any path and no right-leaning red links).
The insertion and deletion process is fairly complicated, actually they are the most intricate methods in the algorithms that we consider so far. We're not going to explain them step by step, please google it for details. For implementation in Java, please see below:
public class RedBlackBST<Key extends Comparable<Key>, Value> { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; // root of the BST // BST helper node data type private class Node { private Key key; // key private Value val; // associated data private Node left, right; // links to left and right subtrees private boolean color; // color of parent link private int N; // subtree count public Node(Key key, Value val, boolean color, int N) { this.key = key; this.val = val; this.color = color; this.N = N; } } /** * ********************************************************************** * Node helper methods * *********************************************************************** */ // is node x red; false if x is null ? private boolean isRed(Node x) { if (x == null) return false; return (x.color == RED); } // number of node in subtree rooted at x; 0 if x is null private int size(Node x) { if (x == null) return 0; return x.N; } /** * ********************************************************************** * Size methods * *********************************************************************** */ // return number of key-value pairs in this symbol table public int size() { return size(root); } // is this symbol table empty? public boolean isEmpty() { return root == null; } /** * ********************************************************************** * Standard BST search * *********************************************************************** */ // value associated with the given key; null if no such key public Value get(Key key) { return get(root, key); } // value associated with the given key in subtree rooted at x; null if no such key private Value get(Node x, Key key) { while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else return x.val; } return null; } // is there a key-value pair with the given key? public boolean contains(Key key) { return (get(key) != null); } // is there a key-value pair with the given key in the subtree rooted at x? private boolean contains(Node x, Key key) { return (get(x, key) != null); } /** * ********************************************************************** * Red-black insertion * *********************************************************************** */ // insert the key-value pair; overwrite the old value with the new value // if the key is already present public void put(Key key, Value val) { root = put(root, key, val); root.color = BLACK; assert check(); } // insert the key-value pair in the subtree rooted at h private Node put(Node h, Key key, Value val) { if (h == null) return new Node(key, val, RED, 1); int cmp = key.compareTo(h.key); if (cmp < 0) h.left = put(h.left, key, val); else if (cmp > 0) h.right = put(h.right, key, val); else h.val = val; // fix-up any right-leaning links if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.N = size(h.left) + size(h.right) + 1; return h; } /** * ********************************************************************** * Red-black deletion * *********************************************************************** */ // delete the key-value pair with the minimum key public void deleteMin() { if (isEmpty()) throw new NoSuchElementException("BST underflow"); // if both children of root are black, set root to red if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = deleteMin(root); if (!isEmpty()) root.color = BLACK; assert check(); } // delete the key-value pair with the minimum key rooted at h private Node deleteMin(Node h) { if (h.left == null) return null; if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); h.left = deleteMin(h.left); return balance(h); } // delete the key-value pair with the maximum key public void deleteMax() { if (isEmpty()) throw new NoSuchElementException("BST underflow"); // if both children of root are black, set root to red if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = deleteMax(root); if (!isEmpty()) root.color = BLACK; assert check(); } // delete the key-value pair with the maximum key rooted at h private Node deleteMax(Node h) { if (isRed(h.left)) h = rotateRight(h); if (h.right == null) return null; if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); h.right = deleteMax(h.right); return balance(h); } // delete the key-value pair with the given key public void delete(Key key) { if (!contains(key)) { System.err.println("symbol table does not contain " + key); return; } // if both children of root are black, set root to red if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = delete(root, key); if (!isEmpty()) root.color = BLACK; assert check(); } // delete the key-value pair with the given key rooted at h private Node delete(Node h, Key key) { assert contains(h, key); if (key.compareTo(h.key) < 0) { if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); h.left = delete(h.left, key); } else { if (isRed(h.left)) h = rotateRight(h); if (key.compareTo(h.key) == 0 && (h.right == null)) return null; if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); if (key.compareTo(h.key) == 0) { h.val = get(h.right, min(h.right).key); h.key = min(h.right).key; h.right = deleteMin(h.right); } else h.right = delete(h.right, key); } return balance(h); } /** * ********************************************************************** * red-black tree helper functions * *********************************************************************** */ // make a left-leaning link lean to the right private Node rotateRight(Node h) { assert (h != null) && isRed(h.left); Node x = h.left; h.left = x.right; x.right = h; x.color = x.right.color; x.right.color = RED; x.N = h.N; h.N = size(h.left) + size(h.right) + 1; return x; } // make a right-leaning link lean to the left private Node rotateLeft(Node h) { assert (h != null) && isRed(h.right); Node x = h.right; h.right = x.left; x.left = h; x.color = x.left.color; x.left.color = RED; x.N = h.N; h.N = size(h.left) + size(h.right) + 1; return x; } // flip the colors of a node and its two children private void flipColors(Node h) { // h must have opposite color of its two children assert (h != null) && (h.left != null) && (h.right != null); assert (!isRed(h) && isRed(h.left) && isRed(h.right)) || (isRed(h) && !isRed(h.left) && !isRed(h.right)); h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } // Assuming that h is red and both h.left and h.left.left // are black, make h.left or one of its children red. private Node moveRedLeft(Node h) { assert (h != null); assert isRed(h) && !isRed(h.left) && !isRed(h.left.left); flipColors(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); // flipColors(h); } return h; } // Assuming that h is red and both h.right and h.right.left // are black, make h.right or one of its children red. private Node moveRedRight(Node h) { assert (h != null); assert isRed(h) && !isRed(h.right) && !isRed(h.right.left); flipColors(h); if (isRed(h.left.left)) { h = rotateRight(h); // flipColors(h); } return h; } // restore red-black tree invariant private Node balance(Node h) { assert (h != null); if (isRed(h.right)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.N = size(h.left) + size(h.right) + 1; return h; } /** * ********************************************************************** * Utility functions * *********************************************************************** */ // height of tree; 0 if empty public int height() { return height(root); } private int height(Node x) { if (x == null) return 0; return 1 + Math.max(height(x.left), height(x.right)); } /** * ********************************************************************** * Ordered symbol table methods. * *********************************************************************** */ // the smallest key; null if no such key public Key min() { if (isEmpty()) return null; return min(root).key; } // the smallest key in subtree rooted at x; null if no such key private Node min(Node x) { assert x != null; if (x.left == null) return x; else return min(x.left); } // the largest key; null if no such key public Key max() { if (isEmpty()) return null; return max(root).key; } // the largest key in the subtree rooted at x; null if no such key private Node max(Node x) { assert x != null; if (x.right == null) return x; else return max(x.right); } // the largest key less than or equal to the given key public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; else return x.key; } // the largest key in the subtree rooted at x less than or equal to the given key private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) return floor(x.left, key); Node t = floor(x.right, key); if (t != null) return t; else return x; } // the smallest key greater than or equal to the given key public Key ceiling(Key key) { Node x = ceiling(root, key); if (x == null) return null; else return x.key; } // the smallest key in the subtree rooted at x greater than or equal to the given key private Node ceiling(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp > 0) return ceiling(x.right, key); Node t = ceiling(x.left, key); if (t != null) return t; else return x; } // the key of rank k public Key select(int k) { if (k < 0 || k >= size()) return null; Node x = select(root, k); return x.key; } // the key of rank k in the subtree rooted at x private Node select(Node x, int k) { assert x != null; assert k >= 0 && k < size(x); int t = size(x.left); if (t > k) return select(x.left, k); else if (t < k) return select(x.right, k - t - 1); else return x; } // number of keys less than key public int rank(Key key) { return rank(key, root); } // number of keys less than key in the subtree rooted at x private int rank(Key key, Node x) { if (x == null) return 0; int cmp = key.compareTo(x.key); if (cmp < 0) return rank(key, x.left); else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } /** * ******************************************************************** * Range count and range search. * ********************************************************************* */ // all of the keys, as an Iterable public Iterable<Key> keys() { return keys(min(), max()); } // the keys between lo and hi, as an Iterable public Iterable<Key> keys(Key lo, Key hi) { Queue<Key> queue = new Queue<Key>(); // if (isEmpty() || lo.compareTo(hi) > 0) return queue; keys(root, queue, lo, hi); return queue; } // add the keys between lo and hi in the subtree rooted at x // to the queue private void keys(Node x, Queue<Key> queue, Key lo, Key hi) { if (x == null) return; int cmplo = lo.compareTo(x.key); int cmphi = hi.compareTo(x.key); if (cmplo < 0) keys(x.left, queue, lo, hi); if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key); if (cmphi > 0) keys(x.right, queue, lo, hi); } // number keys between lo and hi public int size(Key lo, Key hi) { if (lo.compareTo(hi) > 0) return 0; if (contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); } /** * ********************************************************************** * Check integrity of red-black BST data structure * *********************************************************************** */ private boolean check() { if (!isBST()) StdOut.println("Not in symmetric order"); if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent"); if (!isRankConsistent()) StdOut.println("Ranks not consistent"); if (!is23()) StdOut.println("Not a 2-3 tree"); if (!isBalanced()) StdOut.println("Not balanced"); return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced(); } // does this binary tree satisfy symmetric order? // Note: this test also ensures that data structure is a binary tree since order is strict private boolean isBST() { return isBST(root, null, null); } // is the tree rooted at x a BST with all keys strictly between min and max // (if min or max is null, treat as empty constraint) // Credit: Bob Dondero's elegant solution private boolean isBST(Node x, Key min, Key max) { if (x == null) return true; if (min != null && x.key.compareTo(min) <= 0) return false; if (max != null && x.key.compareTo(max) >= 0) return false; return isBST(x.left, min, x.key) && isBST(x.right, x.key, max); } // are the size fields correct? private boolean isSizeConsistent() { return isSizeConsistent(root); } private boolean isSizeConsistent(Node x) { if (x == null) return true; if (x.N != size(x.left) + size(x.right) + 1) return false; return isSizeConsistent(x.left) && isSizeConsistent(x.right); } // check that ranks are consistent private boolean isRankConsistent() { for (int i = 0; i < size(); i++) if (i != rank(select(i))) return false; for (Key key : keys()) if (key.compareTo(select(rank(key))) != 0) return false; return true; } // Does the tree have no red right links, and at most one (left) // red links in a row on any path? private boolean is23() { return is23(root); } private boolean is23(Node x) { if (x == null) return true; if (isRed(x.right)) return false; if (x != root && isRed(x) && isRed(x.left)) return false; return is23(x.left) && is23(x.right); } // do all paths from root to leaf have same number of black edges? private boolean isBalanced() { int black = 0; // number of black links on path from root to min Node x = root; while (x != null) { if (!isRed(x)) black++; x = x.left; } return isBalanced(root, black); } // does every path from the root to a leaf have the given number of black links? private boolean isBalanced(Node x, int black) { if (x == null) return black == 0; if (!isRed(x)) black--; return isBalanced(x.left, black) && isBalanced(x.right, black); } }
Properties of red-black BSTs:
- The height of a red-black BST with N nodes is no more than 2lgN.
- The average length of a path from the root to a node in a red-black BST with N nodes is ~1.00 lg N.
- In a red-black BST, the following operations take logarithmic time in the worst case: search, insertion, finding the minimum, finding the maximum, floor, ceiling, rank, select, delete the minimum, delete the maximum, delete, and range count.
-
Range search additionally costs time proportional to the number of keys returned
相关推荐
数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...
RedBlackTree.h: Top-down red black tree TestRedBlackTree.cpp: Test program for red black trees Treap.h: Treap TestTreap.cpp: Test program for treap SuffixArray.cpp: Suffix array KdTree.cpp: ...
In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete ...
美国人编码数据结构算法和 Leetcode 问题 - Data structure and Algorithm - [:check_mark: ] Dynamic Array - [:check_mark: ] Doubly Linked list - [:check_mark: ] Stack - [:check_mark: ] Queue - [:check_...
tree(red-black tree,AVL),堆heap,并查集disjoint set,字典树Trie 特殊数据结构 位运算Bitwise,布隆过滤器BloomFilter LRU Cache 算法 if-else,switch for,while loop 递归Recursion(Divide & Conquer,...
如果您想使用包含Binary Trees和Red Black树的公共npm软件包,则可以查看。 如果您有兴趣,请随时分叉或给我留言。安装克隆仓库。 git clone git@github.com:bengolder/js-btree 安装开发依赖项。 cd js-btree npm ...
数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出) (先进先出)...
insertion sort, shell sort, quick sort, merge sort, heap sort), searching algorithms (Binary search tree, Red-Black BST, hashing), 所以程序都用java实现,代码风格简洁,很值得学习。
数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出) (先进先出)...
具有可视化和示例代码的基础数据结构,使用不同的编程语言。 带综合笔记的前 100 名 LeetCode 问题(最高频 100 题:题目重点和深度,非数量) 备忘单和 BrainMap 数据结构 线性 Array Linked List (single and ...
排序和数据结构算法 此存储库是一个C#库,具有已实现的排序算法,结构及其算法。 排序算法: 稳定,通用: 不稳定,通用: 非比较算法: -为整数实现 -为整数实现 -为整数实现 -为整数实现 为字符串实现 数据...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 13.3...
C / C ++中的数据结构和算法 该代码由Amit Bansal在学习数据结构和算法时编写。 参考GFG,NPTEL,CLRS。 该存储库包含: 单链表。 添加两个数字表示的链表。 气泡在链接列表中排序合并在链接列表中排序合并排序链表...
lua算法:Lua算法库,涵盖了常用的数据结构和算法
iruka 用Typescript实现的经典和的集合。... 该存储库的主要目标是教育。 因此,所有实施方式都包含大量指导读者的评论。...数据结构 顺序 优先队列 可合并堆 搜索树 哈希表
l2.2 Querying a binary search tree 2S6 l2.3 Insertion and deletion 261 l2.4 Randoinly built binary search trees 265 13 Red-Black Thees 273 l3.l Properties of red-black trees 273 l3.2 Rotations 277 l...
:link:常用的数据结构和算法-源码
286 12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 ? 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations ...
功能列表数据结构优先队列堆rbtree(red_black_tree) 地图/多地图集/多集位图布隆过滤器hamt(hash_array_mapped_trie) 克塔玛跳过列表算法排序(快速排序) 稳定排序(合并排序) binary_search 下界upper_bound ...