西甲

红黑树(RBTree)的分析和实现

2019-09-13 20:03:11来源:励志吧0次阅读

二叉排序树在查找方面提供了很大的方便,但是对worst-case查找/插入/删除/求最值得时间复杂度都为O(n).

红黑树可以保证在worst-case下查找/插入/删除等的复杂度得到O(lgN)。红黑树保持如下特性:

1。节点不是red 就是black

2。root为black

3。所有的leaf为black

4。所有red node 的孩子为black

5。任一node通过左子树和右子树到达叶子节点的black node个数相同

可以证明 红黑树的最大高度为2lg(N+1),所以在红黑树上的操作的时间复杂度为O(lgN)。 其插入和删除操作的时间复杂度都是O(lgN),插入最多需要2次旋转,删除最多需要3次旋转。

其插入和删除操作可能会与红黑树的特性相违背,所以需要修正。在具体的实现中 1)插入的节点都是red。如果其父节点为red,就违背了条件4 2)如果删除的节点为black,违背了条件5需要修正。3)需要一个NIL来表示叶子节点,共享该叶子节点,且为root的父节点,节省空间。

提供了查找 插入 删除 后继 最值操作。

具体实现:

//implement red-black tree

/*

*xiaopei

*06/11/24

*/

#ifndef RBTREE_H

#define RBTREE_H

template <typename Type>

struct TreeNode

{

Type key;

int color;

TreeNode *parent,*left,*right;

};

template <typename Type>

class RBTree

{

private:

enum

{

RED,BLACK

}Color;

Type key;

int color;

TreeNode<Type> *parent,*left,*right;

TreeNode<Type> *NIL;//

TreeNode<Type> *ROOT;

void left_rotate(TreeNode<Type> *&rotate);

void right_rotate(TreeNode<Type> *&rotate);

void RB_insert_fixup(TreeNode<Type>* &node);

void RB_delete_fixup(TreeNode<Type>* &node);

public:

//const static TreeNode<Type>* nil;

RBTree();

TreeNode<Type> *successor(const TreeNode<Type> *node);

TreeNode<Type>* insert(Type key);

TreeNode<Type>* search(Type key);

TreeNode<Type>* remove(Type key);

TreeNode<Type> *maxnum(TreeNode<Type>*node);

TreeNode<Type>* minnum(TreeNode<Type>*node);

TreeNode<Type>* getRoot();

void inorder(TreeNode<Type>*node);

void test()

{

this->insert(1);

this->insert(2);

left_rotate(ROOT);

}

~RBTree();

};

//template <typename Type>

//const TreeNode<Type>* RBTree<Type>::nil=NIL;

template <typename Type>

RBTree<Type>::RBTree()

{

NIL=new TreeNode<Type>;

NIL->color=BLACK;

NIL->key=123456;

NIL->left=0;

NIL->right=0;

NIL->parent=0;

ROOT=NIL;

}

template<typename Type>

RBTree<Type>::~RBTree()

