붉 은 검 은 나무의 독서 노트
이 진 트 리 는 동적 정렬 된 데이터 구조 로 삽입, 삭제, 찾기 등 을 지원 하 며 평균 시간 복잡 도 는 O (log (N) 이지 만 일반 이 진 트 리 는 나무 가 한 가지 로 퇴화 하 는 것 을 보장 하지 못 합 니 다. 이때 최 악의 경우 시간 복잡 도 는 O (N) 입 니 다.이때 균형 이 잡 힌 이 진 트 리 가 생 겼 다.밸 런 스 이 진 트 리 는 밸 런 스 를 동적 으로 조정 하 는 데이터 구조 이지 만 이상 적 인 밸 런 스 이 진 트 리 는 어렵다. 그래서 사람들 은 밸 런 스 이 진 트 리 대신 AVL, 레 드 블랙 트 리, Treap, 스 트 레 칭 트 리 등 을 사용 하 는데 이런 데이터 구 조 는 최 악의 상황 을 잘 개선 할 수 있다.하지만 이 루 기 란 쉽 지 않다.
빨간색 과 검은색 나 무 는 균형 에 가 까 운 데이터 구조 로 삽입, 삭제, 찾기 등의 평균 시간 복잡 도 는 모두 O (N) 로 복잡 하지만 그의 조작 은 좋 은 최 악의 상황 효율 을 가진다. 붉 은 검 은 나 무 는 균형 에 대한 제한 을 풀 었 다.더 이상 엄격 한 의미 의 균형 이 진 트 리 가 아 닐 수 있 습 니 다.
균형 이 진 트 리 는 다음 과 같은 성질 을 만족 시 킵 니 다.
(1) 빨간색 과 검은색 나무 노드 는 빨간색 노드 이거 나 검은색 노드 이다. (2) 뿌리 노드 는 검 은 노드 이다. (3) 잎 노드 (빈 노드) 는 검 은 노드 이다. (4) 모든 빨 간 노드 의 두 개의 키 노드 는 검 은 노드 이다. (5) 각 노드 에 대해 이 노드 에서 자손 노드 까지 의 모든 경로 에 같은 수량의 검 은 노드 를 포함한다.
삽입, 삭제 등 균형 조정 과정 에 대해 서 는 큰 소 를 보 세 요.http://blog.csdn.net/v_july_v / article / details / 654343438 의 블 로그, 나의 주요 사상 학습 은 그 중에서 이 루어 졌 습 니 다. 여기 서 감 사 드 립 니 다!
다음 세그먼트 코드: RedBlackNode. h
#include<iostream>
using namespace std;
const bool RED=true;
const bool BLACK=false;
struct RedBlackNode
{
RedBlackNode *parent;
RedBlackNode *leftChild;
RedBlackNode *rightChild;
int key;
bool color;
RedBlackNode(int tempKey)
{
key=tempKey;
parent=NULL;
leftChild=NULL;
rightChild=NULL;
color=RED;
}
};
다음은 알고리즘 메 인 파일 입 니 다.
#include<iostream>
#include"RedBlackNode.h"
using namespace std;
class RedBlackTree
{
private:
RedBlackNode *Root;
public:
RedBlackTree();
RedBlackNode *GetRoot();
RedBlackNode *FindRB(int );
void UpdataRBNode(int,int);
void InsertRBNode(int);
void InsertFixUp(RedBlackNode *);
void LeftRotate(RedBlackNode *);
void RightRotate(RedBlackNode *);
void DeleteFixUp(RedBlackNode *);
bool DeleteRBNode(int);
void DeleteNoOrOneChildNode(RedBlackNode *,RedBlackNode *);
void PreOrderPrint(RedBlackNode *);
void InOrderPrint(RedBlackNode *);
void SufOrderPrint(RedBlackNode *);
void RotatePrint(RedBlackNode *,int);
};
RedBlackTree::RedBlackTree()
{
Root=NULL;
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
RedBlackNode *RedBlackTree::GetRoot()
{
return this->Root;
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::InsertRBNode(int tempKey)
{
RedBlackNode *pre=NULL,*cur=this->Root;
while(cur!=NULL)
{
pre=cur;
if(cur->key>tempKey)//tempKey
cur=cur->leftChild;
else cur=cur->rightChild;//
}
RedBlackNode *tempNode=new RedBlackNode(tempKey);
tempNode->parent=pre;
if(pre==NULL)//
{
this->Root=tempNode;
}
else if(pre->key>tempNode->key)
pre->leftChild=tempNode;
else pre->rightChild=tempNode;
InsertFixUp(tempNode);//
}
/**********************************************************
* ：
* ： ， NULL
* ：
************************************************************/
RedBlackNode *RedBlackTree::FindRB(int tempKey)
{
RedBlackNode *cur=this->Root;
while(cur!=NULL)
{
if(cur->key==tempKey)
break;
else if(cur->key>tempKey)
cur=cur->leftChild;
else cur=cur->rightChild;
}
return cur;
}
/**********************************************************
* ： oldKey, newKey
* ：
* ：
************************************************************/
void RedBlackTree::UpdataRBNode(int oldKey,int newKey)
{
DeleteRBNode(oldKey);
InsertRBNode(newKey);
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::LeftRotate(RedBlackNode *tempNode)
{
RedBlackNode *rChildNode=tempNode->rightChild;
if(rChildNode->leftChild!=NULL)//
rChildNode->leftChild->parent=tempNode;
rChildNode->parent=tempNode->parent;
if(NULL==tempNode->parent)//
this->Root=rChildNode;
else if(tempNode==tempNode->parent->leftChild)
tempNode->parent->leftChild=rChildNode;
else tempNode->parent->rightChild=rChildNode;
tempNode->parent=rChildNode;
tempNode->rightChild=rChildNode->leftChild;
rChildNode->leftChild=tempNode;
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::RightRotate(RedBlackNode *tempNode)
{
RedBlackNode *lChildNode=tempNode->leftChild;
if(lChildNode->rightChild!=NULL)//
lChildNode->rightChild->parent=tempNode;
lChildNode->parent=tempNode->parent;
if(NULL==tempNode->parent)//
this->Root=lChildNode;
else if(tempNode==tempNode->parent->leftChild)
tempNode->parent->leftChild=lChildNode;
else tempNode->parent->rightChild=lChildNode;
tempNode->parent=lChildNode;
tempNode->leftChild=lChildNode->rightChild;
lChildNode->rightChild=tempNode;
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::InsertFixUp(RedBlackNode *tempNode)
{
RedBlackNode *parTempNode=tempNode->parent,*ancleTempNode;
while(parTempNode!=NULL&&RED==parTempNode->color)//
{
if(parTempNode->parent!=NULL)
{
if(parTempNode->parent->leftChild==parTempNode)
{
ancleTempNode=parTempNode->parent->rightChild;
if(ancleTempNode!=NULL&&RED==ancleTempNode->color)//
{
parTempNode->color=BLACK;
ancleTempNode->color=BLACK;
parTempNode->parent->color=RED;
tempNode=parTempNode->parent;//
parTempNode=tempNode->parent;
}
else
{
if(tempNode==parTempNode->rightChild)
{
LeftRotate(parTempNode);
tempNode=tempNode->leftChild;
parTempNode=tempNode->parent;
}
parTempNode->color=BLACK;
parTempNode->parent->color=RED;
RightRotate(parTempNode->parent);
break;
}
}
else
{
ancleTempNode=parTempNode->parent->leftChild;
if(ancleTempNode!=NULL&&RED==ancleTempNode->color)//
{
parTempNode->color=BLACK;
ancleTempNode->color=BLACK;
parTempNode->parent->color=RED;
tempNode=parTempNode->parent;//
parTempNode=tempNode->parent;
}
else{
if(tempNode==parTempNode->leftChild)
{
RightRotate(parTempNode);
tempNode=tempNode->rightChild;
parTempNode=tempNode->parent;
}
parTempNode->color=BLACK;
parTempNode->parent->color=RED;
LeftRotate(parTempNode->parent);
break;
}
}
}
else break;
}
this->Root->color=BLACK;
}
/**********************************************************
* ：pre ，cur
* ：
* ：
************************************************************/
void RedBlackTree::DeleteNoOrOneChildNode(RedBlackNode *pre,RedBlackNode *cur)
{
if(NULL==cur->leftChild&&NULL==cur->rightChild)//
{
if(NULL==pre)
Root=NULL;
else if(pre->leftChild==cur)
pre->leftChild=NULL;
else pre->rightChild=NULL;
delete cur;
}
else if(cur->rightChild!=NULL)//
{
if(NULL==pre)
{
Root=cur->rightChild;
Root->parent=NULL;
}
else if(pre->leftChild==cur)
{
pre->leftChild=cur->rightChild;
cur->rightChild->parent=pre;
}
else
{
pre->rightChild=cur->rightChild;
cur->rightChild->parent=pre;
}
delete cur;
}
else if(cur->leftChild!=NULL)//
{
if(NULL==pre)
{
Root=cur->leftChild;
Root->parent=NULL;
}
else if(pre->leftChild==cur)
{
pre->leftChild=cur->leftChild;
cur->leftChild->parent=pre;
}
else
{
pre->rightChild=cur->leftChild;
cur->leftChild->parent=pre;
}
delete cur;
}
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::DeleteFixUp(RedBlackNode *tempNode)
{
if(RED==tempNode->color)
InsertFixUp(tempNode);
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
bool RedBlackTree::DeleteRBNode(int tempKey)
{
RedBlackNode *pre=NULL,*cur=Root;
while(cur!=NULL)//
{
if(cur->key==tempKey)
break;
else
{
pre=cur;
if(cur->key>tempKey)
cur=cur->leftChild;
else cur=cur->rightChild;
}
}
if(NULL==cur)return false;
RedBlackNode *tempChild;
bool tempColor;
if(NULL==cur->leftChild||NULL==cur->rightChild)
{
if(NULL==cur->leftChild)//
tempChild=cur->rightChild;
else tempChild=cur->leftChild;
tempColor=cur->color;
DeleteNoOrOneChildNode(pre,cur);
if(tempChild!=NULL&&BLACK==tempColor)
DeleteFixUp(tempChild);
}
else //
{
RedBlackNode *rPre=cur,*rCur=cur->rightChild;//
while(rCur->leftChild!=NULL)
{
rPre=rCur;
rCur=rCur->leftChild;
}
cur->key=rCur->key;
tempChild=rCur->rightChild;//
tempColor=rCur->color;
DeleteNoOrOneChildNode(rPre,rCur);
if(tempChild!=NULL&&BLACK==tempColor)
DeleteFixUp(tempChild);
}
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::PreOrderPrint(RedBlackNode *tempRoot)
{
if(NULL==tempRoot)
return ;
cout<<"("<<tempRoot->key<<",";
if(tempRoot->color)
cout<<" ） ";
else cout<<" ) ";
PreOrderPrint(tempRoot->leftChild);
PreOrderPrint(tempRoot->rightChild);
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::InOrderPrint(RedBlackNode *tempRoot)
{
if(NULL==tempRoot)
return ;
InOrderPrint(tempRoot->leftChild);
cout<<"("<<tempRoot->key<<",";
if(tempRoot->color)
cout<<" ） ";
else cout<<" ) ";
InOrderPrint(tempRoot->rightChild);
}
/**********************************************************
* ：
* ：
* ：
************************************************************/
void RedBlackTree::SufOrderPrint(RedBlackNode *tempRoot)
{
if(NULL==tempRoot)
return ;
SufOrderPrint(tempRoot->leftChild);
SufOrderPrint(tempRoot->rightChild);
cout<<"("<<tempRoot->key<<",";
if(tempRoot->color)
cout<<" ） ";
else cout<<" ) ";
}
/**********************************************************
* ： ，
* ：
* ：
************************************************************/
void RedBlackTree::RotatePrint(RedBlackNode *tempRoot,int tempColumn)
{
if(NULL==tempRoot)
return ;
RotatePrint(tempRoot->leftChild,tempColumn+1);
for(int i=0;i<tempColumn;i++)
cout<<" ";
cout<<"("<<tempRoot->key<<",";
if(tempRoot->color)
cout<<" ）";
else cout<<" )";
cout<<endl;
RotatePrint(tempRoot->rightChild,tempColumn+1);
}
int main()
{
int val;
while(true)
{
RedBlackTree myRedBlackTree;
while(cin>>val)
{
if(val==0)break;
myRedBlackTree.InsertRBNode(val);
}
cout<<endl<<"*****************************"<<endl;
cout<<endl<<"============= ============="<<endl;
myRedBlackTree.PreOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============= ============="<<endl;
myRedBlackTree.InOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============== ============="<<endl;
myRedBlackTree.SufOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============== + ============="<<endl;
myRedBlackTree.RotatePrint(myRedBlackTree.GetRoot(),0);
cout<<endl<<"============================="<<endl;
cout<<"*****************************"<<endl;
while(cin>>val)
{
if(!val)break;
myRedBlackTree.DeleteRBNode(val);
cout<<endl<<"*****************************"<<endl;
cout<<endl<<"============= ============="<<endl;
myRedBlackTree.PreOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============= ============="<<endl;
myRedBlackTree.InOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============== ============="<<endl;
myRedBlackTree.SufOrderPrint(myRedBlackTree.GetRoot());
cout<<endl<<"============== + ============="<<endl;
myRedBlackTree.RotatePrint(myRedBlackTree.GetRoot(),0);
cout<<endl<<"============================="<<endl;
cout<<"*****************************"<<endl;
}
}
system("pause");
return 0;
}부정 을 환영 합 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
