patricia tree是《数据结构(C语言版)》(美)Ellis Horowitz Sartaj Sahni Susan Anderson-Freed 著 中译本(李建中 张岩 李治军译) p351中介绍的一种改进版的数字查找树其插入删除操作实现如下(插入实现和书上示例代码有出入删除算法为自己思考所得)#include iostream #include vector #include stack #include random using namespace std; struct PatriciaTreeNode { size_t bit_number; vectorbool bit_seq; PatriciaTreeNode* left_child nullptr; PatriciaTreeNode* right_child nullptr; PatriciaTreeNode* ptr_for_node_point_to_element nullptr; PatriciaTreeNode(size_t b, const vectorbool bit) :bit_number(b), bit_seq(bit) {} PatriciaTreeNode(const vectorbool bit) :bit_seq(bit) {} }; class PatriciaTree { public: bool remove(const vectorbool key); bool insert(const vectorbool key); bool search(const vectorbool key); private: PatriciaTreeNode* root nullptr; }; size_t compare(const vectorbool key, const vectorbool node) { size_t i 0; for (; i key.size(); i) { if (key[i] ! node[i]) return i; } return i; } bool isEuqal(const vectorbool key, const vectorbool node) { size_t i compare(key, node); if (i key.size()) return false; return true; } bool PatriciaTree::search(const vectorbool key) { if (root nullptr) { return false; } PatriciaTreeNode* pre root; PatriciaTreeNode* cur root-left_child; while (true) { if (pre-bit_number cur-bit_number) { pre cur; if (key[cur-bit_number - 1] false) { cur cur-left_child; } else { cur cur-right_child; } } else { return isEuqal(key, cur-bit_seq); } } } void executeInsert(const vectorbool key, PatriciaTreeNode* pre, PatriciaTreeNode* cur, PatriciaTreeNode* root, size_t scan_bound) { PatriciaTreeNode* _new new PatriciaTreeNode(key); _new-bit_number scan_bound 1; if (pre root ? false : key[pre-bit_number - 1]) { pre-right_child _new; } else { pre-left_child _new; } if (key[scan_bound]) { _new-right_child _new; _new-left_child cur; } else { _new-left_child _new; _new-right_child cur; } _new-ptr_for_node_point_to_element _new; if (pre-bit_number cur-bit_number) cur-ptr_for_node_point_to_element _new; } bool PatriciaTree::insert(const vectorbool key) { if (root nullptr) { root new PatriciaTreeNode(0, key); root-left_child root; root-ptr_for_node_point_to_element root; return true; } size_t scan_bound key.size() - 1; PatriciaTreeNode* pre root; PatriciaTreeNode* cur root-left_child; while (true) { if (pre-bit_number cur-bit_number) { if (cur-bit_number - 1 scan_bound) { executeInsert(key, pre, cur, root, scan_bound); return true; } pre cur; if (key[cur-bit_number - 1] false) { cur cur-left_child; } else { cur cur-right_child; } } else { scan_bound compare(key, cur-bit_seq); if (scan_bound key.size()) return false; if (scan_bound 1 pre-bit_number) { pre root; cur root-left_child; continue; } executeInsert(key, pre, cur, root, scan_bound); return true; } } } void adjustBeforeDelete(PatriciaTreeNode* parent, PatriciaTreeNode* pre, PatriciaTreeNode* left_or_right) { if (pre parent-left_child) { parent-left_child left_or_right; } else { parent-right_child left_or_right; } if (left_or_right-bit_number pre-bit_number) { left_or_right-ptr_for_node_point_to_element parent; } } void adjustBeforeDelete(PatriciaTreeNode* parent, PatriciaTreeNode* pre, PatriciaTreeNode* cur, PatriciaTreeNode* left_or_right) { if (left_or_right ! pre) { adjustBeforeDelete(parent, pre, left_or_right); if (pre-ptr_for_node_point_to_element-left_child pre) { pre-ptr_for_node_point_to_element-left_child cur; } else { pre-ptr_for_node_point_to_element-right_child cur; } cur-ptr_for_node_point_to_element pre-ptr_for_node_point_to_element; } else { if (pre parent-left_child) { parent-left_child cur; } else { parent-right_child cur; } cur-ptr_for_node_point_to_element parent; } } bool PatriciaTree::remove(const vectorbool key) { if (root nullptr) { return false; } if (root-left_child root) { delete root; root nullptr; return true; } PatriciaTreeNode* parent root; PatriciaTreeNode* pre root; PatriciaTreeNode* cur root-left_child; while (true) { if (pre-bit_number cur-bit_number) { parent pre; pre cur; if (key[cur-bit_number - 1] false) { cur cur-left_child; } else { cur cur-right_child; } } else { if (compare(key, cur-bit_seq) key.size()) { return false; } if (pre ! cur) { cur-bit_seq pre-bit_seq; if (pre-left_child cur) { adjustBeforeDelete(parent, pre, cur, pre-right_child); } else { adjustBeforeDelete(parent, pre, cur, pre-left_child); } } else { if (pre-right_child cur) { adjustBeforeDelete(parent, pre, pre-left_child); } else { adjustBeforeDelete(parent, pre, pre-right_child); } } delete pre; return true; } } } void genSeq(vectorbool seq, vectorvectorbool input, size_t level) { if (level seq.size()) input.push_back(seq); else { seq[level] true; genSeq(seq, input, level 1); seq[level] false; genSeq(seq, input, level 1); } } int main() { //vectorvectorbool input{ {true, false, false, false}, {false, false, true, false}, {true, false, false, true}, {true, true, false, false}, {false, false, false, false}, {false, false, false, true} }; vectorvectorbool input; const int N 10; vectorbool seq(N); genSeq(seq, input, 0); shuffle(input.begin(), input.end(), default_random_engine()); PatriciaTree obj; for (size_t i 0; i input.size(); i) { cout 插入; for (size_t j 0; j input[i].size(); j) { if (input[i][j]) { cout 1; } else { cout 0; } } cout endl; if (obj.insert(input[i])) { cout 插入成功; } else { cout 插入失败; } cout endl; } for (size_t i 0; i input.size(); i) { cout 删除; for (size_t j 0; j input[i].size(); j) { if (input[i][j]) { cout 1; } else { cout 0; } } cout endl; if (obj.remove(input[i])) { cout 删除成功; } else { cout 删除失败; } cout endl; } /*for (size_t i 0; i input.size()/2; i) { cout 插入; for (size_t j 0; j input[i].size(); j) { if (input[i][j]) { cout 1; } else { cout 0; } } cout endl; if (obj.insert(input[i])) { cout 插入成功; } else { cout 插入失败; } cout endl; }*/ return 0; }