{

delete NIL;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::maxnum(TreeNode<Type>*node)

{

//如果是空树怎么办?

TreeNode<Type> *max=node;

while(max->right!=NIL)

max=max->right;

return max;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::minnum(TreeNode<Type>*node)

{

//如果是空树怎么办?

TreeNode<Type> *min=node;

while(min->left!=NIL)

min=min->left;

return min;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::successor(const TreeNode<Type>* node)

{

if(node->right!=NIL)

return minnum(node->right);

const TreeNode<Type>*s=node;

const TreeNode<Type>*p=s->parent;

while(p!=NIL&&s==p->right){s=p;p=s->parent;}

return const_cast<TreeNode<Type>*>(p);

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::getRoot()

{

TreeNode<Type>*root=ROOT;

return root;

}

template<typename Type>

void RBTree<Type>::left_rotate(TreeNode<Type>*& _rotate)

{

if(_rotate->right==NIL){cout<<"没有右孩子,不能左旋";return ;}//right child is nil, so can not left rotate

TreeNode<Type>* r = _rotate->right;

TreeNode<Type>*t,*rotate=_rotate;

//deal with r->left

rotate->right=r->left;

r->left->parent=rotate;

//deal with r

//t=rotate->parent;

//r->parent=t;//rotate 被修改成了NIL 为什么?

//rotate=rotate->parent;

if(rotate->parent==NIL)

{ROOT=r;r->parent=NIL;}

else if(rotate==rotate->parent->left)

rotate->parent->left=r;

else

rotate->parent->right=r;

r->parent=rotate->parent;

//deal with rotate

rotate->parent=r;

r->left=rotate;

}

template<typename Type>

void RBTree<Type>::right_rotate(TreeNode<Type>* &_rotate)

{

TreeNode<Type>*rotate=_rotate;//不知道为什么,如果直接对_rotate操作,在过程中会改变_rotate得值

if(rotate->left==NIL)return ;//left child is NIL, so can not right rotate

TreeNode<Type>* l = rotate->left;

//deal with l->right

//cout<<"key"<<rotate->parent->key<<endl;

l->right->parent=rotate;

rotate->left=l->right;

//deal with l

l->parent=rotate->parent;

if(rotate->parent==NIL)

{ROOT=l;l->parent=NIL;}

else if(rotate==rotate->parent->left)

rotate->parent->left=l;

else

rotate->parent->right=l;

//deal with rotate

rotate->parent=l;

l->right=rotate;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::insert(Type key)

{

TreeNode<Type> *node=new TreeNode<Type>;

TreeNode<Type> *down=ROOT;

TreeNode<Type> *s=NIL;

while(down!=NIL)

{

s=down;

if(key<down->key)

down=down->left;

else

down=down->right;

}//找到合适位置

node->parent=s;

if(s==NIL)

{ROOT=node;node->parent=NIL;}

else if(key<s->key)

s->left=node;

else

s->right=node;

node->key=key;

node->left=NIL;

node->right=NIL;

node->color=RED;

RB_insert_fixup(node);

return node;

}

template<typename Type>

void RBTree<Type>::RB_insert_fixup(TreeNode<Type>*& change)

{

//TreeNode<Type>*change=node;

TreeNode<Type>*father;

TreeNode<Type>*uncle;

while(change->parent->color==RED)

{

father=change->parent;

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

{

uncle=father->parent->right;//父节点的兄弟

if(uncle->color==RED)//uncle同样为red

{

father->color=BLACK;

uncle->color=BLACK;

father->parent->color=RED;

change=father->parent;//进行循环

}else

{

//cout<<"uncle node color=black"<<endl;

if(change==father->right)//内插入,左旋

{

change=father;

//cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;

left_rotate(change);

father=change->parent;

//cout<<"after rotate key:"<<change->key<<" color "<<change->color<<endl;

//cout<<"内插入"<<endl;

}

//外插入

father->color=BLACK;

father->parent->color=RED;//改变颜色

//cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;

right_rotate(father->parent);

//cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;

}

}

else

{

uncle=father->parent->left;//父节点的兄弟

if(uncle->color==RED)//uncle同样为red

{

father->color=BLACK;

uncle->color=BLACK;

father->parent->color=RED;

change=father->parent;//进行循环

}else

{

if(change==father->left)//内插入

{

change=father;

right_rotate(change);

father=change->parent;

}

//外插入

father->color=BLACK;

father->parent->color=RED;

left_rotate(father->parent);

}

}

}

ROOT->color=BLACK;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::search(Type key)

{

TreeNode<Type> *p=ROOT;

while(p!=NIL&&p->key!=key)

{

if(key<p->key)

p=p->left;

else

p=p->right;

}

return p;

}

template<typename Type>

TreeNode<Type>* RBTree<Type>::remove(Type key)

{

TreeNode<Type> *p = this->search(key);

if(p==NIL)

return p;

//rn 为需要改变的节点,找到得key节点,如果只有一个孩子或者没有孩子,则需要被删除的就是该节点,否则(两个孩子)

//需要删除的是直接后继节点(首先将key节点用后继节点代替)后继节点没有左孩子

//最后rn最多只有一个孩子

TreeNode<Type> *rn=NIL;

TreeNode<Type> *act;

if(p->left==NIL || p->right==NIL)

rn=p;

else

rn = this->successor(p);

if(rn->left!=NIL)//如果被删除的节点左孩子不空,则使用act纪录(key节点只有左孩子的情况)

act=rn->left;

else//act纪录key没有孩子,有右孩子,双子情况

act=rn->right;

act->parent=rn->parent;//更新父节点

if(rn->parent==NIL)

ROOT=act;//已经将act得parent修改成NIL了

else if(rn == rn->parent->left)

rn->parent->left=act;

else

rn->parent->right=act;

if(rn!=p)//key有两个孩子时,实际删除的是p的直接后继rn节点,所以需要将后继节点的信息复制key节点中

p->key=rn->key;

if(rn->color==BLACK)

RB_delete_fixup(act);

return rn;

}

//删除一个黑色节点后导致两边的bh不同。

template<typename Type>

void RBTree<Type>::RB_delete_fixup(TreeNode<Type> *&_node)

{

TreeNode<Type>*father,*brother,*node;

node=_node;

father=node->parent;

while(node!=ROOT&&node->color==BLACK)//如果color(x)为red,只需要讲color(x)=black就行了

{

if(node=father->left)//color(node)=black,father左孩子得black nodes(m-1) =father右孩子的black nodes(m) -1

{

brother=father->right;

if(brother->color==RED)//color(father)=black,********************case 1

{

brother->color=BLACK;

father->color=RED;

left_rotate(father);//修改了树结构,这一步后brother为node得祖父节点并且brother右孩子的black nodes = m不变

brother=parent->right;//修正node得兄弟节点,现在color(father)=black right(father)=black,并且father->left得

//black nodes还为m-1,father->right得black nodes = m

}

//如果兄弟为黑,则根据兄弟的孩子来区分,color(Node)=black,color(brother)=black,color(father)未知

if(brother->left->color==BLACK&&brother->right->color==BLACK)//********************case 2

{

brother->color=RED;//fater右孩子的black nodes = m-1

node=father;//如果father为red,则循环结束,将father改为black,则整个以father为根的子树左右孩子的black nodes都为m

}

else

{

if(brother->right->color==BLACK)//右孩子为黑色********************case 3

{

brother->left->color=BLACK;

brother->color=RED;

right_rotate(brother);

brother=father->right;//brother的右孩子为red

}

//if(brother->right->color==RED)************************case 4

father->color=BLACK;

brother->right->color=BLACK;//red修改成black

brother->color=father->color;

//执行旋转后,brother为node得祖父,brother右孩子得black nodes=m,做孩子的black nodes=m(+father为黑色)

left_rotate(father);

node=ROOT;//结束

}

}

}

node->color=BLACK;

}

template<typename Type>

void RBTree<Type>::inorder(TreeNode<Type>*node)

{

if(node!=NIL)

{

inorder(node->left);

if(node->color==RED)

if(node->left->color==RED||node->right->color==RED)

cout<<"wrong"<<" ";

cout<<node->key<<" ";

inorder(node->right);

}

}

#endif

宝宝中暑
老年尿急怎么治疗
心肌梗塞早期的症状
小儿厌食怎样治疗
分享到: