Lenyiin/RBTree
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
RBTree/Windows_RBTree/RBTree.hpp

846 lines
24 KiB
C++
Raw Permalink Normal View History

博客 https://blog.lenyiin.com/rbtree/ 的代码仓库
2024-09-19 02:07:52 +08:00
#pragma once
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
namespace Lenyiin
{
enum Colour
{
RED,
BLACK
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
std::pair<K, V> _kv;
Colour _colour;
RBTreeNode(const std::pair<K, V>& kv)
: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _colour(RED)
{
}
};
template <class K, class V>
class RBTree
{
private:
typedef RBTreeNode<K, V> Node;
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void RotateL(Node* parent)
{
Node* ppNode = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
// 1. ԭ<><D4AD> parent <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĸ<EFBFBD>, <20><><EFBFBD><EFBFBD> subR <20>Ǹ<EFBFBD>
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
// 2. parent Ϊ<><CEAA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֻ<EFBFBD><D6BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD><D0B5><EFBFBD><EFBFBD><EFBFBD>, <20>ı<EFBFBD><C4B1><EFBFBD><EFBFBD>ӹ<EFBFBD>ϵ, <20><>ô subR Ҫ<><D2AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
// <20>ҵ<EFBFBD><D2B5><EFBFBD>
void RotateR(Node* parent)
{
Node* ppNode = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
// ɾ<><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void DeleteTree(Node* root)
{
if (root == nullptr)
{
return;
}
// <20>ݹ<EFBFBD>ɾ<EFBFBD><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
DeleteTree(root->_left);
// <20>ݹ<EFBFBD>ɾ<EFBFBD><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
DeleteTree(root->_right);
// ɾ<><C9BE><EFBFBD><EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
delete root;
}
public:
RBTree(Node* root = nullptr)
: _root(root)
{
}
~RBTree()
{
DeleteTree(_root);
}
// 1. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڡ<EFBFBD>
// 2. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɫ<EFBFBD>ڵ㣬<DAB5><E3A3AC><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// 3. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɫ<EFBFBD>ڵ㣬<DAB5><E3A3AC><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD><C6B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>游<EFBFBD><E6B8B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>Ϊ<EFBFBD><CEAA>ɫ<EFBFBD><C9AB><EFBFBD>ؼ<EFBFBD><D8BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// a. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD>죬<EFBFBD>Ѹ<EFBFBD><D1B8>׺<EFBFBD><D7BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڣ<EFBFBD><DAA3>游<EFBFBD><E6B8B8><EFBFBD>죬<EFBFBD><ECA3AC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϴ<EFBFBD><CFB4><EFBFBD><EFBFBD><EFBFBD>
// b. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD>ڣ<EFBFBD><DAA3><EFBFBD><EFBFBD>߲<EFBFBD><DFB2><EFBFBD><EFBFBD>ڡ<EFBFBD><DAA1><EFBFBD>ת<EFBFBD><D7AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD> or ˫<><CBAB><EFBFBD><EFBFBD>+ <20><>ɫ
bool Insert(const std::pair<K, V>& kv)
{
// 1. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ĺ<EFBFBD><C4B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>в<EFBFBD><D0B2><EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD>գ<EFBFBD>ֱ<EFBFBD>ӽ<EFBFBD><D3BD>½ڵ<C2BD><DAB5><EFBFBD>Ϊ<EFBFBD><CEAA><EFBFBD>ڵ㣬<DAB5><E3A3AC>Ⱦ<EFBFBD>ɺ<EFBFBD>ɫ
if (_root == nullptr)
{
_root = new Node(kv);
_root->_colour = BLACK; // <20><><EFBFBD>ڵ<EFBFBD><DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>
return true;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ<C4BD><DAB5>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD>
}
}
// <20>ҵ<EFBFBD>λ<EFBFBD><CEBB> <20><><EFBFBD><EFBFBD><EFBFBD>½ڵ<C2BD>
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
InsertFixUp(parent, cur);
return true;
}
void InsertFixUp(Node* parent, Node* cur)
{
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɫ
// <20>½<EFBFBD><C2BD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ļ<EFBFBD><C4BB>Ǻڵ<C7BA>? <09><>ɫ
// 1. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڡ<EFBFBD>
// 2. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD>, <20><><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// 3. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD>, <20><><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>, <20><><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD><C6B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>游<EFBFBD><E6B8B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>Ϊ<EFBFBD><CEAA>ɫ<EFBFBD><C9AB><EFBFBD>ؼ<EFBFBD><D8BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// a. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>, <20>Ѹ<EFBFBD><D1B8>׺<EFBFBD><D7BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20>游<EFBFBD><E6B8B8><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϴ<EFBFBD><CFB4><EFBFBD><EFBFBD><EFBFBD>
// b. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>, <20><><EFBFBD>߲<EFBFBD><DFB2><EFBFBD><EFBFBD>ڡ<EFBFBD><DAA1><EFBFBD>ת<EFBFBD><D7AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD> or ˫<><CBAB><EFBFBD><EFBFBD>+ <20><>ɫ
while (parent && parent->_colour == RED)
{
// <20>ؼ<EFBFBD><D8BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// <20><><EFBFBD><EFBFBD>1: uncle <20><><EFBFBD><EFBFBD>, <20><>Ϊ<EFBFBD><CEAA>
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϵ<EFBFBD><CFB5><EFBFBD>
cur = grandfather;
parent = cur->_parent;
}
// <20><><EFBFBD><EFBFBD> 2 or <20><><EFBFBD><EFBFBD> 3 : uncle <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> or uncle <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>
else
{
// <20><><EFBFBD><EFBFBD> 3: ˫<><CBAB> -> <20><><EFBFBD>ɵ<EFBFBD><C9B5><EFBFBD>
if (cur == parent->_right)
{
RotateL(parent);
std::swap(parent, cur);
}
// <20>ڶ<EFBFBD><DAB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> (ps: <20>п<EFBFBD><D0BF><EFBFBD><EFBFBD>ǵ<EFBFBD><C7B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>)
RotateR(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
else
{
Node* uncle = grandfather->_left;
// <20><><EFBFBD><EFBFBD>1: uncle <20><><EFBFBD><EFBFBD>, <20><>Ϊ<EFBFBD><CEAA>
if (uncle && uncle->_colour == RED)
{
parent->_colour = BLACK;
uncle->_colour = BLACK;
grandfather->_colour = RED;
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϵ<EFBFBD><CFB5><EFBFBD>
cur = grandfather;
parent = cur->_parent;
}
// <20><><EFBFBD><EFBFBD>2 or <20><><EFBFBD><EFBFBD>3: uncle <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> or uncle <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>
else
{
// <20><><EFBFBD><EFBFBD>3: ˫<><CBAB> -> <20><>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>
if (cur == parent->_left)
{
RotateR(parent);
std::swap(parent, cur);
}
// <20>ڶ<EFBFBD><DAB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> (ps: <20>п<EFBFBD><D0BF><EFBFBD><EFBFBD>ǵ<EFBFBD><C7B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>)
RotateL(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
}
// <20><>֤<EFBFBD><D6A4><EFBFBD>ڵ<EFBFBD>Ϊ<EFBFBD><CEAA>ɫ
_root->_colour = BLACK;
}
// ɾ<><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
bool Erase(const K& key)
{
// <20><><EFBFBD>ҽڵ<D2BD>
Node* nodeToDelete = _root;
while (nodeToDelete)
{
if (nodeToDelete->_kv.first > key)
{
nodeToDelete = nodeToDelete->_left;
}
else if (nodeToDelete->_kv.first < key)
{
nodeToDelete = nodeToDelete->_right;
}
else
{
break; // <20>ҵ<EFBFBD><D2B5><EFBFBD>ɾ<EFBFBD><C9BE><EFBFBD>Ľڵ<C4BD>
}
}
// <20><><EFBFBD><EFBFBD>δ<EFBFBD>ҵ<EFBFBD><D2B5>ڵ<EFBFBD>
if (nodeToDelete == nullptr)
{
return false;
}
// ִ<><D6B4>ɾ<EFBFBD><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
Node* parent, * child;
Colour originalColour = nodeToDelete->_colour;
if (nodeToDelete->_left == nullptr)
{
child = nodeToDelete->_right;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_right);
}
else if (nodeToDelete->_right == nullptr)
{
child = nodeToDelete->_left;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_left);
}
else
{
Node* successor = Minimum(nodeToDelete->_right);
originalColour = successor->_colour;
child = successor->_right;
if (successor->_parent == nodeToDelete)
{
parent = successor;
}
else
{
Transplant(successor, successor->_right);
successor->_right = nodeToDelete->_right;
successor->_right->_parent = successor;
parent = successor->_parent;
}
Transplant(nodeToDelete, successor);
successor->_left = nodeToDelete->_left;
successor->_left->_parent = successor;
successor->_colour = nodeToDelete->_colour;
}
delete nodeToDelete;
// <20><><EFBFBD><EFBFBD>ɾ<EFBFBD><C9BE><EFBFBD>Ľڵ<C4BD><DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB><EFBFBD><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD>е<EFBFBD><D0B5><EFBFBD>
if (originalColour == BLACK)
{
EraseFixUp(child, parent);
}
return true;
}
void EraseFixUp(Node* x, Node* parent)
{
while (x != _root && (x == nullptr || x->_colour == BLACK))
{
if (x == parent->_left)
{
Node* w = parent->_right;
// <20><><EFBFBD><EFBFBD>1: x<><78><EFBFBD>ֵܽڵ<DCBD>w<EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>
if (w->_colour == RED)
{
w->_colour = BLACK;
parent->_colour = RED;
RotateL(parent);
w = parent->_right;
}
// <20><><EFBFBD><EFBFBD>2: x<><78><EFBFBD>ֵܽڵ<DCBD>w<EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӽڵ㶼<DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>
if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
(w->_right == nullptr || w->_right->_colour == BLACK))
{
w->_colour = RED;
x = parent;
parent = x->_parent;
}
else
{
// <20><><EFBFBD><EFBFBD>3: w<>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ
if (w->_right == nullptr || w->_right->_colour == BLACK)
{
if (w->_left)
w->_left->_colour = BLACK;
w->_colour = RED;
RotateR(w);
w = parent->_right;
}
// <20><><EFBFBD><EFBFBD>4: w<>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ
if (w)
{
w->_colour = parent->_colour;
parent->_colour = BLACK;
if (w->_right)
w->_right->_colour = BLACK;
RotateL(parent);
}
x = _root;
break;
}
}
else
{
Node* w = parent->_left;
// <20><><EFBFBD><EFBFBD>1: x<><78><EFBFBD>ֵܽڵ<DCBD>w<EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>
if (w->_colour == RED)
{
w->_colour = BLACK;
parent->_colour = RED;
RotateR(parent);
w = parent->_left;
}
// <20><><EFBFBD><EFBFBD>2: x<><78><EFBFBD>ֵܽڵ<DCBD>w<EFBFBD>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӽڵ㶼<DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB>
if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
(w->_right == nullptr || w->_right->_colour == BLACK))
{
w->_colour = RED;
x = parent;
parent = x->_parent;
}
else
{
// <20><><EFBFBD><EFBFBD>3: w<>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ<EFBFBD><C9AB><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ
if (w->_left == nullptr || w->_left->_colour == BLACK)
{
if (w->_right)
{
w->_right->_colour = BLACK;
}
w->_colour = RED;
RotateL(w);
w = parent->_left;
}
// <20><><EFBFBD><EFBFBD>4: w<>Ǻ<EFBFBD>ɫ<EFBFBD>ģ<EFBFBD><C4A3><EFBFBD><EFBFBD><EFBFBD>w<EFBFBD><77><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5>Ǻ<EFBFBD>ɫ
if (w)
{
w->_colour = parent->_colour;
parent->_colour = BLACK;
if (w->_left)
{
w->_left->_colour = BLACK;
}
RotateR(parent);
}
x = _root;
break;
}
}
}
if (x)
{
x->_colour = BLACK;
}
}
Node* Minimum(Node* node)
{
while (node->_left != nullptr)
{
node = node->_left;
}
return node;
}
void Transplant(Node* u, Node* v)
{
if (u->_parent == nullptr)
{
_root = v;
}
else if (u == u->_parent->_left)
{
u->_parent->_left = v;
}
else
{
u->_parent->_right = v;
}
if (v != nullptr)
{
v->_parent = u->_parent;
}
}
// <20><><EFBFBD>ҽڵ<D2BD>
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
// ǰ<><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵݹ<C4B5>ʵ<EFBFBD><CAB5>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// void _PreOrder(Node *root)
// {
// if (root == nullptr)
// {
// return;
// }
// // <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
// std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
// _PreOrder(root->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// _PreOrder(root->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// }
// void PreOrder()
// {
// std::cout << "ǰ<><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
// _PreOrder(_root);
// std::cout << std::endl;
// }
// ǰ<><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ķǵݹ<C7B5>ʵ<EFBFBD><CAB5>
void PreOrder()
{
if (_root == nullptr)
{
return;
}
std::stack<Node*> stack;
stack.push(_root);
std::cout << "ǰ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
while (!stack.empty())
{
Node* cur = stack.top();
stack.pop();
// <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";
// <20><>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȷ<EFBFBD><C8B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȴ<EFBFBD><C8B4><EFBFBD><EFBFBD><EFBFBD>
if (cur->_right != nullptr)
{
stack.push(cur->_right);
}
if (cur->_left != nullptr)
{
stack.push(cur->_left);
}
}
std::cout << std::endl;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// void _InOrder(Node *root)
// {
// if (root == nullptr)
// {
// return;
// }
// _InOrder(root->_left);
// // <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
// std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
// _InOrder(root->_right);
// }
// void InOrder()
// {
// std::cout << "<22><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
// _InOrder(_root);
// std::cout << std::endl;
// }
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20>ǵݹ<C7B5>
void InOrder()
{
std::stack<Node*> stack;
Node* cur = _root;
std::cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
while (cur != nullptr || !stack.empty())
{
// <20>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߵĽڵ<C4BD>
while (cur != nullptr)
{
stack.push(cur);
cur = cur->_left;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
cur = stack.top();
stack.pop();
// <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";
// ת<><D7AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
cur = cur->_right;
}
std::cout << std::endl;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵݹ<C4B5>ʵ<EFBFBD><CAB5>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// void _PostOrder(Node *root)
// {
// if (root == nullptr)
// {
// return;
// }
// _PostOrder(root->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// _PostOrder(root->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// // <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
// std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
// }
// void PostOrder()
// {
// std::cout << "<22><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
// _PostOrder(_root);
// std::cout << std::endl;
// }
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ķǵݹ<C7B5>ʵ<EFBFBD><CAB5>
void PostOrder()
{
if (_root == nullptr)
{
return;
}
std::stack<Node*> st;
Node* cur = _root;
Node* lastNode = nullptr; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʵĽڵ<C4BD>
std::cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ";
while (cur || !st.empty())
{
while (cur)
{
st.push(cur);
cur = cur->_left;
}
Node* top = st.top();
if ((top->_right == nullptr) || (lastNode == top->_right))
{
// <20><><EFBFBD>ʵ<EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
std::cout << top->_kv.first << " (" << (top->_colour == RED ? "RED" : "BLACK") << ") ";
lastNode = top;
st.pop();
}
else
{
cur = top->_right;
}
}
std::cout << std::endl;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void LevelOrder()
{
if (_root == nullptr)
{
return;
}
std::queue<Node*> queue;
queue.push(_root);
std::cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: " << std::endl;
while (!queue.empty())
{
int size = queue.size();
while (size--)
{
Node* cur = queue.front();
queue.pop();
// <20><><EFBFBD>ʵ<EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";
if (cur->_left != nullptr)
{
queue.push(cur->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
}
if (cur->_right != nullptr)
{
queue.push(cur->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
// <20><><EFBFBD>Һ<EFBFBD><D2BA>̽ڵ<CCBD>
Node* findMin(Node* node)
{
while (node->_left != nullptr)
{
node = node->_left;
}
return node;
}
Node* FindSuccessor(Node* node)
{
if (node->_right != nullptr)
{
return findMin(node->_right);
}
Node* cur = _root;
Node* successor = nullptr;
while (cur != nullptr)
{
if (node->_kv.first < cur->_kv.first)
{
successor = cur;
cur = cur->_left;
}
else if (node->_kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else
{
break;
}
}
return successor;
}
// <20><><EFBFBD><EFBFBD>ǰ<EFBFBD><C7B0><EFBFBD>ڵ<EFBFBD>
Node* findMax(Node* node)
{
while (node->_right != nullptr)
{
node = node->_right;
}
return node;
}
Node* FindPredecessor(Node* node)
{
if (node->_left != nullptr)
{
return findMax(node->_left);
}
Node* cur = _root;
Node* predecessor = nullptr;
while (cur != nullptr)
{
if (node->_kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (node->_kv.first > cur->_kv.first)
{
predecessor = cur;
cur = cur->_right;
}
else
{
break;
}
}
return predecessor;
}
// <20>ж<EFBFBD><D0B6>Ƿ<EFBFBD><C7B7>Ǻ<EFBFBD><C7BA><EFBFBD><EFBFBD><EFBFBD>
bool IsRBTree()
{
// <20><><EFBFBD><EFBFBD>Ҳ<EFBFBD>Ǻ<EFBFBD><C7BA><EFBFBD><EFBFBD><EFBFBD>
if (_root == nullptr)
{
return true;
}
// 1. <20><><EFBFBD>Ǻ<EFBFBD>ɫ
if (_root->_colour != BLACK)
{
std::cout << "<EFBFBD><EFBFBD><EFBFBD>ڵ㲻<EFBFBD>Ǻ<EFBFBD>ɫ" << std::endl;
return false;
}
// <20><>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>·<EFBFBD><C2B7><EFBFBD>Ϻ<EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
size_t blackCount = 0;
Node* cur = _root;
while (cur)
{
if (cur->_colour == BLACK)
{
blackCount++;
}
cur = cur->_left;
}
// <20>ж<EFBFBD><D0B6>Ƿ<EFBFBD><C7B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, k <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>¼·<C2BC><C2B7><EFBFBD>к<EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD><DAB5>ĸ<EFBFBD><C4B8><EFBFBD>
size_t k = 0;
return _IsRBTree(_root, k, blackCount);
}
bool _IsRBTree(Node* root, size_t k, size_t blackCount)
{
// <20>ߵ<EFBFBD> nullptr ֮<><D6AE>, <20>ж<EFBFBD> k <20><> blackCount <20>Ƿ<EFBFBD><C7B7><EFBFBD><EFBFBD><EFBFBD>
if (root == nullptr)
{
// <20><><EFBFBD>պ<EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>
if (blackCount != k)
{
std::cout << "Υ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ÿ<><C3BF>·<EFBFBD><C2B7><EFBFBD>к<EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD><DAB5>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>" << std::endl;
return false;
}
return true;
}
// ͳ<>ƺ<EFBFBD>ɫ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>
if (root->_colour == BLACK)
{
k++;
}
// <20><><EFBFBD>⵱ǰ<E2B5B1>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD>丸<EFBFBD>׽ڵ<D7BD><DAB5>Ƿ<EFBFBD><C7B7><EFBFBD>Ϊ<EFBFBD><CEAA>ɫ
Node* parent = root->_parent;
if (parent && parent->_colour == RED && root->_colour == RED)
{
std::cout << "Υ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: <20><>ɫ<EFBFBD>ڵ<EFBFBD><DAB5>ĺ<EFBFBD><C4BA>ӱ<EFBFBD><D3B1><EFBFBD><EFBFBD>Ǻ<EFBFBD>ɫ" << std::endl;
return false;
}
return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
}
private:
Node* _root;
};
}
Reference in New Issue Copy Permalink