数据结构

红黑树理论及实现

作者:dzf 阅读次数:253 时间:2006-12-3 13:41:25 数据结构

红黑树

二叉树在平衡时或者叶子结点到根结点的高度在一定的范围内时工作起来是最有效的。红黑树算法是平衡树的一种算法。这个名字就是由于树的每个结点都被着上了红色或者黑色，结点所着的颜色被用来检测树的平衡性。在对结点插入和删除的操作中，可能会被旋转来保持树的平衡性。平均和最坏情况插入，删除，查找时间都是 O (lg n)。详细内容请参考Cormen [2001]。

理论

一个红黑树是一颗二叉查找树，具有下列的属性:

1. 所有的结点都被着色为红色或者是黑色。

2. 每一个叶子结点都是空结点，并且被着为黑色。

3. 如果父结点是红色的，那么两个子结点都是黑色的。

4. 结点到其子孙结点的每条简单路径上都包含相同数目的黑色结点。

5. 根结点永远是黑色的。

从根结点到叶结点的黑色结点数被称为树的黑色高度。前面关于红黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。

我们来看一下为什么这个结论是正确的。考虑一颗黑色高度为3 得红黑树，从根结点到叶结点的最短路径长度是2(黑-黑-黑)，最长路径为4(黑-红-黑-红-黑)。由于第4条性质，不可能在最长路径中加入更多的黑色结点，因为性质3规定红色结点的子结点必须是黑色的，因此在同一简单路径中不允许有两个连续的红色结点。因此，我们能够建立的最长路径将是一个红黑交替的路径。

概括起来：对于给定的黑色高度为n的红黑树，从根结点到叶结点的简单路径的最短长度为n-1，最大长度为2(n-1)。所有对树的操作必须保持上面列出的属性。特别要指出的是，插入和删除树的结点的操作必须遵循这些原则。

插入

要插入结点，搜索这棵树，找到插入点并添加结点。新的结点替代一个已经存在的在树底部的空结点，并且将拥有两个作为子结点的空结点，在简单的实现中，空结点就是就是一个指向被染为黑色的监视结点的指针，提醒C语言程序员 — 这不是一个空指针！插入新的结点之后，新的结点被染为红色。而后，结点的父结点会被测试看看红黑树的属性有没有被保留下来。如果需要，做一些调整已适应平衡树的需求。

当插入一个红色结点以及他带的两个空的子结点时符合性质4，我们还必须确保红色结点的两个子结点都是黑色的(性质3)。尽管如此，新结点的子结点是黑色时，插入红色的子结点将是违反属性的。这时存在两种要考虑的情况。

红色父结点，父结点的红色兄弟结点

图3-6 描述了一个红-红错误。结点 X 是新插入的结点, 父结点和父亲兄弟结点都被着为红色。一个简单的着色就可以解决这个红-红错误。在重着色后必须检查祖父结点 (结点 B )是否合法，因为它的父结点也可能是红色的，我们不允许连续出现两个红色结点。这样会产生使红色结点上移的效果。结束时根结点应当是黑色的，如果它原先是红色的，则红黑树的黑色高度将增1。

图 3-6: 插入 -红色父结点，父结点的红色兄弟结点

红色父结点,父结点的黑色兄弟结点

图 3-7 描述了一个红-红错误，父亲的兄弟结点是黑色的。如果我们试图给结点重新着色,将结点 A 着成黑色, 这棵树就不平衡了因为我们增加了左支的黑色高度而没有同时增加右支的黑色高度。如果我们同时将结点B改成红色, 两支的黑色高度减小，而且树还是不平衡。如果我们将节点 A 染成黑色，节点C染成红色。情况更为糟糕。因为我们增加了左支的黑色高度，但是减小了右支的黑色高度。为了解决这个问题，我们将要旋转并且重新为结点作如下的着色。在这点上，这个算法就结束了，因为子树的顶点 (节点A)被着为黑色，这样就没有红-红冲突了。

图 3-7: 插入 - 红色父结点,父结点的黑色兄弟结点

结束

为了插入一个结点，我们可能要对结点进行重新着色或者旋转来确保红黑树的属性。如果完成了旋转，作了简单的重着色，我们看到的是红色的结点在子树的顶部，必需遍历这棵树，重复这个过程以确保黑色高度属性的保持。最坏的情况是，我们会一直执行到根结点。插入时间为O(lg n).删除的技术方法和时间与此类似。

