自顶向下红黑树的详细介绍见数据结构与算法分析java语言描述第三版 Weiss著这里只给出实现#include iostream #include algorithm #include vector #include stack #include random #include ctime #include string using namespace std; //自顶向下插入和删除算法的说明见数据结构与算法分析java语言描述第三版 Weiss著 enum ColorFlag { RED, BLACK }; template typename T struct RBTreeNode { T data; //节点数据域 ColorFlag color; //节点颜色 RBTreeNode* left; RBTreeNode* right; RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {} }; template typename T RBTreeNodeT* RotateLR(RBTreeNodeT* ptr) //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; RBTreeNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; return q; } template typename T RBTreeNodeT* RotateRL(RBTreeNodeT* ptr) //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; RBTreeNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; return q; } template typename T RBTreeNodeT* RotateR(RBTreeNodeT* ptr) //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; ptr-left p-right; p-right ptr; return p; } template typename T RBTreeNodeT* RotateL(RBTreeNodeT* ptr) //对以ptr为根的子树执行左单旋转, ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; ptr-right p-left; p-left ptr; return p; } void printNULL(size_t num) { for (size_t o 1; o num; o) cout ; cout NULL endl; } template typename T void printRBTree(RBTreeNodeT* root, size_t offset) { if (root nullptr) cout NULL空树 endl;; for (int i 1; i offset; i) cout ; string s to_string(root-data); offset s.size() 2; cout s :; if (root-color ColorFlag::RED) cout R; else cout B; cout endl; if (root-left nullptr) { if (root-right ! nullptr) { printNULL(offset); printRBTree(root-right, offset); } } else { printRBTree(root-left, offset); if (root-right nullptr) { printNULL(offset); } else printRBTree(root-right, offset); } }; template typename T int Searchd(RBTreeNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T void output(RBTreeNodeT* ptr) //输出以ptr为根的红黑树对应的广义表形式 { struct memory { RBTreeNodeT* p; int direction; int last; memory(RBTreeNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; int d 0; RBTreeNodeT* const dest ptr; stackmemory arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data; arrange.top().last 1; } else { cout , ptr-data; arrange.top().last 2; } } else { cout ,; cout ptr-data; arrange.top().last 2; } } else { if (arrange.top().last 2) cout ); else { cout , ); } arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { RBTreeNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data (; arrange.top().last 1; } else { cout , ptr-data (; arrange.top().last 2; } } else { cout ,; cout ptr-data (; arrange.top().last 2; } } else { cout ptr-data (; } arrange.push(memory(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) interval ptr-left; else interval ptr-right; } else { arrange.top().direction 2; interval ptr-right; } d 0; ptr interval; } } } bool examineBlackHeight(bool TF, int preroadblacknum, const int blacknum) { if (TF false) { TF true; preroadblacknum blacknum; } else { if (preroadblacknum ! blacknum) { cout 从根节点到外节点的路径上黑节点数目不等,非红黑树 endl; return false; } } return true; } template typename T void addBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) blacknum; } template typename T void reduceBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) --blacknum; } template typename T bool isRB(RBTreeNodeT* root) //判断以root为根的二叉树是否为红黑树(已假定节点颜色不是为红色就是为黑色) { if (root-color ColorFlag::RED) { cout 根节点不为黑色,非红黑树 endl; return false; } struct memory { RBTreeNodeT* p; int direction; T lmin; memory(RBTreeNodeT* p, int d) :p(p), direction(d) {} }; T lmax; T rmin; T rmax; int d 0; RBTreeNodeT* ptr root; RBTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int blacknum 0; //统计路径上黑节点个数的变量 int preroadblacknum 0; //当前路径的前一路径上黑节点数目 while (true) { int result; if ((result Searchd(ptr, d)) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { addBlackNum(ptr, blacknum); if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax ptr-data; } else { rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax ptr-data; } else { rmin lmin; rmax ptr-data; } } else { if (rmin ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; } else rmin ptr-data; } else { T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax rmax; } else rmin lmin; } } } reduceBlackNum(ptr, blacknum); ptr arrange.top().p; d arrange.top().direction; } else { RBTreeNodeT* interval nullptr; if (d 0) { if (ptr-color ColorFlag::RED) { if (result 2) { if (ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } else { if (ptr-left-color ColorFlag::RED || ptr-right ! nullptr ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } } else blacknum; if (ptr-left nullptr || ptr-right nullptr) { if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; } arrange.push(memory(ptr, result)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void link(RBTreeNodeT* parent, RBTreeNodeT* cur, RBTreeNodeT* original) { if (parent-left original) parent-left cur; else parent-right cur; } template typename T void linkAfterRotate(RBTreeNodeT* parent, RBTreeNodeT* cur, RBTreeNodeT* root, RBTreeNodeT* original) //旋转后和上层重新链接 { if (parent ! nullptr) { link(parent, cur, original); } else root cur; } template typename T bool adjust(RBTreeNodeT* cur, RBTreeNodeT* p, RBTreeNodeT* pp, RBTreeNodeT* ppp, RBTreeNodeT* root, bool LL_OR_RR) { bool flag; pp-color ColorFlag::RED; if (p pp-left) { if (cur p-left) { flag false; p-color ColorFlag::BLACK; RotateR(pp); } else { flag true; cur-color ColorFlag::BLACK; if (LL_OR_RR) cur p; else cur pp; p RotateLR(pp); } } else { if (cur p-left) { flag true; cur-color ColorFlag::BLACK; if (LL_OR_RR) cur pp; else cur p; p RotateRL(pp); } else { flag false; p-color ColorFlag::BLACK; RotateL(pp); } } linkAfterRotate(ppp, p, root, pp); return flag; } template typename T bool insertInRBTree(RBTreeNodeT* root, T key) { if (root nullptr) { root new RBTreeNodeT(key, ColorFlag::BLACK); return true; } RBTreeNodeT* cur root; RBTreeNodeT* p nullptr; RBTreeNodeT* pp nullptr; RBTreeNodeT* ppp nullptr; bool f; bool LL_OR_RR; while (true) { if (cur-data key) { root-color ColorFlag::BLACK; return false; } else { if (key cur-data) { LL_OR_RR true; if (cur-left nullptr) f true; else f false; } else { LL_OR_RR false; if (cur-right nullptr) f true; else f false; } if (f) { (LL_OR_RR ? cur-left : cur-right) new RBTreeNodeT(key, ColorFlag::RED); if (cur-color ColorFlag::RED) { RBTreeNodeT* t (LL_OR_RR ? cur-left : cur-right); adjust(t, cur, p, pp, root, LL_OR_RR); } root-color ColorFlag::BLACK; return true; } if (cur-left ! nullptr cur-left-color ColorFlag::RED cur-right ! nullptr cur-right-color ColorFlag::RED) { cur-left-color ColorFlag::BLACK; cur-right-color ColorFlag::BLACK; cur-color ColorFlag::RED; if (p ! nullptr p-color ColorFlag::RED) { if (adjust(cur, p, pp, ppp, root, LL_OR_RR)) continue; } } ppp pp; pp p; p cur; cur (LL_OR_RR ? cur-left : cur-right); } } } template typename T bool replaceDeletedValue(RBTreeNodeT* root, bool left_or_right, T key) //用root左子树(右子树)最大值(最小值)替换root { RBTreeNodeT* p nullptr; RBTreeNodeT* f root; if (left_or_right) { p root-left; while (p-right ! nullptr) { f p; p p-right; } if (p-color ColorFlag::RED || p-left ! nullptr) { if (f root) f-left p-left; else f-right p-left; if (p-color ! ColorFlag::RED) p-left-color ColorFlag::BLACK; } } else { p root-right; while (p-left ! nullptr) { f p; p p-left; } if (p-color ColorFlag::RED || p-right ! nullptr) { if (f root) f-right p-right; else f-left p-right; if (p-color ! ColorFlag::RED) p-right-color ColorFlag::BLACK; } } root-data p-data; if (p-color ColorFlag::RED || (left_or_right ? p-left ! nullptr : p-right ! nullptr)) { delete p; return true; } key root-data; return false; } template typename T RBTreeNodeT* directDelete(RBTreeNodeT* cur, RBTreeNodeT* parent) { RBTreeNodeT* temp nullptr; if (cur-right nullptr) { temp cur-left; } else { temp cur-right; } if (parent ! nullptr) { link(parent, temp, cur); } temp-color ColorFlag::BLACK; delete cur; return temp; } template typename T bool DelInRBTree(RBTreeNodeT* root, T key) { if (root nullptr) { return false; } RBTreeNodeT* cur root; RBTreeNodeT* parent nullptr; RBTreeNodeT* down nullptr; if (root-data key) { if (root-left nullptr) { if (root-right nullptr) { delete root; root nullptr; return true; } root directDelete(root, static_castRBTreeNodeT*(nullptr)); return true; } else { if (root-left-color ! ColorFlag::BLACK || root-right-color ! ColorFlag::BLACK) { if (root-left-color ! ColorFlag::BLACK) { if (replaceDeletedValue(root, true, key)) return true; down root-left; } else { if (replaceDeletedValue(root, false, key)) return true; down root-right; } } } } else { if (key root-data) { down root-left; } else { down root-right; } if (down nullptr) return false; } if ((root-left nullptr || root-left-color ColorFlag::BLACK) (root-right nullptr || root-right-color ColorFlag::BLACK)) { root-color ColorFlag::RED; } else { if (down-color ColorFlag::RED) { parent cur; cur down; down nullptr; } else { if (down cur-left) { swap(cur-color, cur-right-color); parent RotateL(cur); } else { swap(cur-color, cur-left-color); parent RotateR(cur); } root parent; } } while (true) { if (cur-data key) { if (cur-left nullptr) { link(parent, static_castRBTreeNodeT*(nullptr), cur); delete cur; root-color ColorFlag::BLACK; return true; } if (replaceDeletedValue(cur, true, key)) { root-color ColorFlag::BLACK; return true; } down cur-left; } else { if (cur-left nullptr) { root-color ColorFlag::BLACK; return false; } if (down nullptr) { if (key cur-data) down cur-left; else down cur-right; } } if ((down-left nullptr || down-left-color ColorFlag::BLACK) (down-right nullptr || down-right-color ColorFlag::BLACK)) { RBTreeNodeT* p nullptr; if (down cur-left) p cur-right; else p cur-left; cur-color ColorFlag::BLACK; down-color ColorFlag::RED; if ((p-left nullptr || p-left-color ColorFlag::BLACK) (p-right nullptr || p-right-color ColorFlag::BLACK)) { p-color ColorFlag::RED; } else { if (down cur-left) { if (p-left ! nullptr p-left-color ColorFlag::RED) p RotateRL(cur); else { p-color ColorFlag::RED; p-right-color ColorFlag::BLACK; RotateL(cur); } } else { if (p-right ! nullptr p-right-color ColorFlag::RED) p RotateLR(cur); else { p-color ColorFlag::RED; p-left-color ColorFlag::BLACK; RotateR(cur); } } linkAfterRotate(parent, p, root, cur); } parent cur; cur down; } else { if (down-data key) { if (down-left ! nullptr down-left-color ColorFlag::RED) { if (down-right nullptr) { root-color ColorFlag::BLACK; directDelete(down, cur); return true; } if (replaceDeletedValue(down, true, key)) { root-color ColorFlag::BLACK; return true; } cur down-left; } else { if (down-left nullptr) { root-color ColorFlag::BLACK; directDelete(down, cur); return true; } if (replaceDeletedValue(down, false, key)) { root-color ColorFlag::BLACK; return true; } cur down-right; } } else { bool TF; if ((TF key down-data) down-left nullptr || !TF down-right nullptr) { root-color ColorFlag::BLACK; return false; } if (TF down-left-color ColorFlag::RED || !TF down-right-color ColorFlag::RED) { if (TF down-left-color ColorFlag::RED) { cur down-left; } else { cur down-right; } } else { parent cur; cur down; cur-color ColorFlag::RED; RBTreeNodeT* temp nullptr; if (TF) { down down-left; cur-right-color ColorFlag::BLACK; temp RotateL(cur); } else { down down-right; cur-left-color ColorFlag::BLACK; temp RotateR(cur); } linkAfterRotate(parent, temp, root, cur); parent temp; continue; } } parent down; } down nullptr; } } int main() { const int N 2000; vectorint insertvalue(N); for (int r 1; r N; r) { insertvalue[r - 1] r; //insertvalue.push_back(r); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); RBTreeNodeint* root nullptr; for (vectorint::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { int t *p; bool result insertInRBTree(root, t); cout 插入 *p endl; if (result) { cout 插入成功 endl; //output(root); //printRBTree(root, 0); } else { cout 插入失败 endl; //exit(0); } cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } cout endl; cout 插入完成后删除前红黑树对应的广义表形式为: endl; //output(root); //printRBTree(root, 0); cout endl; cout endl; for (vectorint::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { int t *p; cout 删除节点 *p endl; bool result DelInRBTree(root, t); if (result) { cout 删除成功 endl; if (root ! nullptr) { //output(root); //printRBTree(root, 0); cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } else cout NULL; cout endl; } else { cout 删除失败 endl; //exit(0); } } return 0; }