2-3树
为了维护2-3树绝对平衡的性质，插入结点时就要符合一下逻辑：
- 添加结点不能添加到空位置，除非此时整个树为空。
- 如果按照二分搜索树的方式插入元素，如果插入位置为空，此时和最后找到的那个叶子节点融合。
红黑树
添加
左旋转
颜色翻转
右旋转
性能
#pragma once
template
class RBTree {
private:
static const bool RED = true;
static const bool BLACK = false;
struct Node {
Key key;
Value value;
Node *left;
Node *right;
bool color;
Node(Key key, Value value) {
this->key = key;
this->value = value;
this->left = this->right = nullptr;
color = RED;
}
Node(Node *node) {
this->key = node->key;
this->value = node->value;
this->left = node->left;
this->right = node->right;
this->color = node->color;
}
};
Node *root;
int size;
public:
RBTree() : root(nullptr), size(0) {}
~RBTree() {
destroy(root);
}
int getSize() const {
return size;
}
int isEmpty() const {
return size == 0;
}
bool isRed(Node *node) {
if (node == nullptr) {
return BLACK;
}
return node->color;
}
void add(Key key, Value value) {
root = add(root, key, value);
root->color = BLACK;
}
bool contains(Key key) {
return getNode(root, key) != nullptr;
}
Value *get(Key key) {
Node *node = getNode(root, key);
return node == nullptr ? nullptr : &(node->value);
}
void set(Key key, Value newValue) {
Node *node = getNode(root, key);
if (node != nullptr) {
node->value = newValue;
}
}
private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node *add(Node *node, Key key, Value value) {
if (node == nullptr) {
size++;
return new Node(key, value);
}
if (key == node->key) {
node->value = value;
} else if (key < node->key) {
node->left = add(node->left, key, value);
} else {
node->right = add(node->right, key, value);
}
if (isRed(node->right) && !isRed(node->left)) {
node = leftRotate(node);
}
if (isRed(node->left) && isRed(node->left->left)) {
node = rightRotate(node);
}
if (isRed(node->left) && isRed(node->right)) {
flipColors(node);
}
return node;
}
// 在以node为根的二叉搜索树中查找key所对应的Node
Node *getNode(Node *node, Key key) {
if (node == nullptr) {
return nullptr;
}
if (key == node->key) {
return node;
} else if (key < node->key) {
return getNode(node->left, key);
} else {
return getNode(node->right, key);
}
}
void destroy(Node *node) {
if (node != nullptr) {
destroy(node->left);
destroy(node->right);
delete node;
size--;
}
}
Node *leftRotate(Node *node) {
Node *x = node->right;
node->right = x->left;
x->left = node;
x->color = node->color;
node->color = RED;
return x;
}
Node *rightRotate(Node *node) {
Node *x = node->left;
node->left = x->right;
x->right = node;
x->color = node->color;
node->color = RED;
return x;
}
void flipColors(Node *node) {
node->color = RED;
node->left->color = BLACK;
node->right->color = BLACK;
}
};
Original: https://www.cnblogs.com/chengmf/p/16475207.html
Author: 放飞梦想C
Title: 2-3树/红黑树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588196/
转载文章受原作者版权保护。转载请注明原作者出处！