// C语言实现

// red-black tree

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdarg.h>

//////////////////////

// supplied by user //

//////////////////////

typedef int KeyType; // type of key

typedef struct { // value related to key

int stuff;

} ValType;

// how to compare keys

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)

/////////////////////////////////////

// implementation independent code //

/////////////////////////////////////

typedef enum {

RBT_STATUS_OK,

RBT_STATUS_MEM_EXHAUSTED,

RBT_STATUS_DUPLICATE_KEY,

RBT_STATUS_KEY_NOT_FOUND

} RbtStatus;

typedef enum { BLACK, RED } nodeColor;

typedef struct NodeTag {

struct NodeTag *left; // left child

struct NodeTag *right; // right child

struct NodeTag *parent; // parent

nodeColor color; // node color (BLACK, RED)

KeyType key; // key used for searching

ValType val; // data related to key

} NodeType;

#define SENTINEL &sentinel // all leafs are sentinels

static NodeType sentinel = { SENTINEL, SENTINEL, 0, BLACK, 0};

static NodeType *root = SENTINEL; // root of red-black tree

static void rotateLeft(NodeType *x) {

// rotate node x to left

NodeType *y = x->right;

// establish x->right link

x->right = y->left;

if (y->left != SENTINEL) y->left->parent = x;

// establish y->parent link

if (y != SENTINEL) y->parent = x->parent;

if (x->parent) {

if (x == x->parent->left)

x->parent->left = y;

else

x->parent->right = y;

} else {

root = y;

}

// link x and y

y->left = x;

if (x != SENTINEL) x->parent = y;

}

static void rotateRight(NodeType *x) {

// rotate node x to right

NodeType *y = x->left;

// establish x->left link

x->left = y->right;

if (y->right != SENTINEL) y->right->parent = x;

// establish y->parent link

if (y != SENTINEL) y->parent = x->parent;

if (x->parent) {

if (x == x->parent->right)

x->parent->right = y;

else

x->parent->left = y;

} else {

root = y;

}

// link x and y

y->right = x;

if (x != SENTINEL) x->parent = y;

}

