数据结构-创新互联
1. 图文解析介绍：
网站设计制作、网站设计的开发，更需要了解用户，从用户角度来建设网站，获得较好的用户体验。创新互联公司多年互联网经验，见的多，沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司，打造的就是网站建设产品直销的概念。选择创新互联公司，不只是建站，我们把建站作为产品，不断的更新、完善，让每位来访用户感受到浩方产品的价值服务。
- 红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
- 红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL
- 由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息
红黑树性质
1.1 存储结构
- 性质一：结点是红色或黑色
- 性质二：根结点是黑色
- 性质三：空结点为叶子结点，且所有叶子结点都是黑色
- 性质四：每个红色结点的两个子结点都是黑色
- 性质五：从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
与一般二叉树相比，红黑树的结构存在父结点指针和结点颜色的标识
typedef char DataType;
typedef struct RBNode
{int color; // 结点颜色（0:黑色 1:红色）
DataType data; // 结点数据
struct RBNode *parent; // 父结点指针，用于定位
struct RBNode *lchild, *rchild; // 左右孩子指针
}RBNode, *RBTree;在红黑树的插入时，第一个问题就是新插入的结点应该为红色还是黑色呢？
- 根据性质二：如果初始红黑树为空，则插入的一定是根节点且为黑色
- 根据性质五：如果新插入的结点为黑色，那么势必会导致路径上的黑色结点数量的增加，无疑增加了插入后的调整难度
- 根据性质三：如果新插入的结点为红色，那么新结点的两个空结点一定为黑色，那么就不会增加路径上的黑色结点数量
总结：若插入的是根结点，则设置为黑色，其他情况则设置为红色
已知新插入的结点为红色，而如果父结点也为红色，就会违反性质四，则说明此时需要调整红黑树
同时在父亲结点为红色的条件下，则根据性质二，父亲结点一定不是根结点，且存在祖父结点
调整情况如下：
2. 源代码若父亲结点为祖父结点的左孩子结点
- 叔叔结点为红色
调整过程：父亲结点和叔叔结点均变为黑色，祖父结点若不是根结点，则变为红色，并将祖父结点视为新插入的结点，继续向上调整
- 叔叔结点为黑色
2.1 插入的位置是父亲结点的左孩子
- 调整过程：父亲结点变为黑色，祖父结点变为红色，最后右旋祖父结点
2.2 插入父亲结点的右孩子
- 调整过程：左旋父结点，而后可视为2.1的情况进行调整
若父亲结点为祖父结点的右孩子结点，其操作与以上情况对称，详细见代码
#include#includetypedef char DataType;
typedef struct RBNode
{int color; // 结点颜色（0:黑色 1:红色）
DataType data; // 结点数据
struct RBNode *parent; // 父结点指针，用于定位
struct RBNode *lchild, *rchild; // 左右孩子指针
}RBNode, *RBTree;
void InitRBTree(RBTree *T)
{(*T) = NULL;
printf("红黑树已初始化!\n");
}
// 创建新结点
RBNode *NewNode(int color, DataType x)
{RBNode *newNode;
newNode = (RBNode *)malloc(sizeof(RBNode));
newNode->data = x;
newNode->color = color;
newNode->parent = newNode->lchild = newNode->rchild = NULL;
return newNode;
}
// 右旋转，
void RightRotate(RBNode *node, int flag)
{RBNode *parent = node->parent;
RBNode *left = node->lchild;
node->lchild = left->rchild;
if (left->rchild)
{left->rchild->parent = node;
}
left->rchild = node;
node->parent = left;
left->parent = parent;
if (parent)
{// flag = 0：node为父结点左孩子
// flag = 1：node为父结点右孩子
!flag ? (parent->lchild = left) : (parent->rchild = left);
}
}
// 左旋转
void LeftRotate(RBNode *node, int flag)
{RBNode *parent = node->parent;
RBNode *right = node->rchild;
node->rchild = right->lchild;
if (right->lchild)
{right->lchild->parent = node;
}
right->lchild = node;
node->parent = right;
right->parent = parent;
if (parent)
{// flag = 0：node为父结点左孩子
// flag = 1：node为父结点右孩子
!flag ? (parent->lchild = right) : (parent->rchild = right);
}
}
// 红黑树调整
void RBTreeAdjust(RBNode *node)
{// 父结点为红色，则父结点一定不是根结点，且祖父结点一定存在
RBNode *father = node->parent;
RBNode *grandfather = father->parent;
RBNode *uncle;
if (father && father == grandfather->lchild)
{// 父亲为祖父的左孩子
uncle = grandfather->rchild;
// printf("\t父亲(%c)为祖父(%c)的左孩子\n", father->data, grandfather->data);
if (uncle && uncle->color == 1)
{// 若叔叔结点存在且为红色，则进行变色
// printf("\t\t叔叔(%c)为红色，进行变色\n", uncle->data);
father->color = 0;
uncle->color = 0;
grandfather->color = 1;
// 递归调整祖父结点
if (grandfather->parent && grandfather->parent->color == 1)
{RBTreeAdjust(grandfather);
}
else if(!grandfather->parent)
{grandfather->color = 0;
}
}
// 叔叔结点不存在，或者为黑色
else if (node == father->lchild)
{// 若插入的结点是父亲的左孩子，则进行变色并对祖父进行右旋转
// printf("\t\t叔叔为黑色，插入位置为父亲的左孩子\n");
// printf("\t\t>>父结点(%c)变黑色，祖父(%c)边红色, 右旋祖父\n", father->data, grandfather->data);
father->color = 0;
grandfather->color = 1;
RightRotate(grandfather, 0);
}
else
{// 若插入的结点是父亲的右孩子，则对父亲进行左旋转
// printf("\t\t叔叔为黑色，插入位置为父亲的右孩子\n");
// printf("\t\t>>左旋父亲结点\n");
LeftRotate(father, 0);
RBTreeAdjust(father);
}
}
else
{// 父亲为祖父的右孩子
uncle = grandfather->lchild;
// printf("\t父亲(%c)为祖父(%c)的右孩子\n", father->data, grandfather->data);
// 以下同理，对称操作
if (uncle && uncle->color == 1)
{// printf("\t\t叔叔(%c)为红色\n", uncle->data);
father->color = 0;
uncle->color = 0;
grandfather->color = 1;
// 递归调整祖父结点
if (grandfather->parent && grandfather->parent->color == 1)
{RBTreeAdjust(grandfather);
}
else if(!grandfather->parent)
{grandfather->color = 0;
}
}
else if (node == father->lchild)
{// printf("\t\t叔叔为黑色，插入位置为父亲的左孩子\n");
// printf("\t\t>>右旋父亲结点\n");
RightRotate(father, 1);
RBTreeAdjust(father);
}
else
{// printf("\t\t叔叔为黑色，插入位置为父亲的右孩子\n");
// printf("\t\t>>父结点(%c)变黑色，祖父(%c)边红色, 左旋祖父\n", father->data, grandfather->data);
father->color = 0;
grandfather->color = 1;
LeftRotate(grandfather, 1);
}
}
}
// 插入
void RBTreeInsert(RBTree *T, DataType x)
{// 若树为空，则创建新结点作为根结点
if ((*T) == NULL)
{// 性质二：根结点为黑色
(*T) = NewNode(0, x);
return;
}
// 根据二叉排序树的性质查找插入位置
RBNode *node = (*T), *parent;
while (node)
{parent = node;
if (node->data >x)
{node = node->lchild;
}
else if (node->data< x)
{node = node->rchild;
}
else
{printf("插入失败，存在相同数据\n");
return;
}
}
// 根据查找到的位置的父结点插入
node = NewNode(1, x);
if (parent->data >x)
{parent->lchild = node;
}
else
{parent->rchild = node;
}
node->parent = parent;
// 若父结点为红色，则不符合性质三：红色结点的孩子结点均为黑色
if (parent->color == 1)
{// printf("父结点(%c)为红色，需要进行调整!\n", parent->data);
RBTreeAdjust(node);
}
}
// 先序遍历
void PreOrderTraverse(RBTree T)
{if (T)
{printf("%c", T->data);
T->color == 0 ? printf("[黑] ") : printf("[红] ");
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
int main()
{RBTree T;
DataType x;
InitRBTree(&T);
while (1)
{fflush(stdin);
printf("输入插入数据:"); // 测试数据：FEKDCABNMOP
scanf("%c", &x);
if (x == '#')
{break;
}
RBTreeInsert(&T, x);
printf("先序遍历:");
PreOrderTraverse(T);
printf("\n\n");
}
system("pause");
return 0;
} 
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页题目：数据结构-创新互联
URL标题：http://hbruida.cn/article/ieioo.html
