为避免普通的二叉搜索树在最坏情况下退化为单链表,引入了使二叉搜索树近似保持平衡的treap树,treap是一棵二叉搜索树和普通的二叉搜索树不同的是,treap树每一个节点有一个附加的数据域pri,各节点的pri满足最大或最小堆序treap树各节点按关键码组织为二叉搜索树按pri数据域组织为最小堆或最大堆只要在插入或删除时保证堆性质不被破坏就能使二叉搜索树尽可能保持近似平衡保证搜索效率treap树就是二叉搜索树和堆合二为一的产物treap树删除:以最小堆序为例设被删节点为p,若p为叶节点直接删除结束。若p只有一颗子树删除p并把唯一一棵子树链接至p父节点对应指针域结束.若p有两棵子树在两棵子树的根节点中选择pri值较小的节点若该节点是p左子女对p右单旋转,若该节点是p的右子女对p左单旋转旋转完毕后,p应仍然指向旋转前它指向的节点然后对p继续实行以上操作直到结束为止treap树插入以最小堆序为例根据要插入的关键码用二叉搜索树插入算法往treap树中插入新节点然后为新节点生成随机的pri值令p为新插入的节点,算法开始若p为根节点结束算法,否则若p的pri值大于等于p的父节点pri值则结束算法否则若p为父节点的左子女对父节点作右单旋转,若p为父节点右子女对父节点作左单旋转,旋转结束后应令p指向旋转前p指向的节点。然后对p重复前述操作直到结束为止仔细想想不难证明插入删除算法都能保证treap树的性质(二叉搜索树和堆)不被破坏以下是实现treap树的C代码:#include iostream #include stack #include random #include vector using namespace std; template typename T struct TreapTreeNode //Treap树节点定义 { T data_field; unsigned long long priority 0; //堆中优先级 TreapTreeNode* left_child nullptr; TreapTreeNode* right_child nullptr; TreapTreeNode(const T d, unsigned long long p) :data_field(d), priority(p) {} }; template typename T void leftRotate(TreapTreeNodeT* ptr) { TreapTreeNodeT* p ptr-right_child; ptr-right_child p-left_child; p-left_child ptr; ptr p; } template typename T void rightRotate(TreapTreeNodeT* ptr) { TreapTreeNodeT* p ptr-left_child; ptr-left_child p-right_child; p-right_child ptr; ptr p; } template typename T struct JudgeResult //对二叉树的判断结果 { bool isTreap true; //是否为二叉搜索树 T max_value_in_Treap; //二叉搜索树中最大节点值 T min_value_in_Treap; //二叉搜索树中的最小节点值 }; template typename T class TreapTree { public: bool insert(const T key); //插入关键码 bool remove(const T key); //移除关键码 bool judgeTreap() { return isTreap(root).isTreap; } TreapTree() default; TreapTree(unsigned long long seed) :make_priority(seed) {} ~TreapTree() { destory(root); } private: JudgeResultT isTreap(TreapTreeNodeT* root); //判断当前二叉树是否为Treap树 void destory(TreapTreeNodeT* root) { if (root ! nullptr) { destory(root-left_child); destory(root-right_child); delete root; } } TreapTreeNodeT* root nullptr; //Treap树根节点 default_random_engine make_priority; //为新插入节点生成堆优先级的随机数引擎 }; template typename T bool TreapTreeT::insert(const T key) { stackTreapTreeNodeT* work_stack; TreapTreeNodeT* cur root; if (cur nullptr) { root new TreapTreeNodeT(key, make_priority()); return true; } else { while (cur ! nullptr) { if (key cur-data_field) { return false; } if (key cur-data_field) { work_stack.push(cur); cur cur-right_child; } else { work_stack.push(cur); cur cur-left_child; } } } if (key work_stack.top()-data_field) { cur work_stack.top()-left_child new TreapTreeNodeT(key, make_priority()); } else { cur work_stack.top()-right_child new TreapTreeNodeT(key, make_priority()); } while (true) { if (cur-priority work_stack.top()-priority) { if (work_stack.top()-left_child cur) { rightRotate(work_stack.top()); } else { leftRotate(work_stack.top()); } work_stack.pop(); if (work_stack.empty() false) { if (cur-data_field work_stack.top()-data_field) { work_stack.top()-left_child cur; } else { work_stack.top()-right_child cur; } } else { root cur; return true; } } else { return true; } } } template typename T void process(TreapTreeNodeT* cur, TreapTreeNodeT* parent, TreapTreeNodeT* value) { if (parent-left_child cur) { parent-left_child value; } else { parent-right_child value; } } template typename T bool TreapTreeT::remove(const T key) { TreapTreeNodeT* cur root; TreapTreeNodeT* parent nullptr; while (cur ! nullptr) { if (cur-data_field key) { break; } parent cur; if (key cur-data_field) { cur cur-left_child; } else { cur cur-right_child; } } if (cur nullptr) { return false; } while (true) { if (cur-left_child nullptr) { if (cur-right_child nullptr) { if (parent ! nullptr) { process(cur, parent, static_castTreapTreeNodeT*(nullptr)); delete cur; } else { root nullptr; } } else { if (parent ! nullptr) { process(cur, parent, cur-right_child); } else { root cur-right_child; } delete cur; } return true; } else { if (cur-right_child nullptr) { if (parent ! nullptr) { process(cur, parent, cur-left_child); } else { root cur-left_child; } delete cur; return true; } else { TreapTreeNodeT* p nullptr; if (cur-left_child-priority cur-right_child-priority) { p cur-left_child; rightRotate(cur); } else { p cur-right_child; leftRotate(cur); } if (parent ! nullptr) { process(cur, parent, p); } else { root p; } parent p; } } } } template typename T JudgeResultT TreapTreeT::isTreap(TreapTreeNodeT* root) { if (root nullptr) { return JudgeResultT(); } JudgeResultT result; if (root-left_child ! nullptr) { JudgeResultT temp isTreap(root-left_child); if (temp.isTreap true temp.max_value_in_Treap root-data_field root-priority root-left_child-priority) { result.min_value_in_Treap temp.min_value_in_Treap; } else { result.isTreap false; } } else { result.min_value_in_Treap root-data_field; } if (root-right_child ! nullptr) { JudgeResultT temp isTreap(root-right_child); if (temp.isTreap true temp.min_value_in_Treap root-data_field root-priority root-right_child-priority) { result.max_value_in_Treap temp.max_value_in_Treap; } else { result.isTreap false; } } else { result.max_value_in_Treap root-data_field; } return result; } int main() { const int N 2000; TreapTreeint test_obj; vectorsize_t data(N); for (size_t i 0; i N; i) data[i] i 1; shuffle(data.begin(), data.end(), default_random_engine()); for (const int i : data) { cout 在Treap树中插入关键码 i endl; test_obj.insert(i); if (!test_obj.judgeTreap()) { cout ERROR:当前树不为Treap树 endl; exit(-1); } else { cout 当前树为Treap树 endl; cout endl; } } for (const int i : data) { cout 在Treap树中删除关键码 i endl; test_obj.remove(i); if (!test_obj.judgeTreap()) { cout ERROR:当前树不为Treap树 endl; exit(-1); } else { cout 当前树为Treap树 endl; cout endl; } } return 0; }