C++数据结构--红黑树

一.红黑树的基本结构基本性质1.与AVL树相同红黑树也是基于BST树的满足BST树的基本性质。2.每一个节点都是有颜色的红或者黑。3.root根节点必须是黑色的。4.所有叶子节点都必须是黑色的叶子节点是NULL节点并不存储实际数据。5.从根节点到叶子节点不能存在两个连续的红色节点。6.从任意节点到叶子节点的所有简单路径都必须包含相同数目的黑色节点。7.左右子树的高度差不能超过2倍关系。红黑树的基本结构templatetypename T class RbTree { public: RbTree() :root(nullptr) { } ~RbTree() {} private: enum Color { RED, BLACK }; struct Node { Node(T data T(), Node* left nullptr, Node* right nullptr, Color color BLACK, Node* parent nullptr) : m_data(data) , left(left) , right(right) , parent(parent) , color(color) { } T m_data; Node* left; Node* right; Node* parent; Color color; }; Node* root; };二.常见操作1.插入操作红黑树的插入操作会破坏红黑树的性质所有我们需要对其进行插入调整操作。1.如果原树为空直接插入插入节点的颜色为黑色。2.如果原树非空为了维护红黑树的性质我们选择插入红色节点检查插入元素的父节点父节点为黑色则直接插入如果父节点为红色进行插入调整插入调整的三种情况插入调整的第一步就是将祖先节点的颜色与其孩子节点交换但是这样祖先节点变成了红色可能与其另一个孩子节点相冲突所以我们需要关注祖先节点的另一个孩子节点即插入节点的叔叔节点。1如果叔叔节点为红色如图我们就需要将祖先节点的颜色与其孩子节点交换然后将叔叔节点置为黑色。2如果叔叔节点为黑色插入节点位于B节点的左孩子如图我们需要先将祖先节点的颜色与其孩子节点交换然后以A为轴进行右旋转3如果如果叔叔节点为黑色插入节点位于B节点的右孩子我们需要先以B节点为轴进行左旋转然后同情况2.注意所有插入调整都需要处理根节点可能在调整的过程中被变红的可能即都需要在调整结束后强制将根节点设置为黑色。插入操作代码实现//插入调整 void fixAfterinsert(Node* node) { while (getColor(node-parent) RED) { if (getLeft(getParent(getParent(node))) getParent(node)) { Node* uncle getParent(node-parent)-right; if (getColor(uncle) RED) { setColor(getParent(node-parent), RED); setColor(getParent(node), BLACK); setColor(uncle, BLACK); node getParent(node-parent); } else { if (getParent(node)-right node) { node getParent(node); leftRotate(node); } setColor(getParent(node-parent), RED); setColor(getParent(node), BLACK); rightRotate(getParent(node-parent)); break; } } else { Node* uncle getParent(node-parent)-left; if (getColor(uncle) RED) { setColor(getParent(node-parent), RED); setColor(getParent(node), BLACK); setColor(uncle, BLACK); node getParent(node-parent); } else { if (getParent(node)-left node) { node getParent(node); rightRotate(node); } setColor(getParent(node-parent), RED); setColor(getParent(node), BLACK); leftRotate(getParent(node-parent)); break; } } } setColor(root, BLACK); }2.旋转操作1右旋转//右旋转操作 void rightRotate(Node* node) { Node* child node-left; child-parent node-parent; if (node-parent nullptr) { root child; } else { if (node-parent-left node) { node-parent-left child; } else { node-parent-right child; } } node-left child-right; if (child-right ! nullptr) { child-right-parent node; } child-right node; node-parent child; }2左旋转//左旋转操作 void leftRotate(Node* node) { Node* child node-right; child-parent node-parent; if (node-parent nullptr) { root child; } else { if (node-parent-left node) { node-parent-left child; } else { node-parent-right child; } } node-right child-left; if (child-left ! nullptr) { child-left-parent node; } child-left node; node-parent child; }3.删除操作//删除调整 void fixAfterremove(Node* node) { while (getColor(node) BLACK) { if (getLeft(getParent(node)) node) { Node* brother getRight(getParent(node)); if (getColor(brother) RED) { setColor(brother, BLACK); setColor(getParent(node), RED); leftRotate(getParent(node)); brother getRight(getParent(node)); } if (getColor(getRight(brother)) BLACK getColor(getLeft(brother)) BLACK) { setColor(brother, RED); node getParent(node); } else { if (getColor(getRight(brother)) ! RED) { setColor(getLeft(brother), BLACK); setColor(brother, RED); rightRotate(brother); brother getRight(getParent(node)); } setColor(brother, getColor(getParent(node))); setColor(getParent(node), BLACK); setColor(getRight(brother), BLACK); leftRotate(getParent(node)); break; } } else { Node* brother getLeft(getParent(node)); if (getColor(brother) RED) { setColor(brother, BLACK); setColor(getParent(node), RED); rightRotate(getParent(node)); brother getLeft(getParent(node)); } if (getColor(getLeft(brother)) BLACK getColor(getRight(brother)) BLACK) { setColor(brother, RED); node getParent(node); } else { if (getColor(getLeft(brother)) ! RED) { setColor(getRight(brother), BLACK); setColor(brother, RED); leftRotate(brother); brother getLeft(getParent(node)); } setColor(brother, getColor(getParent(node))); setColor(getParent(node), BLACK); setColor(getLeft(brother), BLACK); rightRotate(getParent(node)); break; } } } setColor(node, BLACK); }