自平衡二叉树 (2) -- 红黑树
红黑树
定义:
摘自wiki
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。
红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了O(logn)的时间之外，红黑树的持久版本对每次插入或删除需要O(logn)的空间。
红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。
红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
简而言之:
对于完全随机的数据(数据量不是很大),普通的二分搜索树很好用
缺点：极端情况退化为链表（或者高度不平衡）
对于查询较多的使用情况，AVL树很好用
红黑树牺牲了平衡性(最大高度为2logn的高度)
统计性能更优(综合增删改查所有的操作)
另一种统计性能优秀的树SplayTree (伸展树)
局部性原理:刚被访问的内容下次高概率被再次访问
性质
- 每个节点都是红色或者黑色
- 根节点是黑色的
- 每一个叶子节点（最后的空节点）是黑色的
- 如果一个节点是红色的,那么他的孩子节点都是黑色的.
- 从任意一个节点到叶子节点，经过的黑色节点都是一样的(黑平衡)
从2-3树类比到红黑树
PS
图中实现的红黑树是一种特殊的红黑树——左倾红黑树,同时图中的红黑树并没有经过相应的优化,并不能像算法导论中所说任何不平衡都能在三次旋转内解决。
代码实现
//RBTree.hpp
# include <iostream>
# include <string>
# include <stack>
# include <queue>
# include <time.h>
using namespace std;
template <typename K, typename V> class BST;
template <class K, class V>
class RBTree
{
private:
const static bool RED =true ;
const static bool BLACK = false;
template <class K, class V>
class Node {
public:
Node(K key, V value)
{
this->key = key;
this->value = value;
height = 1; //初始为叶子节点
left = NULL;
right = NULL;
color = RED;//1
}
public:
bool color;
K key;
V value;
Node<K, V>* left;
Node<K, V>* right;
int height;
};
public:
RBTree()
{
root = NULL;
size = 0;
}
inline int Size()
{
return size;
}
V get(K key)
{
V ret = getNode(root, key)->value;
return ret;
}
void add(K key, V value) //向RBT添加新的元素 key ,value
{
root = add(root, key, value);
root->color = BLACK;
}
bool contains(K e)
{
return contains(root, e);
}
void preOrder()
{
preOrder(root);
}
void preOrderNR()
{
stack<Node<K, V>*> stack;
stack.push(root);
while (!stack.empty())
{
Node<K, V>* cur = stack.top();;
stack.pop();
cout << cur->key << " ";
if (cur->left != NULL)
stack.push(cur->left);
if (cur->right != NULL)
stack.push(cur->right);
}
}
void inOrder()
{
inOrder(root);
}
void postOrder() //应用:内存释放方面,先将孩子节点的内存都释放干净，再释放根节点
{
postOrder(root);
}
//层次遍历(广度优先遍历)
void levelOrder()
{
queue<Node<K, V>*> q;
q.push(root);
while (!q.empty())
{
Node<K, V>* cur = q.front();
q.pop();
cout << cur->key << " ";
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
q.push(cur->right);
}
}
K minElement()
{
if (!size)
throw "BST is empty";
return minElement(root)->key;
}
K maxElement()
{
if (!size)
throw "BST is empty";
maxElement(root)->key;
}
string toString()
{
string val;
generateBSTString(root, 0, val);
return val;
}
K removeMin()
{
K val = minElement();
root = removeMin(root);
return val;
}
K removeMax()
{
K val = maxElement();
root = removeMax(root);
return val;
}
void remove(K val)
{
root = remove(root, val);
}
bool isBST()
{
vector<K> keys;
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++)
{
if (keys[i] < keys[i - 1])
return false;
}
return true;
}
private:
bool isRed(Node<K, V>* node) { return node!=NULL&&node->color==RED; }
Node<K, V>* getNode(Node<K, V>* node, K key)
{
if (node == NULL)
return NULL;
if (key < node->key)
return getNode(node->left, key);
else if (key > node->key)
return getNode(node->right, key);
else
return node;
}
Node<K,V>* leftRotate(Node<K,V>* node)
{
Node<K, V>* x = node->right;
node->right = x->left;
x->left = node;
x->color = node->color;
node->color = RED;
return x;
}
Node<K, V>* rightRotate(Node<K, V>* node)
{
Node<K, V>* x = node->left;
node->left = x->right;
x->right = node;
x->color = node->color;
node->color = RED;
return x;
}
//颜色翻转
void flipColors(Node<K, V>* node)
{
node->color = RED;
node->left->color = BLACK;
node->right->color = BLACK;
}
Node<K, V>* add(Node<K, V>* node, K key, V value)
{
if (node == NULL)
{
size++;
return new Node<K, V>(key, value);
}
if (key < node->key)
node->left = add(node->left, key, value);
else if (key > node->key)
node->right = add(node->right, key, value);
else
node->value = 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;
}
bool contains(Node<K, V>* node, K e)
{
if (node == NULL)
return false;
if (node->key == e)
return true;
else if (e< node->key )
return contains(node->left, e);
else
return contains(node->right, e);
}
void preOrder(Node<K, V>* node)
{
if (node == NULL)
return;
cout << node->key << " ";
preOrder(node->left);
preOrder(node->right);
}
void inOrder(Node<K, V>* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->key << " ";
inOrder(node->right);
}
void inOrder(Node<K, V>* node, vector<K>& keys)
{
if (node == NULL)
return;
inOrder(node->left, keys);
keys.push_back(node->key);
inOrder(node->right, keys);
}
void postOrder(Node<K, V>* node)
{
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
cout << node->key << " ";
}
//打印输出函数
void generateBSTString(Node<K, V>* node, int depth, string& str)
{
if (node == NULL)
{
str += generateDepthString(depth) + "null\n";
return;
}
str = str + generateDepthString(depth) + to_string(node->key) + "\n";
generateBSTString(node->left, depth + 1, str);
generateBSTString(node->right, depth + 1, str);
}
string generateDepthString(int depth)
{
string str;
for (int i = 0; i < depth; i++)
str += "--";
return str;
}
Node<K, V>* minElement(Node<K, V>* node)
{
if (node->left == NULL)
return node;
return minElement(node->left);
}
Node<K, V>* maxElement(Node<K, V>* node)
{
if (node->right == NULL)
return node;
return minElement(node->right);
}
//删除以node为根的二分搜索树中的最小节点
//返回删除节点后新的二分搜索树的根
Node<K, V>* removeMin(Node<K, V>* node)
{
if (node->left == NULL)
{
Node<K, V>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
Node<K, V>* removeMax(Node<K, V>* node)
{
if (node->right == NULL) //当前节点为最大值
{
Node* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
//任意删除节点
Node<K, V>* remove(Node<K, V>* node, K e)
{
if (node == NULL)
return NULL;
if (e < node->key)
{
node->left = remove(node->left, e);
return node;
}
else if (e > node->key)
{
node->right = remove(node->right, e);
return node;
}
else
{
if (node->left == NULL)
{
Node<K, V>* rightNode = node->right;
node->right = NULL;
delete node;
node = NULL;
size--;
return rightNode;
}
if (node->right == NULL)
{
Node<K, V>* leftNode = node->left;
node->left = NULL;
delete node;
node = NULL;
size--;
return leftNode;
} //有两个孩子节点且都不为空
Node<K, V>* successor = new Node<K, V>(*minElement(node->right));
successor->right = removeMin(node->right);
successor->left = node->left;
node->left = NULL;
node->right = NULL;
delete node;
node = NULL;
return successor;
}
}
private:
Node<K, V>* root;
int size;
};
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment
