AA树为自平衡二叉搜索树为红黑树的变体。每个AA树节点有该节点所在层数相当于红黑树的黑高度以及一个垂直左链指针和右链指针右链指针可以为垂直也可以为水平,不允许出现两个连续的右链指针。以下AA树实现为笔者自己笔设计者没有看懂数据结构与算法分析Java语言描述第二版中对AA树skew和split操作的介绍于是干脆自行设计插入删除算法C代码如下:#include iostream #include stack #include vector #include random #include ctime using namespace std; template typename T struct AATreeNode { T data; int level 1; AATreeNode* left_child nullptr; AATreeNode* right_child nullptr; bool right_ptr_is_horizontal_chain false; AATreeNode(const T d) : data(d) {} }; template typename T struct AATreeInfo { bool isAATree; int height; T min; T max; }; template typename T class AATree { public: bool remove(const T key); bool insert(const T key); bool isAATree(); void printAATree(); ~AATree() { delete_tree(root); } private: void delete_tree(AATreeNodeT* root) { if (root ! nullptr) { delete_tree(root-left_child); delete_tree(root-right_child); delete root; } } void print(AATreeNodeT* root); AATreeInfoT checkAATree(AATreeNodeT* root); AATreeNodeT* root nullptr; }; template typename T void AATreeT::print(AATreeNodeT* root) { if (root-left_child ! nullptr) { cout ( root-data (; print(root-left_child); if (root-right_ptr_is_horizontal_chain) { cout ),; print(root-right_child); } else { cout ,; print(root-right_child); cout ); } cout ); } else { cout ( root-data; if (root-right_child ! nullptr) { cout , root-right_child-data; } cout ); } } template typename T void AATreeT::printAATree() { if (root nullptr) { cout NULL; } else { print(root); } cout endl; } template typename T AATreeInfoT AATreeT::checkAATree(AATreeNodeT* root) { AATreeInfoT result; if (root-left_child ! nullptr) { if (root-right_child ! nullptr) { if (root-right_ptr_is_horizontal_chain) { if (root-right_child-right_ptr_is_horizontal_chain) { result.isAATree false; return result; } } AATreeInfoT temp checkAATree(root-left_child); if (!temp.isAATree || temp.max root-data) { result.isAATree false; } else { result.height temp.height 1; result.min temp.min; temp checkAATree(root-right_child); if (!temp.isAATree || temp.min root-data || root-right_ptr_is_horizontal_chain result.height ! temp.height || root-right_ptr_is_horizontal_chain false result.height ! temp.height 1) { result.isAATree false; return result; } if (root-level ! result.height) { cout 节点 root-data level不正确应为 result.height; } result.max temp.max; result.isAATree true; } } else { result.isAATree false; } } else { if (root-right_child nullptr || root-right_ptr_is_horizontal_chain root-right_child-left_child nullptr root-right_child-right_child nullptr) { result.height 1; result.isAATree true; result.min root-data; if (root-level ! 1) { cout 节点 root-data level不正确应为1 endl; } if (root-right_child nullptr) { result.max root-data; } else { result.max root-right_child-data; if (root-right_child-level ! 1) { cout 节点 root-right_child-data level不正确应为1 endl; } } } else { result.isAATree false; } } return result; } template typename T bool AATreeT::isAATree() { if (root nullptr) { return true; } return checkAATree(root).isAATree; } template typename T AATreeNodeT* replace(AATreeNodeT* root, stackAATreeNodeT* work_stack) //调用函数时总是假定root为AATree分支节点故有两子女 { work_stack.push(root); AATreeNodeT* cur root-right_child; while (cur-left_child ! nullptr) { work_stack.push(cur); cur cur-left_child; } root-data cur-data; return cur; } template typename T void linkWithUpper(AATreeNodeT* original_link_point, AATreeNodeT* link_point, AATreeNodeT* parent) { if (original_link_point ! link_point) { if (parent-left_child original_link_point) { parent-left_child link_point; } else { parent-right_child link_point; } } } template typename T AATreeNodeT* processSituation5(AATreeNodeT* p); template typename T AATreeNodeT* processSituation1b(AATreeNodeT* cur, AATreeNodeT* p); template typename T //处理诸情形时不调整节点所在层次只修改指针和水平右链标志 AATreeNodeT* processSituation1(AATreeNodeT* cur, AATreeNodeT* p); template typename T void processSituation3(AATreeNodeT* p); template typename T bool AATreeT::remove(const T key) { if (root nullptr) { return false; } AATreeNodeT* cur root; stackAATreeNodeT* work_stack; while (cur ! nullptr) { if (cur-data key) { break; } work_stack.push(cur); if (key cur-data) { cur cur-left_child; } else { cur cur-right_child; } } if (cur nullptr) { return false; } if (work_stack.empty()) { if (cur-level 1) { if (cur-right_child ! nullptr) { root cur-right_child; } else { root nullptr; } delete cur; return true; } else { cur replace(cur, work_stack); } } else { if (cur-level 1) { if (root-level 1) { delete cur; root-right_child nullptr; root-right_ptr_is_horizontal_chain false; return true; } } else { cur replace(cur, work_stack); } } if (work_stack.top()-right_child cur) { if (work_stack.top()-right_ptr_is_horizontal_chain) { delete cur; work_stack.top()-right_child nullptr; work_stack.top()-right_ptr_is_horizontal_chain false; return true; } else { if (cur-right_child nullptr) { delete cur; work_stack.top()-right_child nullptr; AATreeNodeT* _left work_stack.top()-left_child; AATreeNodeT* p work_stack.top(); work_stack.pop(); if (_left-right_child nullptr) { p-left_child nullptr; _left-right_child p; _left-right_ptr_is_horizontal_chain true; --(p-level); if (work_stack.empty() false) { if (work_stack.top()-right_child p work_stack.top()-right_ptr_is_horizontal_chain true) { work_stack.top()-right_ptr_is_horizontal_chain false; linkWithUpper(p, _left, work_stack.top()); return true; } linkWithUpper(p, _left, work_stack.top()); cur _left; } else { root _left; return true; } } else { p-right_child nullptr; p-left_child nullptr; --(p-level); AATreeNodeT* red_leaf _left-right_child; _left-right_child nullptr; _left-right_ptr_is_horizontal_chain false; red_leaf-left_child _left; red_leaf-right_child p; (red_leaf-level); if (work_stack.empty() false) { linkWithUpper(p, red_leaf, work_stack.top()); } else { root red_leaf; } return true; } } else { work_stack.top()-right_child cur-right_child; delete cur; return true; } } } else { if (cur-right_child nullptr) { delete cur; if (work_stack.top()-right_ptr_is_horizontal_chain) { AATreeNodeT* _left work_stack.top(); _left-left_child nullptr; --(_left-level); AATreeNodeT* _right _left-right_child; _left-right_child nullptr; _left-right_ptr_is_horizontal_chain false; AATreeNodeT* _right_left _right-left_child; if (_right_left-right_child ! nullptr) { AATreeNodeT* _right_left_right _right_left-right_child; (_right_left-level); _right_left-left_child _left; _right_left-right_child _right; _right-left_child _right_left_right; } else { AATreeNodeT* _right_right _right-right_child; if (_right_right-right_child nullptr) { _right_left-left_child _left; _right_left-right_child _right; (_right_left-level); _right-left_child nullptr; _right-right_ptr_is_horizontal_chain true; --(_right-level); } else { AATreeNodeT* _right_right_right _right_right-right_child; _right_left-left_child _left; _right_left-right_child _right_right; _right_left-right_ptr_is_horizontal_chain true; (_right_left-level); _right_right-left_child _right; _right_right-right_ptr_is_horizontal_chain false; (_right_right-level); _right-left_child nullptr; _right-right_child nullptr; --(_right-level); } } work_stack.pop(); if (work_stack.empty() false) { linkWithUpper(_left, _right_left, work_stack.top()); } else { root _right_left; } return true; } else { AATreeNodeT* p work_stack.top(); work_stack.pop(); p-left_child nullptr; AATreeNodeT* p_right p-right_child; if (p_right-right_child nullptr) { p-right_ptr_is_horizontal_chain true; --(p-level); if (work_stack.empty() false work_stack.top()-right_child p work_stack.top()-right_ptr_is_horizontal_chain) { work_stack.top()-right_ptr_is_horizontal_chain false; return true; } if (work_stack.empty()) { return true; } cur p; } else { AATreeNodeT* p_right_right p_right-right_child; p_right-left_child p; p_right-right_ptr_is_horizontal_chain false; (p_right-level); p-right_child nullptr; --(p-level); if (work_stack.empty()) { root p_right; } else { linkWithUpper(p, p_right, work_stack.top()); } return true; } } } else { work_stack.top()-left_child cur-right_child; delete cur; return true; } } while (work_stack.empty() false) { AATreeNodeT* p work_stack.top(); work_stack.pop(); if (cur p-left_child) { if (p-right_ptr_is_horizontal_chain) { --(p-level); AATreeNodeT* _right_left p-right_child-left_child; processSituation5(p); if (work_stack.empty() false) { linkWithUpper(p, _right_left, work_stack.top()); return true; } else { root _right_left; } } else { AATreeNodeT* p_right p-right_child; if (p_right-right_ptr_is_horizontal_chain) { p-right_child p_right-left_child; p-right_ptr_is_horizontal_chain false; --(p-level); p_right-left_child p; p_right-right_ptr_is_horizontal_chain false; (p_right-level); if (work_stack.empty() false) { linkWithUpper(p, p_right, work_stack.top()); return true; } else { root p_right; } } else { processSituation3(p); --(p-level); if (work_stack.empty() false) { cur p; } } } } else { if (p-right_ptr_is_horizontal_chain false) { AATreeNodeT* _left p-left_child; if (_left-right_ptr_is_horizontal_chain) { cur processSituation1b(_left, p); --(p-level); if (work_stack.empty() false) { linkWithUpper(p, cur, work_stack.top()); } else { root cur; } return true; } else { processSituation1(_left, p); (--p-level); if (work_stack.empty() false) { linkWithUpper(p, _left, work_stack.top()); cur _left; } else { root _left; } } } else { p-right_ptr_is_horizontal_chain false; return true; } } } return true; } template typename T //处理诸情形时不调整节点所在层次只修改指针和水平右链标志 AATreeNodeT* processSituation1(AATreeNodeT* cur, AATreeNodeT* p) { p-left_child cur-right_child; cur-right_child p; cur-right_ptr_is_horizontal_chain true; return cur; } template typename T AATreeNodeT* processSituation1b(AATreeNodeT* cur, AATreeNodeT* p) { AATreeNodeT* _right cur-right_child; cur-right_child _right-left_child; cur-right_ptr_is_horizontal_chain false; p-left_child _right-right_child; _right-left_child cur; _right-right_child p; (_right-level); return _right; } template typename T void processSituation2(AATreeNodeT* p) { p-right_ptr_is_horizontal_chain false; } template typename T void processSituation3(AATreeNodeT* p) { p-right_ptr_is_horizontal_chain true; } template typename T AATreeNodeT* processSituation4(AATreeNodeT* cur, AATreeNodeT* p) { p-right_child cur-left_child; cur-left_child p; cur-right_ptr_is_horizontal_chain false; return p; } template typename T AATreeNodeT* processSituation5(AATreeNodeT* p) //高度必加一 { AATreeNodeT* _right p-right_child; AATreeNodeT* _right_left _right-left_child; p-right_child _right_left-left_child; p-right_ptr_is_horizontal_chain false; AATreeNodeT* _right_left_right _right_left-right_child; _right_left-left_child p; if (_right_left-right_ptr_is_horizontal_chain) { _right_left-right_child _right; (_right_left-level); } else { AATreeNodeT* _right_right _right-right_child; (_right_left-level); if (_right_right-right_ptr_is_horizontal_chain) { _right_left-right_child _right_right; _right_left-right_ptr_is_horizontal_chain true; AATreeNodeT* L3 _right_right-left_child; _right_right-left_child _right; _right_right-right_ptr_is_horizontal_chain false; (_right_right-level); _right-right_child L3; } else { _right_left-right_child _right; _right-right_ptr_is_horizontal_chain true; } --(_right-level); } _right-left_child _right_left_right; return _right_left; } template typename T pairAATreeNodeT*, bool processSituation6(AATreeNodeT* cur, AATreeNodeT* p) //返回的pair(旋转后的新根节点, 旋转后高度加2true, 高度加1false) { AATreeNodeT* _left cur-left_child; AATreeNodeT* _right nullptr; AATreeNodeT* _right_left nullptr; if (_left-right_ptr_is_horizontal_chain || (_right cur-right_child, _right_left _right-left_child, _right_left-right_ptr_is_horizontal_chain)) { p-right_child _left-left_child; // p-right_ptr_is_horizontal_chain false;// cur-right_ptr_is_horizontal_chain false;// _left-left_child p;// (_left-level);// if (_left-right_ptr_is_horizontal_chain) { (cur-level); _left-right_ptr_is_horizontal_chain false; return { cur, true }; } else { AATreeNodeT* _right_left_right _right_left-right_child; cur-left_child _left-right_child; cur-right_child _right_left-left_child; --(cur-level); _left-right_child cur; _right-left_child _right_left_right; _right_left-left_child _left; _right_left-right_child _right; _right_left-right_ptr_is_horizontal_chain false; _right_left-level 2; return { _right_left, true }; } } else { p-right_child _left; cur-left_child p; return { cur, false }; } } template typename T AATreeNodeT* processSituation7(AATreeNodeT* cur, AATreeNodeT* p) { AATreeNodeT* _right_left p-left_child; if (_right_left-right_ptr_is_horizontal_chain) { AATreeNodeT* _right_left_right _right_left-right_child; cur-right_child _right_left_right; p-left_child _right_left_right-right_child; _right_left-right_child _right_left_right-left_child; _right_left-right_ptr_is_horizontal_chain false; _right_left_right-left_child _right_left; _right_left_right-right_child p; (_right_left_right-level); return cur; } else { AATreeNodeT* _left cur-left_child; if (_left-right_ptr_is_horizontal_chain) { AATreeNodeT* _left_right _left-right_child; _left-right_child _left_right-left_child; _left-right_ptr_is_horizontal_chain false; _left_right-left_child _left; AATreeNodeT* L5 _left_right-right_child; _left_right-right_child _right_left; _left_right-right_ptr_is_horizontal_chain true; (_left_right-level); cur-left_child L5; cur-right_child _right_left-left_child; cur-right_ptr_is_horizontal_chain false; --(cur-level); p-left_child _right_left-right_child; _right_left-left_child cur; _right_left-right_child p; (_right_left-level); return _left_right; } else { cur-right_child _right_left; cur-right_ptr_is_horizontal_chain false; p-left_child _right_left-right_child; _right_left-right_child p; _right_left-right_ptr_is_horizontal_chain true; return cur; } } } template typename T AATreeNodeT* processSituation8(AATreeNodeT* cur, AATreeNodeT* p, AATreeNodeT* _new) { _new-right_child cur-left_child; _new-right_ptr_is_horizontal_chain false; cur-left_child _new; cur-right_ptr_is_horizontal_chain false; (cur-level); return cur; } template typename T AATreeNodeT* ifHeightAdd2(AATreeNodeT* cur, AATreeNodeT* p) //操作完后旋转后的新树高度必加一 { if (cur p-left_child) { if (p-right_ptr_is_horizontal_chain false) { processSituation1(cur, p); return processSituation7(cur, p); } else { processSituation2(p); (p-level); return processSituation1(cur, p); } } else { processSituation3(p); return processSituation5(p); } } template typename T pairAATreeNodeT*, bool processLeafNodeInsert(AATreeNodeT* cur, AATreeNodeT* p, AATreeNodeT* pp) //pair(旋转后新根节点,true高度加一, false不变) { if (pp ! nullptr || p-right_ptr_is_horizontal_chain || p-left_child cur) { if (pp ! nullptr) { pp-right_ptr_is_horizontal_chain false; pp-right_child nullptr; } if (pp ! nullptr ? cur p-left_child : p-right_ptr_is_horizontal_chain false) { p-left_child nullptr; cur-right_child p; if (pp ! nullptr) { cur-left_child pp; (cur-level); return { cur, true }; } cur-right_ptr_is_horizontal_chain true; return { cur, false }; } if (pp ! nullptr) { p-left_child pp; p-right_child cur; } else { p-left_child cur; p-right_ptr_is_horizontal_chain false; } (p-level); return { p, true }; } else { p-right_ptr_is_horizontal_chain true; return { p, false }; } } template typename T bool AATreeT::insert(const T key) { if (root nullptr) { root new AATreeNodeT(key); return true; } stackAATreeNodeT* work_stack; AATreeNodeT* cur root; while (cur ! nullptr) { if (cur-data key) { return false; } work_stack.push(cur); if (key cur-data) { cur cur-left_child; } else { cur cur-right_child; } } cur new AATreeNodeT(key); if (cur-data work_stack.top()-data) { work_stack.top()-left_child cur; } else { work_stack.top()-right_child cur; } pairAATreeNodeT*, bool temp; AATreeNodeT* p nullptr; if (work_stack.top()-right_ptr_is_horizontal_chain) { temp processLeafNodeInsertT(cur, work_stack.top(), nullptr); p work_stack.top(); work_stack.pop(); } else { p work_stack.top(); work_stack.pop(); if (work_stack.empty() false work_stack.top()-level 1) { temp processLeafNodeInsert(cur, p, work_stack.top()); p work_stack.top(); work_stack.pop(); } else { temp processLeafNodeInsertT(cur, p, nullptr); } } if (temp.second false) { if (work_stack.empty()) { root temp.first; } else { linkWithUpper(p, temp.first, work_stack.top()); } return true; } else { if (work_stack.empty()) { root temp.first; return true; } linkWithUpper(p, temp.first, work_stack.top()); cur temp.first; } bool height_add_two false; while (true) { AATreeNodeT* p work_stack.top(); work_stack.pop(); if (height_add_two false) { if (p-right_ptr_is_horizontal_chain false || cur ! p-right_child) { if (cur p-left_child) { if (p-right_ptr_is_horizontal_chain false) { if (cur-right_ptr_is_horizontal_chain) { cur processSituation1b(cur, p); if (work_stack.empty()) { root cur; return true; } linkWithUpper(p, cur, work_stack.top()); } else { processSituation1(cur, p); if (work_stack.empty()) { root cur; return true; } linkWithUpper(p, cur, work_stack.top()); if (work_stack.top()-left_child cur || work_stack.top()-right_ptr_is_horizontal_chain false) { return true; } else { processSituation8(cur, p, work_stack.top()); work_stack.pop(); if (work_stack.empty() false) { linkWithUpper(cur-left_child, cur, work_stack.top()); } else { root cur; return true; } } } } else { processSituation2(p); (p-level); if (work_stack.empty()) { return true; } else { cur p; } } } else { if (cur-right_ptr_is_horizontal_chain false) { processSituation3(p); if (work_stack.empty()) { root p; return true; } if (work_stack.top()-left_child p || work_stack.top()-right_ptr_is_horizontal_chain false) { return true; } else { processSituation8(p, cur, work_stack.top()); work_stack.pop(); if (work_stack.empty() false) { linkWithUpper(p-left_child, p, work_stack.top()); cur p; } else { root p; return true; } } } else { processSituation4(cur, p); (cur-level); if (work_stack.empty()) { root cur; return true; } linkWithUpper(p, cur, work_stack.top()); } } } else { if (cur-right_ptr_is_horizontal_chain false) { cur processSituation5(p); if (work_stack.empty()) { root cur; return true; } linkWithUpper(p, cur, work_stack.top()); } else { pairAATreeNodeT*, bool temp processSituation6(cur, p); if (work_stack.empty()) { root temp.first; return true; } linkWithUpper(p, temp.first, work_stack.top()); if (temp.second) { height_add_two true; } cur temp.first; } } } else { cur ifHeightAdd2(cur, p); if (work_stack.empty()) { root cur; return true; } linkWithUpper(p, cur, work_stack.top()); height_add_two false; } } } int main() { const int N 2000; AATreeint g; //vectorint input{7, 15, 18, 16, 20, 1, 9, 21, 17, 6, 14, 12, 11, 2, 19, 5, 10, 8, 13, 3}; vectorint input; for (int i 1; i N; i) { input.push_back(i); } shuffle(input.begin(), input.end(), default_random_engine(time(nullptr))); for (const int run : input) { cout 插入关键码 run endl; if (g.insert(run)) { cout 插入成功 endl; if (g.isAATree()) { cout 当前树是AA树,打印结果:; //g.printAATree(); cout endl; } else { cout 错误,当前树不是AA树! endl; exit(-1); } } else { cout 插入失败 endl; } } for (const int run : input) { cout 删除关键码 run endl; if (g.remove(run)) { cout 删除成功 endl; if (g.isAATree()) { cout 当前树是AA树,打印结果:; //g.printAATree(); cout endl; } else { cout 错误,当前树不是AA树! endl; exit(-1); } } else { cout 删除失败 endl; } } return 0; }