手写了一个红黑树插入节点
主要参考了以下两位博主的写法
#include<iostream>
using namespace std;typedef enum { RED = 0, BLACK } Color;
struct RBTreeNode {int key;Color color;struct RBTreeNode* left; //左孩子struct RBTreeNode* right; //右孩子struct RBTreeNode* parent; //父节点//RBTreeNode(int _key):key(_key),color(RED),left(nullptr),right(nullptr),parent(nullptr){}
};
class RBTree
{
private:RBTreeNode * root;RBTreeNode * Nil;
public:RBTree();~RBTree();RBTreeNode* createNode(int key);void destroyRBTree(RBTreeNode* root);RBTreeNode* searchNode(int key); //查找keyRBTreeNode* searchMiniNode(RBTreeNode * p);RBTreeNode* searchMaxiNode(RBTreeNode * p);RBTreeNode* searchPredecessorNode(RBTreeNode * p);RBTreeNode* searchSuccessorNode(RBTreeNode * p);void InOrderTravel() { InOrderTravel(root); }void InOrderTravel(RBTreeNode * p);void InOrderTravelPrint() { InOrderTravelPrint(root); }//中序遍历打印void InOrderTravelPrint(RBTreeNode * p);void leftRotate(RBTreeNode * node);void rightRotate(RBTreeNode * node);void insertNodeAdjust(RBTreeNode * node);void insertNode(RBTreeNode *node);bool insertKey(int key);
};
//构造函数
RBTree::RBTree()
{Nil = new RBTreeNode;Nil->color = BLACK;Nil->parent = nullptr;Nil->left = nullptr;Nil->right = nullptr;root = Nil;//cout << " create Nil and root for RBtree successfully" << endl;
}
//析构函数
RBTree::~RBTree() {destroyRBTree(root); //销毁创建的非Nil结点delete Nil; //最后删除Nil结点Nil = NULL;
}//新建节点
RBTreeNode* RBTree::createNode(int key)
{RBTreeNode *p = new RBTreeNode;p->key = key;p->left = Nil;p->right = Nil;p->parent = Nil;p->color = RED;return p;
}
//析构函数 删除红黑树的所有节点
void RBTree::destroyRBTree(RBTreeNode* root) {if (root == Nil){return;}if (root->left != Nil){destroyRBTree(root->left);}if (root->right != Nil){destroyRBTree(root->right);}delete root;root = NULL;
}
//根据key值查找红黑树上的节点 如果不存在就返回Nil这个节点
RBTreeNode* RBTree::searchNode(int key) {RBTreeNode *p = root;while (p != Nil and p->key != key) {if (key < p->key)p = p->left;elsep = p->right;}return p;
}
//找指定p节点下左子树中的最小值
RBTreeNode * RBTree::searchMiniNode(RBTreeNode * p) {if (p == Nil) return Nil;while (p->left != Nil)p = p->left;return p;
}
//找指定p节点下右子树中的最大值
RBTreeNode * RBTree::searchMaxiNode(RBTreeNode * p) {if (p == Nil) return Nil;while (p->right != Nil)p = p->right;return p;
}//中序遍历实现函数
void RBTree::InOrderTravel(RBTreeNode * p) {if (p != Nil) {InOrderTravel(p->left);cout << p->key << " ";InOrderTravel(p->right);}
}
void RBTree::InOrderTravelPrint(RBTreeNode * p) {if (p == Nil) return;if (p->left != nullptr)InOrderTravelPrint(p->left);cout << p->key << "(" << ((p->color == BLACK) ? "BLACK" : "RED") << ")" << " ";if (p->right != nullptr)InOrderTravelPrint(p->right);
}//查找前继节点
RBTreeNode * RBTree::searchPredecessorNode(RBTreeNode * p) {if (p == Nil) return Nil;if (p->left != Nil)return searchMaxiNode(p->left);else {RBTreeNode * father = p->parent;while (father != Nil and father->left == p) {p = father;father = father->parent;}return father;}
}
//查找后继节点
RBTreeNode * RBTree::searchSuccessorNode(RBTreeNode * p) {if (p == Nil) return Nil;if (p->right != Nil)return searchMaxiNode(p->right);else {RBTreeNode * father = p->parent;while (father != Nil and father->right == p) {p = father;father = father->parent;}return father;}
}void RBTree::leftRotate(RBTreeNode * node) {RBTreeNode *rotateNode = node->right; //旋转点node->right = rotateNode->left;if (rotateNode->left != Nil) {rotateNode->left->parent = node;}rotateNode->parent = node->parent;if (node == root) {root = rotateNode;}else if (node == node->parent->left) {node->parent->left = rotateNode;}else {node->parent->right = rotateNode;}rotateNode->left = node;node->parent = rotateNode;
}
//对node 进行右旋转
void RBTree::rightRotate(RBTreeNode * node) {RBTreeNode *rotateNode = node->left; //旋转点node->left = rotateNode->right;if (rotateNode->right != Nil) {rotateNode->right->parent = node;}rotateNode->parent = node->parent;if (node == root) {root = rotateNode;}else if (node == node->parent->left) {node->parent->left = rotateNode;}else {node->parent->right = rotateNode;}rotateNode->right = node;node->parent = rotateNode;
}
//插入节点调整
void RBTree::insertNodeAdjust(RBTreeNode * node) {RBTreeNode *uncle;//叔节点while (node->parent->color == RED) //node 父节点的颜色为红色{if (node->parent == node->parent->parent->left) { //父亲节点作为祖父节点的左节点uncle = node->parent->parent->right; //叔节点if (uncle->color == RED) { //叔节点为红色uncle->color = BLACK; //叔节点变黑node->parent->color = BLACK; //父节点变黑node->parent->parent->color = RED; //祖父节点变红node = node->parent->parent; //node 指向祖父节点}else { //没有叔节点 或者叔节点为黑if (node == node->parent->right) { //父节点为红 叔节点为黑 且当前节点为父节点的右子树 左旋node = node->parent; //先将node指向父亲节点leftRotate(node); //左旋}//如果调整的结点在左结点,将node的父节点变为黑色，将祖父的结点变为红色，将node的祖父结点右转node->parent->color = BLACK;node->parent->parent->color = RED;rightRotate(node->parent->parent);}}else if (node->parent == node->parent->parent->right) {uncle = node->parent->parent->left; //叔节点if (uncle->color == RED) { //叔节点为红色uncle->color = BLACK; //叔节点变黑node->parent->color = BLACK; //父节点变黑node->parent->parent->color = RED; //祖父节点变红node = node->parent->parent; //node 指向祖父节点}else {if (node == node->parent->left) {node = node->parent;rightRotate(node);}node->parent->color = BLACK;node->parent->parent->color = RED;leftRotate(node->parent->parent);}}}root->color = BLACK;
}void RBTree::insertNode(RBTreeNode * node) {RBTreeNode* s = root; //用来指向当前节点RBTreeNode* fatherNode = Nil; //用来保存指向当前节点的父节点while (s != Nil) {fatherNode = s;if (node->key < s->key) s = s->left;else s = s->right;}node->parent = fatherNode; //node的父节点设置为if (fatherNode == Nil) { //如果root本身就为nil节点root = node;}else {if (node->key < fatherNode->key) {fatherNode->left = node;}else {fatherNode->right = node;}}insertNodeAdjust(node); //插入节点调整
}
bool RBTree::insertKey(int key) {//先搜索判断这个key在不在红黑树中RBTreeNode *node = searchNode(key);if (node != Nil)return false;node = createNode(key);insertNode(node);return true;
}int main() {RBTree rb = RBTree();int a[10] = { 4,1,7,8,9,3,2,11,18 };for (int i = 0; i < 10; i++) {rb.insertKey(a[i]);cout << a[i] << " ";}cout << endl;rb.InOrderTravel();cout << endl;rb.InOrderTravelPrint();cin.get();return 0;
}