一、概念
1.定义与性质
（1）定义
红黑树字义：满足(a)每个结点或是红的，或是黑的(b)根结点是黑的(c)每个叶结点（NIL）是黑的(d)如果一个结点是红的，则它的两个儿子是黑的(e)对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点的二叉查找树称为红黑树。
黑高度定义：从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上的黑色结点的个数称为x的黑高度。
（2）性质
红黑树确保没有一条路径会比其它路径长出两倍。
一棵有n个内结点的红黑树的高度至多为2lg(n+1)
2.结构
（1）红黑树结点结构
struct node
{node *left;node *right;node *p;int key;bool color;
};
（2）红黑树结构
struct Red_Black_Tree
{node *root;//根结点node *nil;//哨兵
};
3.红黑树上的操作
SEARCH
PREDECESSOR
MINIMUM
MAXIMUM
INSERT
DELETE
二、代码
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
