更多文章见C++面试题系列
产生背景:
红黑树解决了平衡二叉树为了重新维持平衡旋转成本太高的问题.
平衡二叉树又称AVLTree,平衡二叉树最大的作用是查找,因为AVL树的查找,插入和删除在平均和最坏情况小都是O(logn)?
红黑树与AVL树比较:
1.插入删除操作,红黑树更容易控制;
2.旋转操作,调整平衡时红黑树的旋转次数更少.
红黑树性质和定义:
红黑树(Red-Black Tree)又称RB Tree,它是一个二叉查找树(二叉搜索树)?,每个节点包含一个存储为来表示节点的颜色,节点的颜色可以是红色或者黑色.一棵红黑树具有如下性质:
1.每个节点的颜色不是红色就是黑色
2.根节点的颜色是黑色
3.叶子节点(NULL)的颜色是黑色
4.每个红色节点,它的子节点必须是黑色
5.一个节点到该节点所有子孙节点的路径包含相同的黑色节点数,该性质保证最大路径长度不会超过最小路径长度的2倍,从而保证红黑树是一颗近似平衡二叉树.
定义红黑树节点:
enum RBTColor{RED, BLACK};template <class T>class RBTNode {public:RBTColor color;T key;RBTNode *left;RBTNode *right;RBTNode *parent;RBTNode(T val, RBTColor col, RBTNode *p, RBTNode *l,RBTNode *r):key(val),color(col),parent(p),left(l),right(r){}};
红黑树操作:
1.左旋和右旋
对红黑树进行插入或删除操作后,该红黑树可能不再满足红黑树的5个基本性质,为了保持红黑树的特性,需要对该树进行旋转操作.
常见的旋转操作包括:左旋和右旋.
1.左旋
对x节点进行左旋,就是让X节点旋转后成为一个左孩子,成为它右孩子的左孩子.
下面再看1个例子:
例子1:
总结,左旋操作可以分三步走:
（1）移动y的左孩子，y的左孩子移动为X的右孩子。X的右孩子指向y的左孩子,y的左孩子的父节点指向X.
（2）移动y节点，y的父节点指向X的父节点，如果X不是根节点，X父节点的左孩子或右孩子指向Y.。如果X是根节点则，y设置为根节点
（3）移动X节点，y节点的左孩子指向X，X的父节点指向Y.
实现代码:
/** 对红黑树的节点(x)进行左旋转** 左旋示意图(对节点x进行左旋)：*pxpx*/ /* x y* / \--(左旋)--> / \#* lx yx ry*/ \ / \* ly ry lx ly***/template<class T>void CMyRBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x){//定义一个指针y,指向x的右孩子;RBTNode<T> *y = x->right;//1.将"y的左孩子"设为"X的右孩子"x->right = y->left;if (y->left != nullptr){y->left->parent = x;}//2.将"X的父节点"设为"Y的父节点"y->parent = x->parent;if (x->parent == nullptr){root = y;}else{if (x->parent->left == x){x->parent->left = y;}else {x->parent->right = y;}}//3.将x作为y的左孩子y->left = x;x->parent = y;}
2.右旋
假设右旋节点为y,y的左孩子为x。右旋就是让y成为它的左孩子的有孩子
1.移动y节点的左孩子的右孩子，这里是beta,beta变为y节点的左孩子
2.移动y节点的左孩子，这里是X,X的父亲节点指向y的父亲节点
如果y的父亲节点为空，则root==x
如果y->parent->left==y,则y->parent->left=x;
如果y->parent->right==y,则y->parent->right=x
3.移动y节点，y->parent=x;x->right=y;
/* * 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)：* py py* / /*y x * / \--(右旋)--> / \ #* x ry lx y * / \/ \ #*lx rx rx ry* */template <class T>void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y){// 设置x是当前节点的左孩子。RBTNode<T> *x = y->left;// 将 “x的右孩子” 设为 “y的左孩子”；// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”y->left = x->right;if (x->right != NULL)x->right->parent = y;// 将 “y的父亲” 设为 “x的父亲”x->parent = y->parent;if (y->parent == NULL) {root = x; // 如果 “y的父亲” 是空节点，则将x设为根节点}else{if (y == y->parent->right)y->parent->right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”elsey->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”}// 将 “y” 设为 “x的右孩子”x->right = y;// 将 “y的父节点” 设为 “x”y->parent = x;}
牛客网：C++校招面试题合集
269：请问红黑树了解吗
270：请你说一说红黑树的性质还有左右旋转
271：请你说一说红黑树的原理以及erase以后迭代器的具体分布情况？
/topics/350253651/
参考文献：
红黑树原理
红黑树C++实现
附件:源代码
.h
#pragma onceenum RBTColor{RED, BLACK};template <class T>class RBTNode {public:RBTColor color;T key;RBTNode *left;RBTNode *right;RBTNode *parent;RBTNode(T val, RBTColor col, RBTNode *p, RBTNode *l,RBTNode *r):key(val),color(col),parent(p),left(l),right(r){}};template <class T>class CMyRBTree{private://跟节点RBTNode<T> *mRoot;public:CMyRBTree();~CMyRBTree();// 前序遍历"红黑树"void preOrder();// 中序遍历"红黑树"void inOrder();// 后序遍历"红黑树"void postOrder();// (递归实现)查找"红黑树"中键值为key的节点RBTNode<T>* search(T key);// (非递归实现)查找"红黑树"中键值为key的节点RBTNode<T>* iterativeSearch(T key);// 查找最小结点：返回最小结点的键值。T minimum();// 查找最大结点：返回最大结点的键值。T maximum();// 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。RBTNode<T>* successor(RBTNode<T> *x);// 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。RBTNode<T>* predecessor(RBTNode<T> *x);// 将结点(key为节点键值)插入到红黑树中void insert(T key);// 删除结点(key为节点键值)void remove(T key);// 销毁红黑树void destroy();// 打印红黑树void print();private:// 前序遍历"红黑树"void preOrder(RBTNode<T>* tree) const;// 中序遍历"红黑树"void inOrder(RBTNode<T>* tree) const;// 后序遍历"红黑树"void postOrder(RBTNode<T>* tree) const;// (递归实现)查找"红黑树x"中键值为key的节点RBTNode<T>* search(RBTNode<T>* x, T key) const;// (非递归实现)查找"红黑树x"中键值为key的节点RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;// 查找最小结点：返回tree为根结点的红黑树的最小结点。RBTNode<T>* minimum(RBTNode<T>* tree);// 查找最大结点：返回tree为根结点的红黑树的最大结点。RBTNode<T>* maximum(RBTNode<T>* tree);// 左旋void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);// 右旋void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);// 插入函数void insert(RBTNode<T>* &root, RBTNode<T>* node);// 插入修正函数void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);// 删除函数void remove(RBTNode<T>* &root, RBTNode<T> *node);// 删除修正函数void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);// 销毁红黑树void destroy(RBTNode<T>* &tree);// 打印红黑树void print(RBTNode<T>* tree, T key, int direction);#define rb_parent(r) ((r)->parent)#define rb_color(r) ((r)->color)#define rb_is_red(r) ((r)->color==RED)#define rb_is_black(r) ((r)->color==BLACK)#define rb_set_black(r) do { (r)->color = BLACK;}while(0)#define rb_set_red(r) do { (r)->color = RED; } while (0)#define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)#define rb_set_color(r,c) do { (r)->color = (c); } while (0)};
.cpp
#include "stdafx.h"#include "MyRBTree.h"template<class T>CMyRBTree<T>::CMyRBTree(){}template<class T>CMyRBTree<T>::~CMyRBTree(){}/** 对红黑树的节点(x)进行左旋转** 左旋示意图(对节点x进行左旋)：*pxpx*/ /* x y* / \--(左旋)--> / \#* lx yx ry*/ \ / \* ly ry lx ly***/template<class T>void CMyRBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x){//定义一个指针y,指向x的右孩子;RBTNode<T> *y = x->right;//将"y的左孩子"设为"X的右孩子"x->right = y->left;if (y->left != nullptr){y->left->parent = x;}//将"X的父节点"设为"Y的父节点"y->parent = x->parent;if (x->parent == nullptr){root = y;}else{if (x->parent->left == x){x->parent->left = y;}else {x->parent->right = y;}}y->left = x;x->parent = y;}/** 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)：* py py* / /*y x* / \--(右旋)--> / \ #* x ry lx y* / \/ \ #*lx rx rx ry**/template<class T>void CMyRBTree<T>::rightRotate(RBTNode<T>*& root, RBTNode<T>* y){//定义一个指针,指向Y的左孩子RBTNode *x = y->left;//1.X的右孩子设置为y的左孩子y->left = x->right;if (x->right != nullptr){x->right->parent = y;}//2.y的父亲节点设置为X的父亲节点x->parent = y->parent;if (y->parent == nullptr){root = x;}else {if (y->parent->left == y){y->parent->left = x;}else {y->parent->right = x;}}x->right = y;y->parent = x;}
参考文献
/skywang12345/archive//01/13/3245399.html