static void insertFixup(NodeType *x) {

// maintain red-black tree balance

// after inserting node x

// check red-black properties

while (x != root && x->parent->color == RED) {

// we have a violation

if (x->parent == x->parent->parent->left) {

NodeType *y = x->parent->parent->right;

if (y->color == RED) {

// uncle is RED

x->parent->color = BLACK;

y->color = BLACK;

x->parent->parent->color = RED;

x = x->parent->parent;

} else {

// uncle is BLACK

if (x == x->parent->right) {

// make x a left child

x = x->parent;

rotateLeft(x);

}

// recolor and rotate

x->parent->color = BLACK;

x->parent->parent->color = RED;

rotateRight(x->parent->parent);

}

} else {

// mirror image of above code

NodeType *y = x->parent->parent->left;

if (y->color == RED) {

// uncle is RED

x->parent->color = BLACK;

y->color = BLACK;

x->parent->parent->color = RED;

x = x->parent->parent;

} else {

// uncle is BLACK

if (x == x->parent->left) {

x = x->parent;

rotateRight(x);

}

x->parent->color = BLACK;

x->parent->parent->color = RED;

rotateLeft(x->parent->parent);

}

root->color = BLACK;

}

// insert new node (no duplicates allowed)

RbtStatus rbtInsert(KeyType key, ValType val) {

NodeType *current, *parent, *x;

// allocate node for data and insert in tree

// find future parent

current = root;

parent = 0;

while (current != SENTINEL) {

if (compEQ(key, current->key))

return RBT_STATUS_DUPLICATE_KEY;

parent = current;

current = compLT(key, current->key) ?

current->left : current->right;

}

// setup new node

if ((x = malloc (sizeof(*x))) == 0)

return RBT_STATUS_MEM_EXHAUSTED;

x->parent = parent;

x->left = SENTINEL;

x->right = SENTINEL;

x->color = RED;

x->key = key;

x->val = val;

// insert node in tree

if(parent) {

if(compLT(key, parent->key))

parent->left = x;

else

parent->right = x;

} else {

root = x;

}

insertFixup(x);

return RBT_STATUS_OK;

}

static void deleteFixup(NodeType *x) {

// maintain red-black tree balance

// after deleting node x

while (x != root && x->color == BLACK) {

if (x == x->parent->left) {

NodeType *w = x->parent->right;

if (w->color == RED) {

w->color = BLACK;

x->parent->color = RED;

rotateLeft (x->parent);

w = x->parent->right;

}

if (w->left->color == BLACK && w->right->color == BLACK) {

w->color = RED;

x = x->parent;

} else {

if (w->right->color == BLACK) {

w->left->color = BLACK;

w->color = RED;

rotateRight (w);

w = x->parent->right;

}

w->color = x->parent->color;

x->parent->color = BLACK;

w->right->color = BLACK;

rotateLeft (x->parent);

x = root;

}

} else {

NodeType *w = x->parent->left;

if (w->color == RED) {

w->color = BLACK;

x->parent->color = RED;

rotateRight (x->parent);

w = x->parent->left;

}

if (w->right->color == BLACK && w->left->color == BLACK) {

w->color = RED;

x = x->parent;

} else {

if (w->left->color == BLACK) {

w->right->color = BLACK;

w->color = RED;

rotateLeft (w);

w = x->parent->left;

}

w->color = x->parent->color;

x->parent->color = BLACK;

w->left->color = BLACK;

rotateRight (x->parent);

x = root;

}

x->color = BLACK;

}

// delete node

RbtStatus rbtErase(NodeType * z) {

NodeType *x, *y;

if (z->left == SENTINEL || z->right == SENTINEL) {

// y has a SENTINEL node as a child

y = z;

} else {

// find tree successor with a SENTINEL node as a child

y = z->right;

while (y->left != SENTINEL) y = y->left;

}

// x is y‘s only child

if (y->left != SENTINEL)

x = y->left;

else

x = y->right;

// remove y from the parent chain

x->parent = y->parent;

if (y->parent)

if (y == y->parent->left)

y->parent->left = x;

else

y->parent->right = x;

else

root = x;

if (y != z) {

z->key = y->key;

z->val = y->val;

}

if (y->color == BLACK)

deleteFixup (x);

free (y);

return RBT_STATUS_OK;

}

// find key

NodeType *rbtFind(KeyType key) {

NodeType *current;

current = root;

while(current != SENTINEL) {

if(compEQ(key, current->key)) {

return current;

} else {

current = compLT (key, current->key) ?

current->left : current->right;

}

return NULL;

}

// in-order walk of tree

void rbtInorder(NodeType *p, void (callback)(NodeType *)) {

if (p == SENTINEL) return;

rbtInorder(p->left, callback);

callback(p);

rbtInorder(p->right, callback);

}

// delete nodes depth-first

void rbtDelete(NodeType *p) {

if (p == SENTINEL) return;

rbtDelete(p->left);

rbtDelete(p->right);

free(p);

}

void displayNode(NodeType *p) {

printf("%d %d\n", p->key, p->val.stuff);

}

int main(int argc, char **argv) {

int maxnum, ct;

KeyType key;

RbtStatus status;

// command-line:

// rbt 2000

// process 2000 records

NodeType *p;

maxnum = atoi(argv[1]);

printf("maxnum = %d\n", maxnum);

for (ct = maxnum; ct; ct--) {

key = rand() % 90 + 1;

if ((p = rbtFind(key)) != NULL) {

if (p->val.stuff != 10*key) printf("fail val\n");

status = rbtErase(p);

if (status) printf("fail: status = %d\n", status);

} else {

ValType val;

val.stuff = 10*key;

status = rbtInsert(key, val);

if (status) printf("fail: status = %d\n", status);

}

// output nodes in order

rbtInorder(root, displayNode);

rbtDelete(root);

return 0;

}

C语言实现一个用ANSI-C 实现的红黑树包含在这里。 Typedefs recType , keyType , 以及 compLT 和 compEQ 应当改变以反映在树中的数据存储。每一个结点都由 left , right , 和 parent 指针组成。指出每个子结点和父结点。结点的颜色存储在 color 中, 或者是 RED 或者是 BLACK . 所有的椰子结点都是一个监视结点。

函数 insert 分配了一个新的结点并且将这个结点插入树当中。而后，它调用 insertFixup 来确保红黑树属性的维持 erase 从树中删除

个结点，为了维护红黑树的属性, deleteFixup 会被调用。函数 find 查找树中的一个特殊值

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。