《算法导论》学习总结 — 15. 第13章 红黑树(4)
这一章把前面三篇的代码总结起来，然后推荐一些网上红黑树的优秀讲解资源。
代码：
/*
* Author: Tanky Woo
* Blog: www.WuTianQi.com
* Description: 《算法导论》第13章 Red Black Tree
*/
#include <iostream>
//#define NULL 0
using namespace std;
const int RED = 0;
const int BLACK = 1;
// ①
typedef struct Node{
int color;
int key;
Node *lchild, *rchild, *parent;
}Node, *RBTree;
static Node NIL = {BLACK, 0, 0, 0, 0};
#define NULL (&NIL)
// ②
Node * RBTreeSearch(RBTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return RBTreeSearch(T->lchild, k);
else
return RBTreeSearch(T->rchild, k);
}
/*
BSNode * IterativeRBTreeSearch(RBTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->lchild->key);
x = T->lchild;
else
x = T->rchild;
}
return x;
}
*/
// ③
Node * RBTreeMinimum(RBTree T)
{
while(T->lchild != NULL)
T = T->lchild;
return T;
}
Node * RBTreeMaximum(RBTree T)
{
while(T->rchild != NULL)
T = T->rchild;
return T;
}
// ④
Node *RBTreeSuccessor(Node *x)
{
if(x->rchild != NULL)
return RBTreeMinimum(x->rchild);
Node *y = x->parent;
while(y != NULL && x == y->rchild)
{
x = y;
y = y->parent;
}
return y;
}
void LeftRotate(RBTree &T, Node *x)
{
Node *y = x->rchild;
x->rchild = y->lchild;
if(y->lchild != NULL)
y->lchild->parent = x;
y->parent = x->parent;
if(x->parent == NULL)
T = y;
else
{
if(x == x->parent->lchild)
x->
补充：综合编程 , 其他综合 ,
