데이터 구조의 붉 은 검 은 나무의 실현
14942 단어 데이터 구조
#include<iostream>
using namespace std;
#include<assert.h>
enum color{
RED,
BLACK,
};
template<class K, class V>
struct TreeNode{
public:
TreeNode<K, V>* _left;
TreeNode<K, V>* _right;
TreeNode<K, V>* _parent;
color _color;
V _val;;
TreeNode(const V& val)
:_val(val)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _color(RED)
{}
};
template<class K, class V>
class RBTree{
public:
typedef TreeNode<K, V> Node;
RBTree()
:_root(NULL)
{}
bool Insert(const V& val){
if (_root == NULL){
_root = new Node(val);
_root->_color = BLACK;
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur){
if (val < cur->_val){
parent = cur;
cur = cur->_left;
}
else if (val>cur->_val){
parent = cur;
cur = cur->_right;
}
else{
return false;
}
}
cur = new Node(val);
if (cur->_val < parent->_val){
parent->_left = cur;
cur->_parent = parent;
}
else{
parent->_right = cur;
cur->_parent = parent;
}
//
Node* grandfather = parent->_parent;
while (parent&&parent->_color == RED){
if (grandfather->_left == parent){
Node* uncle = grandfather->_right;
if (uncle&&uncle->_color == RED){//
parent->_color = BLACK;
uncle->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else{// /
if (parent->_right == cur){
RotateL(parent);
swap(cur, parent);
}
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color= RED;
break;
}
}
else{
Node* uncle = grandfather->_left;
if (uncle&&uncle->_color == RED){
uncle->_color = BLACK;
parent->_color = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else{
if (parent->_left == cur){
RotateR(parent);
swap(cur, parent);
}
RotateL(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
break;
}
}
}
_root->_color = BLACK;
return true;
}
void RotateL(Node* parent){
assert(parent);
Node* ppNode = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_left = subRL;
if (subRL){
subRL->_parent = parent;
}
if (ppNode == NULL){
_root = subR;
subR->_parent = ppNode;
}
else{
if (ppNode->_left == parent){
ppNode->_left = subR;
subR->_parent = ppNode;
}
else{
ppNode->_right = subR;
subR->_parent = ppNode;
}
}
subR->_left = parent;
parent->_parent = subR;
}
void RotateR(Node* parent){
assert(parent);
Node* ppNode = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_right = subLR;
if (subLR){
subLR->_parent = parent;
}
if (ppNode == NULL){
_root = subL;
subL->_parent = ppNode;
}
else{
if (ppNode->_left == parent){
ppNode->_left = subL;
subL->_parent = ppNode;
}
else{
ppNode->_right = subL;
subL->_parent = ppNode;
}
}
subL->_right = parent;
parent->_parent = subL;
}
bool IsBlance(){
if (_root&&_root->_color == RED){
return false;
}
int N = 0;int blacknum = 0;
return _IsBalance(_root, blacknum, N);
}
bool _IsBalance(Node* root, size_t blacknum, const size_t N){
if (root == NULL){
return true;
}
if (root->_color == BLACK){
++blacknum;
}
if (root->_color == RED&&root->_parent->_color == RED){
cout << " " << endl;
}
return _IsBalance(root->_left, blacknum, N) && _IsBalance(root->_right, blacknum, N);
}
private:
Node* _root;
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.