?? rbtree.cpp
字號:
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)
{
//如果是空樹
if (node == NULL)
{
return NULL;
}
TreeNode<Type> *max=node;
while(max->right!=NIL)
max=max->right;
return max;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::minnum(TreeNode<Type>*node)
{
//如果是空樹
if (node == NULL)
{
return NULL;
}
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;//父節(jié)點的兄弟
if(uncle->color==RED)//uncle同樣為red
{
father->color=BLACK;
uncle->color=BLACK;
father->parent->color=RED;
change=father->parent;//進行循環(huán)
}else
{
//cout<<"uncle node color=black"<<endl;
if(change==father->right)//內(nèi)插入，左旋
{
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<<"內(nèi)插入"<<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;//父節(jié)點的兄弟
if(uncle->color==RED)//uncle同樣為red
{
father->color=BLACK;
uncle->color=BLACK;
father->parent->color=RED;
change=father->parent;//進行循環(huán)
}else
{
if(change==father->left)//內(nèi)插入
{
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 為需要改變的節(jié)點，找到得key節(jié)點，如果只有一個孩子或者沒有孩子，則需要被刪除的就是該節(jié)點，否則（兩個孩子）
//需要刪除的是直接后繼節(jié)點（首先將key節(jié)點用后繼節(jié)點代替）后繼節(jié)點沒有左孩子
//最后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)//如果被刪除的節(jié)點左孩子不空，則使用act紀錄(key節(jié)點只有左孩子的情況)
act=rn->left;
else//act紀錄key沒有孩子，有右孩子，雙子情況
act=rn->right;
act->parent=rn->parent;//更新父節(jié)點
if(rn->parent==NIL)
ROOT=act;//已經(jīng)將act得parent修改成NIL了
else if(rn == rn->parent->left)
rn->parent->left=act;
else
rn->parent->right=act;
if(rn!=p)//key有兩個孩子時，實際刪除的是p的直接后繼rn節(jié)點，所以需要將后繼節(jié)點的信息復制key節(jié)點中
p->key=rn->key;
if(rn->color==BLACK)
RB_delete_fixup(act);
return rn;
}
//刪除一個黑色節(jié)點后導致兩邊的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);//修改了樹結(jié)構(gòu),這一步后brother為node得祖父節(jié)點并且brother右孩子的black nodes = m不變
brother=parent->right;//修正node得兄弟節(jié)點，現(xiàn)在color(father)=black right(father)=black,并且father->left得
//black nodes還為m-1,father->right得black nodes = m
}
//如果兄弟為黑，則根據(jù)兄弟的孩子來區(qū)分,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，則循環(huán)結(jié)束，將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;
//執(zhí)行旋轉(zhuǎn)后，brother為node得祖父，brother右孩子得black nodes=m,做孩子的black nodes=m(+father為黑色)
left_rotate(father);
node=ROOT;//結(jié)束
}
}
}
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);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -