网站搭建方案模板,广州网站seo招聘,台州企业网站搭建价格,桐庐做网站红黑树-高级的二叉查找树
平衡树和非平衡树红黑树特征#xff1a;结点都有颜色#xff0c;插入和删除结点时要遵循红黑规则#xff1b;红黑规则 每一个结点不是红色就是黑色#xff1b;跟总是黑色的#xff1b;如果结点时红色的#xff0c;则它的子节点必须是黑色的结点都有颜色插入和删除结点时要遵循红黑规则红黑规则 每一个结点不是红色就是黑色跟总是黑色的如果结点时红色的则它的子节点必须是黑色的从根到叶子结点的每条路径必须包含相同的黑色结点。
修正方法 改变结点颜色旋转C函数库包含的红黑树 #includeset#includemap
C实现红黑树主要类如下 Class RedBlackTreeClass RedBlackNodeNullNodeHeader一个空的红黑树RedBlackTree.h #pragma once
#ifndef RED_BLACKT_REE_H_
#define RED_BLACKT_REE_H_//模板类声明
template class comparable
class RedBlackTree;
template class comparable
class RedBlackNode;//类定义
template class comparable
class RedBlackTree
{
private:RedBlackNodecomparable *header; //红黑树头结点RedBlackNodecomparable *nullNode;//空结点public:enum {RED,BLACK}; //枚举颜色放在RedBlackTree类内部RedBlackTree(const comparable h);~RedBlackTree();
};template class comparable
class RedBlackNode
{comparable element;RedBlackNode* left;RedBlackNode* right;int color;RedBlackNode(const comparable elecomparable(),//comparable类型是传递进来的类型缺省参数赋初值是需要使用自己的类型注意写法。RedBlackNode *lNULL,RedBlackNode* rNULL,int cRedBlackTreecomparable::BLACK): element(ele),left(l),right(r),color(c) //成员函数赋初值{}//友元类RedBlackTree类可以方位RedBlackNode类的默认的private成员数据注意在哪个类中声明友元friend class RedBlackTreecomparable;
};
#endif//类成员函数定义
templateclass comparable
RedBlackTreecomparable::RedBlackTree(const comparable h)
{//new创建节点存储指向根节点的指针不存储其他数据nullNode new RedBlackNodecomparable();//使用缺省参数构造,nullNode-left nullNode;nullNode-right nullNode;//红黑树头指针指向根节点头指针也是一个结点也需要使用new创建只是其不存储数据仅作存储根节点用于指向根节点。header new RedBlackNodecomparable(h);header-left nullNode;header-right nullNode;
}templateclass comparable
inline RedBlackTreecomparable::~RedBlackTree()
{delete nullNode;delete header;
}
