)实现)
所谓1-2-3跳跃表是指跳跃表每一个链接层中两个相邻链接指针之间的下一层节点数只能是12或3.它是一种特殊的跳跃表其操作的时间复杂度可以达到实现C代码如下分为两个版本第一版本中每个节点的所有链接指针用vector容器组织,第二个版本中每个节点的链接指针用list容器组织第一个版本#include iostream #include vector #include deque #include set #include random #include ctime using namespace std; template typename T struct HeadTailNode; template typename T struct NodeInfo { int gap_capacity; HeadTailNodeT* ptr_to_same_level; NodeInfo(const NodeInfoT copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template typename T struct HeadTailNode { vectorNodeInfoT post_ptr; virtual ~HeadTailNode() { } HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNodeT copy) :post_ptr(copy.post_ptr) {} }; template typename T struct _123SkipListNode : public HeadTailNodeT { T data; _123SkipListNode(const T data) :data(data), HeadTailNodeT() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode copy) :data(copy.data), HeadTailNodeT(copy) {} }; template typename T _123SkipListNodeT* typeCast(HeadTailNodeT* convert) { return dynamic_cast_123SkipListNodeT*(convert); } template typename T class _123SkipList { public: _123SkipList(); _123SkipListT* copy(); ~_123SkipList(); bool insert(const T key); bool remove(const T key); private: HeadTailNodeT* head; HeadTailNodeT* tail; }; template typename T _123SkipListT* _123SkipListT::copy() { struct Node_pair { HeadTailNodeT* copy; HeadTailNodeT* _new; Node_pair(HeadTailNodeT* c, HeadTailNodeT* _n) :copy(c), _new(_n) {} bool operator(const Node_pair t) const { return copy t.copy; } }; _123SkipListT* new_123_skip_list new _123SkipList(); new_123_skip_list-~_123SkipList(); new_123_skip_list-head new HeadTailNodeT(*head); setNode_pair has_visited; HeadTailNodeT* cur new_123_skip_list-head; for (HeadTailNodeT* run head; run ! tail; run run-post_ptr[0].ptr_to_same_level) { for (size_t i 0; i run-post_ptr.size(); i) { typename setNode_pair::iterator it has_visited.find(Node_pair(run-post_ptr[i].ptr_to_same_level, nullptr)); if (it ! has_visited.end()) { cur-post_ptr[i].ptr_to_same_level it-_new; } else { if (run-post_ptr[i].ptr_to_same_level tail) { cur-post_ptr[i].ptr_to_same_level new HeadTailNodeT(*tail); } else { cur-post_ptr[i].ptr_to_same_level new _123SkipListNodeT(*typeCast(run-post_ptr[i].ptr_to_same_level)); } has_visited.insert(Node_pair(run-post_ptr[i].ptr_to_same_level, cur-post_ptr[i].ptr_to_same_level)); } } cur cur-post_ptr[0].ptr_to_same_level; } new_123_skip_list-tail new_123_skip_list-head-post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template typename T _123SkipListT::~_123SkipList() { while (head-post_ptr[0].ptr_to_same_level ! tail) { HeadTailNodeT* cur head-post_ptr[0].ptr_to_same_level; head-post_ptr[0].ptr_to_same_level cur-post_ptr[0].ptr_to_same_level; delete cur; } delete head; delete tail; } template typename T _123SkipListT::_123SkipList() :head(new HeadTailNodeT()), tail(new HeadTailNodeT()) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr[0].ptr_to_same_level tail; } template typename T void borrowFromLeft(vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path, HeadTailNodeT* run, int borrow_point, size_t level) { for (int j borrowing_path.size() - 1; j borrow_point; --j) { borrowing_path[j].second-post_ptr.push_back(borrowing_path[j].first-post_ptr.back()); borrowing_path[j].first-post_ptr.pop_back(); borrowing_path[j].second-post_ptr.back().gap_capacity 1; if (j 0) { run-post_ptr[level - 1].ptr_to_same_level borrowing_path[j].second; run-post_ptr[level - 1].gap_capacity - 1; } else { borrowing_path[j - 1].first-post_ptr[level - 1].ptr_to_same_level borrowing_path[j].second; borrowing_path[j - 1].first-post_ptr[level - 1].gap_capacity - 1; } } } template typename T void borrowFromRight(HeadTailNodeT* cur, HeadTailNodeT* first_level, size_t level) { HeadTailNodeT* pre cur; HeadTailNodeT* post cur-post_ptr[level - 1].ptr_to_same_level; do { HeadTailNodeT* sub post-post_ptr[level - 2].ptr_to_same_level; sub-post_ptr.push_back(post-post_ptr.back()); post-post_ptr.pop_back(); pre-post_ptr[level - 1].ptr_to_same_level sub; sub-post_ptr.back().gap_capacity - 1; pre-post_ptr[level - 1].gap_capacity 1; pre sub; post sub-post_ptr[level - 1].ptr_to_same_level; } while (post ! first_level); } template typename T HeadTailNodeT* Find(HeadTailNodeT* run, size_t level) { while (run-post_ptr[level - 2].ptr_to_same_level-post_ptr.size() ! level) { run run-post_ptr[level - 2].ptr_to_same_level; } return run; } template typename T bool _123SkipListT::remove(const T key) { if (head-post_ptr.size() 1) { return false; } size_t level head-post_ptr.size(); HeadTailNodeT* run head; vectorHeadTailNodeT* list(head-post_ptr.size(), nullptr); for (; level 1; --level) { while (run-post_ptr[level - 1].ptr_to_same_level ! tail typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data key) { run run-post_ptr[level - 1].ptr_to_same_level; } list[level - 1] run; } HeadTailNodeT* cur run-post_ptr[0].ptr_to_same_level; if (cur tail || typeCast(cur)-data ! key) { return false; } if (cur-post_ptr.size() 2) { _123SkipListNodeT* _deleted typeCast(cur-post_ptr[0].ptr_to_same_level); typeCast(cur)-data _deleted-data; cur-post_ptr[0].ptr_to_same_level _deleted-post_ptr[0].ptr_to_same_level; delete _deleted; --(cur-post_ptr[1].gap_capacity); } else { run-post_ptr[0].ptr_to_same_level cur-post_ptr[0].ptr_to_same_level; delete typeCast(cur); --(list[1]-post_ptr[1].gap_capacity); cur list[1]; } size_t _size head-post_ptr.size(); for (level 2; level _size; level) { if (cur-post_ptr[level - 1].gap_capacity ! 0) { break; } if (cur-post_ptr.size() level) { HeadTailNodeT* first_level cur-post_ptr[level - 1].ptr_to_same_level; while (first_level ! cur-post_ptr[level].ptr_to_same_level) { if (first_level-post_ptr[level - 1].gap_capacity 2) { break; } first_level first_level-post_ptr[level - 1].ptr_to_same_level; } if (first_level cur-post_ptr[level].ptr_to_same_level) { first_level cur-post_ptr[level - 1].ptr_to_same_level; cur-post_ptr[level - 1].ptr_to_same_level first_level-post_ptr[level - 1].ptr_to_same_level; first_level-post_ptr.pop_back(); cur-post_ptr[level - 1].gap_capacity 2; cur-post_ptr[level].gap_capacity - 1; if (cur-post_ptr[level].gap_capacity ! 0) { break; } } else { borrowFromRight(cur, first_level-post_ptr[level - 1].ptr_to_same_level, level); break; } } else { if (level _size) { head-post_ptr.pop_back(); break; } else { HeadTailNodeT* post cur-post_ptr[level - 1].ptr_to_same_level; run list[level]; vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path; //(借补过程中高度降一的节点高度增一节点) if (post tail || post-post_ptr.size() level) { while (run ! cur) { run Find(run, level); borrowing_path.push_back({ run-post_ptr[level - 2].ptr_to_same_level , run }); run run-post_ptr[level - 2].ptr_to_same_level; } run list[level]; int i borrowing_path.size() - 1; for (; i 0; --i) { if (i 0) { if (run-post_ptr[level - 1].gap_capacity 2) { break; } } else { if (borrowing_path[i - 1].first-post_ptr[level - 1].gap_capacity 2) { break; } } } if (i 0) { cur-post_ptr.pop_back(); if (borrowing_path.size() 1) { run-post_ptr[level - 1].ptr_to_same_level post; run-post_ptr[level - 1].gap_capacity 1; } else { borrowing_path[borrowing_path.size() - 2].first-post_ptr[level - 1].ptr_to_same_level post; borrowing_path[borrowing_path.size() - 2].first-post_ptr[level - 1].gap_capacity 1; } run-post_ptr[level].gap_capacity - 1; if (run-post_ptr[level].gap_capacity ! 0) { break; } cur run; } else { borrowFromLeft(borrowing_path, run, i, level); break; } } else { { int borrow_point; if (run-post_ptr[level - 1].ptr_to_same_level ! cur) { HeadTailNodeT* _first run-post_ptr[level - 1].ptr_to_same_level; if (_first-post_ptr[level - 1].gap_capacity 2) { _first Find(_first, level); borrowing_path.push_back({ run-post_ptr[level - 1].ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point 1; } else if (run-post_ptr[level - 1].gap_capacity 2) { HeadTailNodeT* temp Find(run, level); borrowing_path.push_back({ _first, temp }); temp Find(_first, level); borrowing_path.push_back({ cur , temp }); borrow_point 0; } } else { if (run-post_ptr[level - 1].gap_capacity 2) { HeadTailNodeT* temp Find(run, level); borrowing_path.push_back({ cur, temp }); borrow_point 0; } } if (borrowing_path.empty() false) { borrowFromLeft(borrowing_path, run, borrow_point, level); break; } } { HeadTailNodeT* borrow_point nullptr; if (post-post_ptr[level - 1].ptr_to_same_level ! run-post_ptr[level].ptr_to_same_level) { if (post-post_ptr[level - 1].gap_capacity 2) { borrow_point post-post_ptr[level - 1].ptr_to_same_level; } else { HeadTailNodeT* temp post-post_ptr[level - 1].ptr_to_same_level; if (temp-post_ptr[level - 1].gap_capacity 2) { borrow_point temp-post_ptr[level - 1].ptr_to_same_level; } } } else { if (post-post_ptr[level - 1].gap_capacity 2) { borrow_point run-post_ptr[level].ptr_to_same_level; } } if (borrow_point ! nullptr) { borrowFromRight(cur, borrow_point, level); break; } cur-post_ptr.back().ptr_to_same_level post-post_ptr.back().ptr_to_same_level; post-post_ptr.pop_back(); cur-post_ptr.back().gap_capacity 2; run-post_ptr[level].gap_capacity - 1; if (run-post_ptr[level].gap_capacity ! 0) { break; } cur run; } } } } } return true; } template typename T bool _123SkipListT::insert(const T key) { if (head-post_ptr.size() 1) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr[1].ptr_to_same_level tail; head-post_ptr[1].gap_capacity 1; HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr[0].ptr_to_same_level tail; head-post_ptr[0].ptr_to_same_level _new; return true; } int level head-post_ptr.size(); int original_level head-post_ptr.size(); HeadTailNodeT* run head; HeadTailNodeT* pre_level nullptr; for (; level 1; --level) { while (run-post_ptr[level - 1].ptr_to_same_level ! tail typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data key) { run run-post_ptr[level - 1].ptr_to_same_level; } if (level ! 1) { if (run-post_ptr[level - 1].gap_capacity 3) { if (level original_level) { pre_level head; run-post_ptr.push_back(NodeInfoT()); run-post_ptr.back().ptr_to_same_level tail; } HeadTailNodeT* mid run-post_ptr[level - 2].ptr_to_same_level-post_ptr[level - 2].ptr_to_same_level; mid-post_ptr.push_back(NodeInfoT()); mid-post_ptr.back().ptr_to_same_level run-post_ptr[level - 1].ptr_to_same_level; run-post_ptr[level - 1].ptr_to_same_level mid; mid-post_ptr.back().gap_capacity 1; run-post_ptr[level - 1].gap_capacity 1; pre_level-post_ptr[level].gap_capacity 1; if (key typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data) { run run-post_ptr[level - 1].ptr_to_same_level; } } pre_level run; } else { if (run-post_ptr[0].ptr_to_same_level tail || typeCast(run-post_ptr[0].ptr_to_same_level)-data ! key) { HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr[0].ptr_to_same_level run-post_ptr[0].ptr_to_same_level; run-post_ptr[0].ptr_to_same_level _new; pre_level-post_ptr[1].gap_capacity 1; } else { return false; } } } return true; } int main() { const int N 2000; _123SkipListint g; //vectorint input{34, 12, 9, 23, 56, 11, 6, 67}; 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; } else { cout 插入失败 endl; } } _123SkipListint* copy g.copy(); for (const int run : input) { cout 删除 run endl; if (copy-remove(run)) { cout 删除成功 endl; } else { cout 删除失败 endl; } } delete copy; return 0; }第二个版本:#include iostream #include vector #include deque #include set #include random #include ctime #include list #include algorithm using namespace std; template typename T struct HeadTailNode; template typename T struct NodeInfo { int gap_capacity; HeadTailNodeT* ptr_to_same_level; NodeInfo(const NodeInfoT copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template typename T struct HeadTailNode { listNodeInfoT post_ptr; virtual ~HeadTailNode() {} HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNodeT copy) :post_ptr(copy.post_ptr) {} }; template typename T struct _123SkipListNode : public HeadTailNodeT { T data; _123SkipListNode(const T data) :data(data), HeadTailNodeT() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode copy) :data(copy.data), HeadTailNodeT(copy) {} }; template typename T struct ListNode { typename listNodeInfoT::iterator cur_level_pos; HeadTailNodeT* cur_level_ptr nullptr; ListNode() default; }; template typename T _123SkipListNodeT* typeCast(HeadTailNodeT* convert) { return dynamic_cast_123SkipListNodeT*(convert); } template typename T class _123SkipList { public: _123SkipList(); _123SkipListT* copy(); ~_123SkipList(); bool insert(const T key); bool remove(const T key); private: HeadTailNodeT* head; HeadTailNodeT* tail; }; template typename T _123SkipListT* _123SkipListT::copy() { struct Node_pair { HeadTailNodeT* copy; HeadTailNodeT* _new; Node_pair(HeadTailNodeT* c, HeadTailNodeT* _n) :copy(c), _new(_n) {} bool operator(const Node_pair t) const { return copy t.copy; } }; _123SkipListT* new_123_skip_list new _123SkipList(); new_123_skip_list-~_123SkipList(); new_123_skip_list-head new HeadTailNodeT(*head); setNode_pair has_visited; HeadTailNodeT* cur new_123_skip_list-head; for (HeadTailNodeT* run head; run ! tail; run run-post_ptr.begin()-ptr_to_same_level) { for (typename listNodeInfoT::iterator cur_it cur-post_ptr.begin(), it run-post_ptr.begin(); it ! run-post_ptr.end(); it, cur_it) { typename setNode_pair::iterator temp has_visited.find(Node_pair(it-ptr_to_same_level, nullptr)); if (temp ! has_visited.end()) { cur_it-ptr_to_same_level temp-_new; } else { if (it-ptr_to_same_level tail) { cur_it-ptr_to_same_level new HeadTailNodeT(*tail); } else { cur_it-ptr_to_same_level new _123SkipListNodeT(*typeCast(it-ptr_to_same_level)); } has_visited.insert(Node_pair(it-ptr_to_same_level, cur_it-ptr_to_same_level)); } } cur cur-post_ptr.begin()-ptr_to_same_level; } new_123_skip_list-tail new_123_skip_list-head-post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template typename T _123SkipListT::~_123SkipList() { while (head-post_ptr.front().ptr_to_same_level ! tail) { HeadTailNodeT* cur head-post_ptr.front().ptr_to_same_level; head-post_ptr.front().ptr_to_same_level cur-post_ptr.front().ptr_to_same_level; delete cur; } delete head; delete tail; } template typename T _123SkipListT::_123SkipList() :head(new HeadTailNodeT()), tail(new HeadTailNodeT()) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr.back().ptr_to_same_level tail; } template typename T typename listNodeInfoT::iterator next(typename listNodeInfoT::iterator it) { return it; } template typename T typename listNodeInfoT::iterator _pre(typename listNodeInfoT::iterator it) { return --it; } template typename T void borrowFromLeft(vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path, typename listNodeInfoT::iterator it, int borrow_point) { for (int j borrowing_path.size() - 1; j borrow_point; --j) { borrowing_path[j].second-post_ptr.push_back(borrowing_path[j].first-post_ptr.back()); borrowing_path[j].first-post_ptr.pop_back(); borrowing_path[j].second-post_ptr.back().gap_capacity 1; if (j 0) { it-ptr_to_same_level borrowing_path[j].second; it-gap_capacity - 1; } else { borrowing_path[j - 1].first-post_ptr.back().ptr_to_same_level borrowing_path[j].second; borrowing_path[j - 1].first-post_ptr.back().gap_capacity - 1; } } } template typename T void borrowFromRight(typename listNodeInfoT::iterator it, HeadTailNodeT* first_level) { HeadTailNodeT* post it-ptr_to_same_level; do { HeadTailNodeT* sub _preT(_preT(post-post_ptr.end()))-ptr_to_same_level; sub-post_ptr.push_back(post-post_ptr.back()); post-post_ptr.pop_back(); it-ptr_to_same_level sub; sub-post_ptr.back().gap_capacity - 1; it-gap_capacity 1; it _preT(sub-post_ptr.end()); post it-ptr_to_same_level; } while (post ! first_level); } template typename T HeadTailNodeT* Find(typename listNodeInfoT::iterator it, size_t level) { HeadTailNodeT* run nullptr; while (it-ptr_to_same_level-post_ptr.size() ! level) { run it-ptr_to_same_level; it --run-post_ptr.end(); } return run; } template typename T bool _123SkipListT::remove(const T key) { if (head-post_ptr.size() 1) { return false; } size_t level head-post_ptr.size(); HeadTailNodeT* run head; typename listNodeInfoT::iterator run_it --head-post_ptr.end(); vectorListNodeT list(head-post_ptr.size()); for (; level 1; --level) { while (run_it-ptr_to_same_level ! tail typeCast(run_it-ptr_to_same_level)-data key) { run run_it-ptr_to_same_level; run_it --run-post_ptr.end(); } list[level - 1].cur_level_ptr run; list[level - 1].cur_level_pos run_it; if (level ! 1) { --run_it; } } HeadTailNodeT* cur run-post_ptr.begin()-ptr_to_same_level; if (cur tail || typeCast(cur)-data ! key) { return false; } if (cur-post_ptr.size() 2) { _123SkipListNodeT* _deleted typeCast(cur-post_ptr.begin()-ptr_to_same_level); typeCast(cur)-data _deleted-data; cur-post_ptr.begin()-ptr_to_same_level _deleted-post_ptr.begin()-ptr_to_same_level; delete _deleted; --(((cur-post_ptr.begin()))-gap_capacity); } else { run-post_ptr.begin()-ptr_to_same_level cur-post_ptr.begin()-ptr_to_same_level; delete typeCast(cur); --(list[1].cur_level_pos-gap_capacity); cur list[1].cur_level_ptr; } run_it cur-post_ptr.begin(); run cur; size_t _size head-post_ptr.size(); for (level 2; level _size; level) { if (run-post_ptr.end() run_it) { run_it list[level - 1].cur_level_pos; } if (run_it-gap_capacity ! 0) { break; } if (cur-post_ptr.size() level) { HeadTailNodeT* first_level run_it-ptr_to_same_level; run_it; while (first_level ! run_it-ptr_to_same_level) { if ((--first_level-post_ptr.end())-gap_capacity 2) { break; } first_level (--first_level-post_ptr.end())-ptr_to_same_level; } if (first_level run_it-ptr_to_same_level) { --run_it; first_level run_it-ptr_to_same_level; run_it-ptr_to_same_level (--first_level-post_ptr.end())-ptr_to_same_level; first_level-post_ptr.pop_back(); run_it-gap_capacity 2; next(run_it)-gap_capacity - 1; if (next(run_it)-gap_capacity ! 0) { break; } run cur; } else { --run_it; borrowFromRight(run_it, first_level-post_ptr.back().ptr_to_same_level); break; } } else { if (level _size) { head-post_ptr.pop_back(); break; } else { HeadTailNodeT* post run_it-ptr_to_same_level; run list[level].cur_level_ptr; vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path; //(借补过程中高度降一的节点高度增一节点) typename std::listNodeInfoT::iterator _it list[level].cur_level_pos; if (post tail || post-post_ptr.size() level) { _it _preT(_preT(_it)); while (run ! cur) { run FindT(_it, level); borrowing_path.push_back({ run-post_ptr.back().ptr_to_same_level , run }); run run-post_ptr.back().ptr_to_same_level; _it _preT(_preT(run-post_ptr.end())); } run list[level].cur_level_ptr; _it _preT(list[level].cur_level_pos); int i borrowing_path.size() - 1; for (; i 0; --i) { if (i 0) { if (_it-gap_capacity 2) { break; } } else { if (borrowing_path[i - 1].first-post_ptr.back().gap_capacity 2) { break; } } } if (i 0) { --run_it; cur-post_ptr.pop_back(); if (borrowing_path.size() 1) { _it-ptr_to_same_level post; _it-gap_capacity 1; } else { borrowing_path[borrowing_path.size() - 2].first-post_ptr.back().ptr_to_same_level post; borrowing_path[borrowing_path.size() - 2].first-post_ptr.back().gap_capacity 1; } _it; _it-gap_capacity - 1; if (_it-gap_capacity ! 0) { break; } swap(cur, run); } else { borrowFromLeft(borrowing_path, _it, i); break; } } else { { int borrow_point; --_it; if (_it-ptr_to_same_level ! cur) { HeadTailNodeT* _first _it-ptr_to_same_level; if (_first-post_ptr.back().gap_capacity 2) { _first FindT(_preT(_preT(_first-post_ptr.end())), level); borrowing_path.push_back({ _it-ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point 1; } else if (_it-gap_capacity 2) { HeadTailNodeT* temp FindT(_preT(_it), level); borrowing_path.push_back({ _first, temp }); temp FindT(_preT(_preT(_first-post_ptr.end())), level); borrowing_path.push_back({ cur , temp }); borrow_point 0; } } else { if (_it-gap_capacity 2) { HeadTailNodeT* temp FindT(_preT(_it), level); borrowing_path.push_back({ cur, temp }); borrow_point 0; } } if (borrowing_path.empty() false) { borrowFromLeft(borrowing_path, _it, borrow_point); break; } } { _it; HeadTailNodeT* borrow_point nullptr; if (post-post_ptr.back().ptr_to_same_level ! _it-ptr_to_same_level) { if (post-post_ptr.back().gap_capacity 2) { borrow_point post-post_ptr.back().ptr_to_same_level; } else { HeadTailNodeT* temp post-post_ptr.back().ptr_to_same_level; if (temp-post_ptr.back().gap_capacity 2) { borrow_point temp-post_ptr.back().ptr_to_same_level; } } } else { if (post-post_ptr.back().gap_capacity 2) { borrow_point _it-ptr_to_same_level; } } if (borrow_point ! nullptr) { borrowFromRight(run_it, borrow_point); break; } cur-post_ptr.back().ptr_to_same_level post-post_ptr.back().ptr_to_same_level; post-post_ptr.pop_back(); cur-post_ptr.back().gap_capacity 2; _it-gap_capacity - 1; if (_it-gap_capacity ! 0) { break; } swap(cur, run); } } } } run_it; } return true; } template typename T bool _123SkipListT::insert(const T key) { if (head-post_ptr.size() 1) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr.back().ptr_to_same_level tail; head-post_ptr.back().gap_capacity 1; HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr.begin()-ptr_to_same_level tail; head-post_ptr.begin()-ptr_to_same_level _new; return true; } int level head-post_ptr.size(); int original_level head-post_ptr.size(); HeadTailNodeT* run head; typename listNodeInfoT::iterator run_it --head-post_ptr.end(); typename listNodeInfoT::iterator pre_run_it; for (; level 1; --level) { while (run_it-ptr_to_same_level ! tail typeCast(run_it-ptr_to_same_level)-data key) { run run_it-ptr_to_same_level; run_it --run-post_ptr.end(); } if (level ! 1) { if (run_it-gap_capacity 3) { if (level original_level) { run-post_ptr.push_back(NodeInfoT()); run-post_ptr.back().ptr_to_same_level tail; pre_run_it --run-post_ptr.end(); } HeadTailNodeT* mid _preT(run_it)-ptr_to_same_level; mid mid-post_ptr.back().ptr_to_same_level; mid-post_ptr.push_back(NodeInfoT()); mid-post_ptr.back().ptr_to_same_level run_it-ptr_to_same_level; run_it-ptr_to_same_level mid; mid-post_ptr.back().gap_capacity 1; run_it-gap_capacity 1; pre_run_it-gap_capacity 1; if (key typeCast(mid)-data) { run mid; run_it --run-post_ptr.end(); } } pre_run_it run_it; --run_it; } else { if (run-post_ptr.begin()-ptr_to_same_level tail || typeCast(run-post_ptr.begin()-ptr_to_same_level)-data ! key) { HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr.back().ptr_to_same_level run-post_ptr.begin()-ptr_to_same_level; run-post_ptr.begin()-ptr_to_same_level _new; pre_run_it-gap_capacity 1; } else { return false; } } } return true; } int main() { const int N 2000; _123SkipListint g; //vectorint input{34, 12, 9, 23, 56, 11, 6, 67}; 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; } else { cout 插入失败 endl; } } _123SkipListint* copy g.copy(); for (const int run : input) { cout 删除 run endl; if (copy-remove(run)) { cout 删除成功 endl; } else { cout 删除失败 endl; } } delete copy; return 0; }
所谓1-2-3跳跃表是指跳跃表每一个链接层中两个相邻链接指针之间的下一层节点数只能是12或3.它是一种特殊的跳跃表其操作的时间复杂度可以达到实现C代码如下分为两个版本第一版本中每个节点的所有链接指针用vector容器组织,第二个版本中每个节点的链接指针用list容器组织第一个版本#include iostream #include vector #include deque #include set #include random #include ctime using namespace std; template typename T struct HeadTailNode; template typename T struct NodeInfo { int gap_capacity; HeadTailNodeT* ptr_to_same_level; NodeInfo(const NodeInfoT copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template typename T struct HeadTailNode { vectorNodeInfoT post_ptr; virtual ~HeadTailNode() { } HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNodeT copy) :post_ptr(copy.post_ptr) {} }; template typename T struct _123SkipListNode : public HeadTailNodeT { T data; _123SkipListNode(const T data) :data(data), HeadTailNodeT() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode copy) :data(copy.data), HeadTailNodeT(copy) {} }; template typename T _123SkipListNodeT* typeCast(HeadTailNodeT* convert) { return dynamic_cast_123SkipListNodeT*(convert); } template typename T class _123SkipList { public: _123SkipList(); _123SkipListT* copy(); ~_123SkipList(); bool insert(const T key); bool remove(const T key); private: HeadTailNodeT* head; HeadTailNodeT* tail; }; template typename T _123SkipListT* _123SkipListT::copy() { struct Node_pair { HeadTailNodeT* copy; HeadTailNodeT* _new; Node_pair(HeadTailNodeT* c, HeadTailNodeT* _n) :copy(c), _new(_n) {} bool operator(const Node_pair t) const { return copy t.copy; } }; _123SkipListT* new_123_skip_list new _123SkipList(); new_123_skip_list-~_123SkipList(); new_123_skip_list-head new HeadTailNodeT(*head); setNode_pair has_visited; HeadTailNodeT* cur new_123_skip_list-head; for (HeadTailNodeT* run head; run ! tail; run run-post_ptr[0].ptr_to_same_level) { for (size_t i 0; i run-post_ptr.size(); i) { typename setNode_pair::iterator it has_visited.find(Node_pair(run-post_ptr[i].ptr_to_same_level, nullptr)); if (it ! has_visited.end()) { cur-post_ptr[i].ptr_to_same_level it-_new; } else { if (run-post_ptr[i].ptr_to_same_level tail) { cur-post_ptr[i].ptr_to_same_level new HeadTailNodeT(*tail); } else { cur-post_ptr[i].ptr_to_same_level new _123SkipListNodeT(*typeCast(run-post_ptr[i].ptr_to_same_level)); } has_visited.insert(Node_pair(run-post_ptr[i].ptr_to_same_level, cur-post_ptr[i].ptr_to_same_level)); } } cur cur-post_ptr[0].ptr_to_same_level; } new_123_skip_list-tail new_123_skip_list-head-post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template typename T _123SkipListT::~_123SkipList() { while (head-post_ptr[0].ptr_to_same_level ! tail) { HeadTailNodeT* cur head-post_ptr[0].ptr_to_same_level; head-post_ptr[0].ptr_to_same_level cur-post_ptr[0].ptr_to_same_level; delete cur; } delete head; delete tail; } template typename T _123SkipListT::_123SkipList() :head(new HeadTailNodeT()), tail(new HeadTailNodeT()) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr[0].ptr_to_same_level tail; } template typename T void borrowFromLeft(vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path, HeadTailNodeT* run, int borrow_point, size_t level) { for (int j borrowing_path.size() - 1; j borrow_point; --j) { borrowing_path[j].second-post_ptr.push_back(borrowing_path[j].first-post_ptr.back()); borrowing_path[j].first-post_ptr.pop_back(); borrowing_path[j].second-post_ptr.back().gap_capacity 1; if (j 0) { run-post_ptr[level - 1].ptr_to_same_level borrowing_path[j].second; run-post_ptr[level - 1].gap_capacity - 1; } else { borrowing_path[j - 1].first-post_ptr[level - 1].ptr_to_same_level borrowing_path[j].second; borrowing_path[j - 1].first-post_ptr[level - 1].gap_capacity - 1; } } } template typename T void borrowFromRight(HeadTailNodeT* cur, HeadTailNodeT* first_level, size_t level) { HeadTailNodeT* pre cur; HeadTailNodeT* post cur-post_ptr[level - 1].ptr_to_same_level; do { HeadTailNodeT* sub post-post_ptr[level - 2].ptr_to_same_level; sub-post_ptr.push_back(post-post_ptr.back()); post-post_ptr.pop_back(); pre-post_ptr[level - 1].ptr_to_same_level sub; sub-post_ptr.back().gap_capacity - 1; pre-post_ptr[level - 1].gap_capacity 1; pre sub; post sub-post_ptr[level - 1].ptr_to_same_level; } while (post ! first_level); } template typename T HeadTailNodeT* Find(HeadTailNodeT* run, size_t level) { while (run-post_ptr[level - 2].ptr_to_same_level-post_ptr.size() ! level) { run run-post_ptr[level - 2].ptr_to_same_level; } return run; } template typename T bool _123SkipListT::remove(const T key) { if (head-post_ptr.size() 1) { return false; } size_t level head-post_ptr.size(); HeadTailNodeT* run head; vectorHeadTailNodeT* list(head-post_ptr.size(), nullptr); for (; level 1; --level) { while (run-post_ptr[level - 1].ptr_to_same_level ! tail typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data key) { run run-post_ptr[level - 1].ptr_to_same_level; } list[level - 1] run; } HeadTailNodeT* cur run-post_ptr[0].ptr_to_same_level; if (cur tail || typeCast(cur)-data ! key) { return false; } if (cur-post_ptr.size() 2) { _123SkipListNodeT* _deleted typeCast(cur-post_ptr[0].ptr_to_same_level); typeCast(cur)-data _deleted-data; cur-post_ptr[0].ptr_to_same_level _deleted-post_ptr[0].ptr_to_same_level; delete _deleted; --(cur-post_ptr[1].gap_capacity); } else { run-post_ptr[0].ptr_to_same_level cur-post_ptr[0].ptr_to_same_level; delete typeCast(cur); --(list[1]-post_ptr[1].gap_capacity); cur list[1]; } size_t _size head-post_ptr.size(); for (level 2; level _size; level) { if (cur-post_ptr[level - 1].gap_capacity ! 0) { break; } if (cur-post_ptr.size() level) { HeadTailNodeT* first_level cur-post_ptr[level - 1].ptr_to_same_level; while (first_level ! cur-post_ptr[level].ptr_to_same_level) { if (first_level-post_ptr[level - 1].gap_capacity 2) { break; } first_level first_level-post_ptr[level - 1].ptr_to_same_level; } if (first_level cur-post_ptr[level].ptr_to_same_level) { first_level cur-post_ptr[level - 1].ptr_to_same_level; cur-post_ptr[level - 1].ptr_to_same_level first_level-post_ptr[level - 1].ptr_to_same_level; first_level-post_ptr.pop_back(); cur-post_ptr[level - 1].gap_capacity 2; cur-post_ptr[level].gap_capacity - 1; if (cur-post_ptr[level].gap_capacity ! 0) { break; } } else { borrowFromRight(cur, first_level-post_ptr[level - 1].ptr_to_same_level, level); break; } } else { if (level _size) { head-post_ptr.pop_back(); break; } else { HeadTailNodeT* post cur-post_ptr[level - 1].ptr_to_same_level; run list[level]; vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path; //(借补过程中高度降一的节点高度增一节点) if (post tail || post-post_ptr.size() level) { while (run ! cur) { run Find(run, level); borrowing_path.push_back({ run-post_ptr[level - 2].ptr_to_same_level , run }); run run-post_ptr[level - 2].ptr_to_same_level; } run list[level]; int i borrowing_path.size() - 1; for (; i 0; --i) { if (i 0) { if (run-post_ptr[level - 1].gap_capacity 2) { break; } } else { if (borrowing_path[i - 1].first-post_ptr[level - 1].gap_capacity 2) { break; } } } if (i 0) { cur-post_ptr.pop_back(); if (borrowing_path.size() 1) { run-post_ptr[level - 1].ptr_to_same_level post; run-post_ptr[level - 1].gap_capacity 1; } else { borrowing_path[borrowing_path.size() - 2].first-post_ptr[level - 1].ptr_to_same_level post; borrowing_path[borrowing_path.size() - 2].first-post_ptr[level - 1].gap_capacity 1; } run-post_ptr[level].gap_capacity - 1; if (run-post_ptr[level].gap_capacity ! 0) { break; } cur run; } else { borrowFromLeft(borrowing_path, run, i, level); break; } } else { { int borrow_point; if (run-post_ptr[level - 1].ptr_to_same_level ! cur) { HeadTailNodeT* _first run-post_ptr[level - 1].ptr_to_same_level; if (_first-post_ptr[level - 1].gap_capacity 2) { _first Find(_first, level); borrowing_path.push_back({ run-post_ptr[level - 1].ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point 1; } else if (run-post_ptr[level - 1].gap_capacity 2) { HeadTailNodeT* temp Find(run, level); borrowing_path.push_back({ _first, temp }); temp Find(_first, level); borrowing_path.push_back({ cur , temp }); borrow_point 0; } } else { if (run-post_ptr[level - 1].gap_capacity 2) { HeadTailNodeT* temp Find(run, level); borrowing_path.push_back({ cur, temp }); borrow_point 0; } } if (borrowing_path.empty() false) { borrowFromLeft(borrowing_path, run, borrow_point, level); break; } } { HeadTailNodeT* borrow_point nullptr; if (post-post_ptr[level - 1].ptr_to_same_level ! run-post_ptr[level].ptr_to_same_level) { if (post-post_ptr[level - 1].gap_capacity 2) { borrow_point post-post_ptr[level - 1].ptr_to_same_level; } else { HeadTailNodeT* temp post-post_ptr[level - 1].ptr_to_same_level; if (temp-post_ptr[level - 1].gap_capacity 2) { borrow_point temp-post_ptr[level - 1].ptr_to_same_level; } } } else { if (post-post_ptr[level - 1].gap_capacity 2) { borrow_point run-post_ptr[level].ptr_to_same_level; } } if (borrow_point ! nullptr) { borrowFromRight(cur, borrow_point, level); break; } cur-post_ptr.back().ptr_to_same_level post-post_ptr.back().ptr_to_same_level; post-post_ptr.pop_back(); cur-post_ptr.back().gap_capacity 2; run-post_ptr[level].gap_capacity - 1; if (run-post_ptr[level].gap_capacity ! 0) { break; } cur run; } } } } } return true; } template typename T bool _123SkipListT::insert(const T key) { if (head-post_ptr.size() 1) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr[1].ptr_to_same_level tail; head-post_ptr[1].gap_capacity 1; HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr[0].ptr_to_same_level tail; head-post_ptr[0].ptr_to_same_level _new; return true; } int level head-post_ptr.size(); int original_level head-post_ptr.size(); HeadTailNodeT* run head; HeadTailNodeT* pre_level nullptr; for (; level 1; --level) { while (run-post_ptr[level - 1].ptr_to_same_level ! tail typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data key) { run run-post_ptr[level - 1].ptr_to_same_level; } if (level ! 1) { if (run-post_ptr[level - 1].gap_capacity 3) { if (level original_level) { pre_level head; run-post_ptr.push_back(NodeInfoT()); run-post_ptr.back().ptr_to_same_level tail; } HeadTailNodeT* mid run-post_ptr[level - 2].ptr_to_same_level-post_ptr[level - 2].ptr_to_same_level; mid-post_ptr.push_back(NodeInfoT()); mid-post_ptr.back().ptr_to_same_level run-post_ptr[level - 1].ptr_to_same_level; run-post_ptr[level - 1].ptr_to_same_level mid; mid-post_ptr.back().gap_capacity 1; run-post_ptr[level - 1].gap_capacity 1; pre_level-post_ptr[level].gap_capacity 1; if (key typeCast(run-post_ptr[level - 1].ptr_to_same_level)-data) { run run-post_ptr[level - 1].ptr_to_same_level; } } pre_level run; } else { if (run-post_ptr[0].ptr_to_same_level tail || typeCast(run-post_ptr[0].ptr_to_same_level)-data ! key) { HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr[0].ptr_to_same_level run-post_ptr[0].ptr_to_same_level; run-post_ptr[0].ptr_to_same_level _new; pre_level-post_ptr[1].gap_capacity 1; } else { return false; } } } return true; } int main() { const int N 2000; _123SkipListint g; //vectorint input{34, 12, 9, 23, 56, 11, 6, 67}; 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; } else { cout 插入失败 endl; } } _123SkipListint* copy g.copy(); for (const int run : input) { cout 删除 run endl; if (copy-remove(run)) { cout 删除成功 endl; } else { cout 删除失败 endl; } } delete copy; return 0; }第二个版本:#include iostream #include vector #include deque #include set #include random #include ctime #include list #include algorithm using namespace std; template typename T struct HeadTailNode; template typename T struct NodeInfo { int gap_capacity; HeadTailNodeT* ptr_to_same_level; NodeInfo(const NodeInfoT copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template typename T struct HeadTailNode { listNodeInfoT post_ptr; virtual ~HeadTailNode() {} HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNodeT copy) :post_ptr(copy.post_ptr) {} }; template typename T struct _123SkipListNode : public HeadTailNodeT { T data; _123SkipListNode(const T data) :data(data), HeadTailNodeT() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode copy) :data(copy.data), HeadTailNodeT(copy) {} }; template typename T struct ListNode { typename listNodeInfoT::iterator cur_level_pos; HeadTailNodeT* cur_level_ptr nullptr; ListNode() default; }; template typename T _123SkipListNodeT* typeCast(HeadTailNodeT* convert) { return dynamic_cast_123SkipListNodeT*(convert); } template typename T class _123SkipList { public: _123SkipList(); _123SkipListT* copy(); ~_123SkipList(); bool insert(const T key); bool remove(const T key); private: HeadTailNodeT* head; HeadTailNodeT* tail; }; template typename T _123SkipListT* _123SkipListT::copy() { struct Node_pair { HeadTailNodeT* copy; HeadTailNodeT* _new; Node_pair(HeadTailNodeT* c, HeadTailNodeT* _n) :copy(c), _new(_n) {} bool operator(const Node_pair t) const { return copy t.copy; } }; _123SkipListT* new_123_skip_list new _123SkipList(); new_123_skip_list-~_123SkipList(); new_123_skip_list-head new HeadTailNodeT(*head); setNode_pair has_visited; HeadTailNodeT* cur new_123_skip_list-head; for (HeadTailNodeT* run head; run ! tail; run run-post_ptr.begin()-ptr_to_same_level) { for (typename listNodeInfoT::iterator cur_it cur-post_ptr.begin(), it run-post_ptr.begin(); it ! run-post_ptr.end(); it, cur_it) { typename setNode_pair::iterator temp has_visited.find(Node_pair(it-ptr_to_same_level, nullptr)); if (temp ! has_visited.end()) { cur_it-ptr_to_same_level temp-_new; } else { if (it-ptr_to_same_level tail) { cur_it-ptr_to_same_level new HeadTailNodeT(*tail); } else { cur_it-ptr_to_same_level new _123SkipListNodeT(*typeCast(it-ptr_to_same_level)); } has_visited.insert(Node_pair(it-ptr_to_same_level, cur_it-ptr_to_same_level)); } } cur cur-post_ptr.begin()-ptr_to_same_level; } new_123_skip_list-tail new_123_skip_list-head-post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template typename T _123SkipListT::~_123SkipList() { while (head-post_ptr.front().ptr_to_same_level ! tail) { HeadTailNodeT* cur head-post_ptr.front().ptr_to_same_level; head-post_ptr.front().ptr_to_same_level cur-post_ptr.front().ptr_to_same_level; delete cur; } delete head; delete tail; } template typename T _123SkipListT::_123SkipList() :head(new HeadTailNodeT()), tail(new HeadTailNodeT()) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr.back().ptr_to_same_level tail; } template typename T typename listNodeInfoT::iterator next(typename listNodeInfoT::iterator it) { return it; } template typename T typename listNodeInfoT::iterator _pre(typename listNodeInfoT::iterator it) { return --it; } template typename T void borrowFromLeft(vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path, typename listNodeInfoT::iterator it, int borrow_point) { for (int j borrowing_path.size() - 1; j borrow_point; --j) { borrowing_path[j].second-post_ptr.push_back(borrowing_path[j].first-post_ptr.back()); borrowing_path[j].first-post_ptr.pop_back(); borrowing_path[j].second-post_ptr.back().gap_capacity 1; if (j 0) { it-ptr_to_same_level borrowing_path[j].second; it-gap_capacity - 1; } else { borrowing_path[j - 1].first-post_ptr.back().ptr_to_same_level borrowing_path[j].second; borrowing_path[j - 1].first-post_ptr.back().gap_capacity - 1; } } } template typename T void borrowFromRight(typename listNodeInfoT::iterator it, HeadTailNodeT* first_level) { HeadTailNodeT* post it-ptr_to_same_level; do { HeadTailNodeT* sub _preT(_preT(post-post_ptr.end()))-ptr_to_same_level; sub-post_ptr.push_back(post-post_ptr.back()); post-post_ptr.pop_back(); it-ptr_to_same_level sub; sub-post_ptr.back().gap_capacity - 1; it-gap_capacity 1; it _preT(sub-post_ptr.end()); post it-ptr_to_same_level; } while (post ! first_level); } template typename T HeadTailNodeT* Find(typename listNodeInfoT::iterator it, size_t level) { HeadTailNodeT* run nullptr; while (it-ptr_to_same_level-post_ptr.size() ! level) { run it-ptr_to_same_level; it --run-post_ptr.end(); } return run; } template typename T bool _123SkipListT::remove(const T key) { if (head-post_ptr.size() 1) { return false; } size_t level head-post_ptr.size(); HeadTailNodeT* run head; typename listNodeInfoT::iterator run_it --head-post_ptr.end(); vectorListNodeT list(head-post_ptr.size()); for (; level 1; --level) { while (run_it-ptr_to_same_level ! tail typeCast(run_it-ptr_to_same_level)-data key) { run run_it-ptr_to_same_level; run_it --run-post_ptr.end(); } list[level - 1].cur_level_ptr run; list[level - 1].cur_level_pos run_it; if (level ! 1) { --run_it; } } HeadTailNodeT* cur run-post_ptr.begin()-ptr_to_same_level; if (cur tail || typeCast(cur)-data ! key) { return false; } if (cur-post_ptr.size() 2) { _123SkipListNodeT* _deleted typeCast(cur-post_ptr.begin()-ptr_to_same_level); typeCast(cur)-data _deleted-data; cur-post_ptr.begin()-ptr_to_same_level _deleted-post_ptr.begin()-ptr_to_same_level; delete _deleted; --(((cur-post_ptr.begin()))-gap_capacity); } else { run-post_ptr.begin()-ptr_to_same_level cur-post_ptr.begin()-ptr_to_same_level; delete typeCast(cur); --(list[1].cur_level_pos-gap_capacity); cur list[1].cur_level_ptr; } run_it cur-post_ptr.begin(); run cur; size_t _size head-post_ptr.size(); for (level 2; level _size; level) { if (run-post_ptr.end() run_it) { run_it list[level - 1].cur_level_pos; } if (run_it-gap_capacity ! 0) { break; } if (cur-post_ptr.size() level) { HeadTailNodeT* first_level run_it-ptr_to_same_level; run_it; while (first_level ! run_it-ptr_to_same_level) { if ((--first_level-post_ptr.end())-gap_capacity 2) { break; } first_level (--first_level-post_ptr.end())-ptr_to_same_level; } if (first_level run_it-ptr_to_same_level) { --run_it; first_level run_it-ptr_to_same_level; run_it-ptr_to_same_level (--first_level-post_ptr.end())-ptr_to_same_level; first_level-post_ptr.pop_back(); run_it-gap_capacity 2; next(run_it)-gap_capacity - 1; if (next(run_it)-gap_capacity ! 0) { break; } run cur; } else { --run_it; borrowFromRight(run_it, first_level-post_ptr.back().ptr_to_same_level); break; } } else { if (level _size) { head-post_ptr.pop_back(); break; } else { HeadTailNodeT* post run_it-ptr_to_same_level; run list[level].cur_level_ptr; vectorpairHeadTailNodeT*, HeadTailNodeT* borrowing_path; //(借补过程中高度降一的节点高度增一节点) typename std::listNodeInfoT::iterator _it list[level].cur_level_pos; if (post tail || post-post_ptr.size() level) { _it _preT(_preT(_it)); while (run ! cur) { run FindT(_it, level); borrowing_path.push_back({ run-post_ptr.back().ptr_to_same_level , run }); run run-post_ptr.back().ptr_to_same_level; _it _preT(_preT(run-post_ptr.end())); } run list[level].cur_level_ptr; _it _preT(list[level].cur_level_pos); int i borrowing_path.size() - 1; for (; i 0; --i) { if (i 0) { if (_it-gap_capacity 2) { break; } } else { if (borrowing_path[i - 1].first-post_ptr.back().gap_capacity 2) { break; } } } if (i 0) { --run_it; cur-post_ptr.pop_back(); if (borrowing_path.size() 1) { _it-ptr_to_same_level post; _it-gap_capacity 1; } else { borrowing_path[borrowing_path.size() - 2].first-post_ptr.back().ptr_to_same_level post; borrowing_path[borrowing_path.size() - 2].first-post_ptr.back().gap_capacity 1; } _it; _it-gap_capacity - 1; if (_it-gap_capacity ! 0) { break; } swap(cur, run); } else { borrowFromLeft(borrowing_path, _it, i); break; } } else { { int borrow_point; --_it; if (_it-ptr_to_same_level ! cur) { HeadTailNodeT* _first _it-ptr_to_same_level; if (_first-post_ptr.back().gap_capacity 2) { _first FindT(_preT(_preT(_first-post_ptr.end())), level); borrowing_path.push_back({ _it-ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point 1; } else if (_it-gap_capacity 2) { HeadTailNodeT* temp FindT(_preT(_it), level); borrowing_path.push_back({ _first, temp }); temp FindT(_preT(_preT(_first-post_ptr.end())), level); borrowing_path.push_back({ cur , temp }); borrow_point 0; } } else { if (_it-gap_capacity 2) { HeadTailNodeT* temp FindT(_preT(_it), level); borrowing_path.push_back({ cur, temp }); borrow_point 0; } } if (borrowing_path.empty() false) { borrowFromLeft(borrowing_path, _it, borrow_point); break; } } { _it; HeadTailNodeT* borrow_point nullptr; if (post-post_ptr.back().ptr_to_same_level ! _it-ptr_to_same_level) { if (post-post_ptr.back().gap_capacity 2) { borrow_point post-post_ptr.back().ptr_to_same_level; } else { HeadTailNodeT* temp post-post_ptr.back().ptr_to_same_level; if (temp-post_ptr.back().gap_capacity 2) { borrow_point temp-post_ptr.back().ptr_to_same_level; } } } else { if (post-post_ptr.back().gap_capacity 2) { borrow_point _it-ptr_to_same_level; } } if (borrow_point ! nullptr) { borrowFromRight(run_it, borrow_point); break; } cur-post_ptr.back().ptr_to_same_level post-post_ptr.back().ptr_to_same_level; post-post_ptr.pop_back(); cur-post_ptr.back().gap_capacity 2; _it-gap_capacity - 1; if (_it-gap_capacity ! 0) { break; } swap(cur, run); } } } } run_it; } return true; } template typename T bool _123SkipListT::insert(const T key) { if (head-post_ptr.size() 1) { head-post_ptr.push_back(NodeInfoT()); head-post_ptr.back().ptr_to_same_level tail; head-post_ptr.back().gap_capacity 1; HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr.begin()-ptr_to_same_level tail; head-post_ptr.begin()-ptr_to_same_level _new; return true; } int level head-post_ptr.size(); int original_level head-post_ptr.size(); HeadTailNodeT* run head; typename listNodeInfoT::iterator run_it --head-post_ptr.end(); typename listNodeInfoT::iterator pre_run_it; for (; level 1; --level) { while (run_it-ptr_to_same_level ! tail typeCast(run_it-ptr_to_same_level)-data key) { run run_it-ptr_to_same_level; run_it --run-post_ptr.end(); } if (level ! 1) { if (run_it-gap_capacity 3) { if (level original_level) { run-post_ptr.push_back(NodeInfoT()); run-post_ptr.back().ptr_to_same_level tail; pre_run_it --run-post_ptr.end(); } HeadTailNodeT* mid _preT(run_it)-ptr_to_same_level; mid mid-post_ptr.back().ptr_to_same_level; mid-post_ptr.push_back(NodeInfoT()); mid-post_ptr.back().ptr_to_same_level run_it-ptr_to_same_level; run_it-ptr_to_same_level mid; mid-post_ptr.back().gap_capacity 1; run_it-gap_capacity 1; pre_run_it-gap_capacity 1; if (key typeCast(mid)-data) { run mid; run_it --run-post_ptr.end(); } } pre_run_it run_it; --run_it; } else { if (run-post_ptr.begin()-ptr_to_same_level tail || typeCast(run-post_ptr.begin()-ptr_to_same_level)-data ! key) { HeadTailNodeT* _new new _123SkipListNodeT(key); _new-post_ptr.push_back(NodeInfoT()); _new-post_ptr.back().ptr_to_same_level run-post_ptr.begin()-ptr_to_same_level; run-post_ptr.begin()-ptr_to_same_level _new; pre_run_it-gap_capacity 1; } else { return false; } } } return true; } int main() { const int N 2000; _123SkipListint g; //vectorint input{34, 12, 9, 23, 56, 11, 6, 67}; 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; } else { cout 插入失败 endl; } } _123SkipListint* copy g.copy(); for (const int run : input) { cout 删除 run endl; if (copy-remove(run)) { cout 删除成功 endl; } else { cout 删除失败 endl; } } delete copy; return 0; }
