{"id":402452,"date":"2024-06-29T16:30:51","date_gmt":"2024-06-29T16:30:51","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=402452"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=402452","title":{"rendered":"\u041a\u0440\u0430\u0441\u0438\u0432\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e PATRICIA (\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 C++)<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

\u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a, \u0445\u0430\u0431\u0440\u043e\u0432\u0447\u0430\u043d\u0435! \u0421\u0435\u0439\u0447\u0430\u0441 \u044f \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u044e \u043e\u043a\u0443\u043d\u0443\u0442\u044c \u0432\u0430\u0441 \u0432 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435, \u0432\u0441\u0435\u043c\u0438 \u0437\u0430\u0431\u044b\u0442\u043e\u0435, \u0433\u0434\u0435-\u0442\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e PATRICIA, \u0442\u0430\u043a\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e \u0435\u0435 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u0421++, \u0431\u0443\u0434\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u043d\u043e, \u043f\u0440\u0438\u0433\u043e\u0442\u043e\u0432\u044c\u0442\u0435\u0441\u044c.<\/p>\n\n

<\/figcaption><\/figure>\n

\u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0442\u0435\u043e\u0440\u0438\u0438 \u0438 \u0441\u0440\u0430\u0437\u0443 \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n

\u041f\u0430\u0442\u0440\u0438\u0446\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0441\u043c\u0435\u0448\u0435\u043d\u0438\u0435 trie \u0438 DST \u0434\u0435\u0440\u0435\u0432\u0430, \u043d\u0430 \u043d\u0435\u0439 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0432\u043e\u0439 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u043e\u043a, \u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e \u0431\u0438\u0442\u0430.<\/p>\n

\u041a\u0430\u0436\u0434\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0438\u043c\u0435\u0435\u0442:<\/p>\n

    \n
  1. \n

    \u041a\u043b\u044e\u0447(string key<\/code>)<\/p>\n<\/li>\n

  2. \n

    \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435(int value<\/code>)<\/p>\n<\/li>\n

  3. \n

    \u0418\u043d\u0434\u0435\u043a\u0441 \u0431\u0438\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430(size_t index<\/code>)<\/p>\n<\/li>\n

  4. \n

    \u0423\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u043f\u0440\u0430\u0432\u0443\u044e \u0438 \u043b\u0435\u0432\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443(Node *right, *left<\/code>)<\/p>\n<\/li>\n<\/ol>\n

    struct Patricia::Node{     std::string key;     int value;     size_t index;     Node *right, *left;      Node(const std::string& key, const int& value, const int& index)         : key(key), value(value), index(index), left(nullptr), right(nullptr) { }      ~Node(){} };<\/code><\/pre>\n
    \u0422\u0435\u043f\u0435\u0440\u044c \u0441\u0430\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043e \u0441\u0430\u043c\u043e\u0439 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438, \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 \u043e \u0435\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u0445, \u0438\u0445 \u043d\u0435\u043c\u043d\u043e\u0433\u043e. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043f\u0440\u0430\u0432\u044b\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043a\u043e\u0440\u043d\u044f — nullptr<\/code> \u0432\u0441\u0435\u0433\u0434\u0430<\/strong>. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u043a\u0430\u0436\u0434\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438, \u043a\u0440\u043e\u043c\u0435 \u043a\u043e\u0440\u043d\u044f \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0438\u043d\u0434\u0435\u043a\u0441, \u0438 \u0432\u0441\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0432\u0441\u0435\u0433\u0434\u0430<\/strong> \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u044b \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043a\u0430\u0436\u0434\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0441\u0430\u043c\u043e\u043c \u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043e\u0440\u043d\u044f, \u0430 \u043f\u043e\u0438\u0441\u043a \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043e\u0442 \u043a\u043e\u0440\u043d\u044f. \u0412-\u0442\u0440\u0435\u0442\u044c\u0438\u0445, \u043b\u0438\u0441\u0442\u043e\u043c \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u043e\u0434\u0438\u043d \u0438\u0437 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d \u043d\u0430 \u0441\u0430\u043c\u043e\u0433\u043e \u0441\u0435\u0431\u044f. \u041d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n
    typedef class Patricia{ private:     struct Node;     Node *root = nullptr; public: } patr;<\/code><\/pre>\n
    \u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438 (\u0434\u043b\u044f \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u044f \u044f \u043d\u0435 \u0441\u0442\u0430\u043b \u0440\u0438\u0441\u043e\u0432\u0430\u0442\u044c value \u0432\u0435\u0440\u0448\u0438\u043d):<\/p>\n
    \"\u041f\u0440\u0438\u043c\u0435\u0440
    \u041f\u0440\u0438\u043c\u0435\u0440 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438 1<\/figcaption><\/figure>\n
    \u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c\u0441\u044f \u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u0435, \u0441\u043f\u0440\u0430\u0432\u0430 \u0441\u0432\u0435\u0440\u0445\u0443 \u043d\u0430\u0440\u0438\u0441\u043e\u0432\u0430\u043d \u0448\u0430\u0431\u043b\u043e\u043d, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0443\u043a\u0430\u0437\u0430\u043d\u043e, \u0447\u0442\u043e \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442\u0441\u044f. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0438\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c, \u043d\u0430\u0445\u043e\u0434\u044f\u0441\u044c \u0432 \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435. \u0412\u043d\u0438\u0437\u0443 \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u0441\u0430\u043c \u043a\u043b\u044e\u0447. \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0434\u0435\u0440\u0435\u0432\u0430(1).<\/p>\n
    \u0421\u0434\u0435\u043b\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0430\u043b\u0444\u0430\u0432\u0438\u0442 \u0432 \u043d\u0430\u0448\u0435\u043c \u043a\u043b\u044e\u0447\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u0438\u0435 \u0431\u0443\u043a\u0432\u044b \u0432 \u043d\u0438\u0436\u043d\u0435\u043c \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0435. \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043d\u0430 \u044d\u043a\u0440\u0430\u043d \u0431\u0438\u0442\u043e\u0432\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0439 \u0431\u0443\u043a\u0432\u044b, \u043d\u0430\u043c \u044d\u0442\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f(\u0441\u043e\u0432\u0435\u0442\u0443\u044e \u043f\u0440\u043e\u0434\u0443\u0431\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u043a\u043b\u0430\u0434\u043a\u0443).<\/p>\n
    \"\u041a\u043e\u043d\u0435\u0447\u043d\u043e
    \u041a\u043e\u043d\u0435\u0447\u043d\u043e \u0436\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0431\u0430\u0439\u0442(\u0441\u0438\u043c\u0432\u043e\u043b) \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f 8 \u0431\u0438\u0442\u0430\u043c\u0438, \u043d\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u043d\u0438\u0436\u043d\u0435\u0433\u043e \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u0448\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c\u0438 5-\u044e \u0431\u0438\u0442\u0430\u043c\u0438<\/figcaption><\/figure>\n
    \u041f\u043e\u0438\u0441\u043a<\/h2>\n
    \u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u0443\u0437\u0435\u043b \u0441 \u043a\u043b\u044e\u0447\u043e\u043c «a», \u0435\u0433\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 00001. \u0412\u0430\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u0438\u0434\u0435\u0442 \u043d\u0435 \u0441 0, \u0430 \u0441 1, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c ‘1’ \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 5.<\/p>\n
    \u041a\u0430\u043a \u0431\u044b\u043b\u043e \u0441\u043a\u0430\u0437\u0430\u043d\u043e \u0432\u044b\u0448\u0435, \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043e\u0440\u043d\u044f, \u0435\u0441\u043b\u0438 \u0435\u0433\u043e \u043d\u0435\u0442, \u0442\u043e \u0432\u044b\u0432\u043e\u0434\u0438\u043c nullptr<\/code>, \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c, \u0442\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u0441 \u043b\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u044d\u0442\u043e \u0443\u0437\u0435\u043b \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 1<\/strong> \u0438 \u043a\u043b\u044e\u0447\u043e\u043c «y». \u0411\u0435\u0440\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441<\/abbr> \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0431\u0438\u0442 \u0438\u0437 \u0438\u0441\u043a\u043e\u043c\u043e\u0439 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438<\/abbr> \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430. \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0438\u0442 \u0440\u0430\u0432\u0435\u043d — 0, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b \u0434\u0432\u0438\u0433\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e.<\/p>\n
    \u0422\u0435\u043f\u0435\u0440\u044c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0440\u0430\u0432\u0435\u043d \u0438\u043d\u0434\u0435\u043a\u0441\u0443 2<\/strong> \u0438 \u043a\u043b\u044e\u0447\u0443 «l», \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0431\u0438\u0442 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430(«\u0430») \u043f\u043e \u0442\u0435\u043a\u0443\u0449\u0435\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443(2). \u0411\u0438\u0442 \u0440\u0430\u0432\u0435\u043d — 0, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u043d\u043e\u0432\u0430 \u0434\u0432\u0438\u0433\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e.<\/p>\n
    \u0422\u0435\u043f\u0435\u0440\u044c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0440\u0430\u0432\u0435\u043d \u0438\u043d\u0434\u0435\u043a\u0441\u0443 4<\/strong> \u0438 \u043a\u043b\u044e\u0447\u0443 «b», \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0431\u0438\u0442 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430(«\u0430») \u043f\u043e \u0442\u0435\u043a\u0443\u0449\u0435\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443(4). \u0411\u0438\u0442 \u0440\u0430\u0432\u0435\u043d — 0, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u043d\u043e\u0432\u0430 \u0434\u0432\u0438\u0433\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e.<\/p>\n
    \u041f\u043e\u0438\u0441\u043a \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u0435\u043d \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443, \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 — 0<\/strong>, \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 — 4<\/strong>. \u041f\u043e\u0438\u0441\u043a \u0437\u0430\u043a\u043e\u043d\u0447\u0435\u043d, \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430: «\u0430», \u0438\u043d\u0434\u0435\u043a\u0441 0 — \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0443\u0436\u043d\u043e\u0439 \u043d\u0430\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0438\u0441\u043a\u0430\u043b\u0438.<\/p>\n
    \"\u0422\u0435\u043c\u043d\u043e
    \u0422\u0435\u043c\u043d\u043e \u043e\u0440\u0430\u043d\u0436\u0435\u0432\u044b\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0443\u0437\u043b\u044b, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u0421\u0438\u043d\u0438\u043c — \u0441\u0442\u0440\u0435\u043b\u043a\u0438, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u041a\u0440\u0430\u0441\u043d\u044b\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u043d \u0443\u0437\u0435\u043b, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0441\u044f \u043f\u043e\u0438\u0441\u043a \u0421\u0432\u0435\u0440\u0445\u0443 \u0432 \u043a\u0440\u0430\u0441\u043d\u043e\u043c \u043e\u0431\u0440\u0430\u043c\u043b\u0435\u043d\u0438\u0438 \u0443\u043a\u0430\u0437\u0430\u043d \u043c\u0435\u0442\u043e\u0434, \u043a\u043b\u044e\u0447 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0438\u0449\u0435\u043c \u0438 \u0435\u0433\u043e \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430<\/figcaption><\/figure>\n
    \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043c\u0435\u0442\u043e\u0434 Search. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u0434\u0432\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f currentNode \u0438 prevNode, \u043e\u043d\u0438 \u043d\u0443\u0436\u043d\u044b \u0434\u043b\u044f \u043e\u0442\u0441\u043b\u0435\u0436\u0438\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438 \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0433\u0434\u0430 currentNode->index <= prevNode->index<\/code>.<\/p>\n
    Patricia::Node* Patricia::Search(const std::string& findKey) const{     Node *currentNode = root->left, *prevNode = root;      while(currentNode->index > prevNode->index){         \/\/ Index of char that we need to check         size_t charIndex = (currentNode->index - 1) \/ BIT_COUNT;<\/code><\/pre>\n
    \u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438. \u0411\u0435\u0440\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u0438\u0437 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430, \u0432\u044b\u0447\u0438\u0442\u0430\u044f 1. \u0414\u0430\u043b\u044c\u0448\u0435 \u0434\u0435\u043b\u0438\u043c \u043d\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443 BIT_COUNT<\/abbr>. \u0412\u044b\u0447\u0438\u0442\u0430\u0435\u043c 1 \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u043d\u0435 \u0441 0, \u0430 \u0441 1. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u0438\u0437 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438 1 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 «m», \u0443 \u043d\u0435\u0435 \u0438\u043d\u0434\u0435\u043a\u0441 5 — 1 = 4, \u043f\u0440\u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u043d\u0430 BIT_COUNT \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u0435\u0441\u043b\u0438 \u0431\u044b \u043c\u044b \u043d\u0435 \u0432\u044b\u0447\u0438\u0442\u0430\u043b\u0438, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0431\u044b \u0438\u043d\u0434\u0435\u043a\u0441 1, \u0447\u0442\u043e \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e.<\/p>\n
    \u0414\u0430\u043b\u044c\u0448\u0435 \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438:<\/p>\n
        \/\/ FindKey is less than need char     if(charIndex >= findKey.size()){       \/\/ Remember prevNode       prevNode = currentNode;       \/\/ Only '0'       currentNode = currentNode->left;       continue;     }<\/code><\/pre>\n
    \u0415\u0441\u043b\u0438 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u044b, \u0442\u043e \u043c\u044b «\u043a\u0430\u043a \u0431\u044b» \u0431\u0435\u0440\u0435\u043c \u0431\u0438\u0442 \u0438\u0437 \u043d\u0443\u043b\u0435\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0440\u0430\u0432\u043d\u0430 — 00000, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0432 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0431\u0438\u0442 0, \u0430 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e, \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u044f \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0432 prevNode<\/code>.<\/p>\n
    char currentChar = findKey[charIndex];         \/\/ How many times should we shift to the right         int offset = (BIT_COUNT - 1 - ((currentNode->index - 1) % BIT_COUNT));         \/\/ Get current bit         bool currentBit = (currentChar >> offset) & 1;          \/\/ Remember prevNode         prevNode = currentNode;         \/\/ If '1' go right, '0' go left         currentBit  ? currentNode = currentNode->right                     : currentNode = currentNode->left;     }     return currentNode;<\/code><\/pre>\n
    \u0415\u0441\u043b\u0438 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432\u0441\u0435 \u0442\u0430\u043a\u0438 \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u0437\u044f\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0437 \u0441\u0442\u0440\u043e\u043a\u0438. \u0412\u044b\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435, \u0442.\u0435. \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0434\u043e \u0441\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0431\u0438\u0442\u043e\u0432\u0443\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0443, \u0447\u0442\u043e\u0431 \u043d\u0443\u0436\u043d\u044b\u0439 \u043d\u0430\u043c \u0431\u0438\u0442 \u043e\u0441\u0442\u0430\u043b\u0441\u044f \u0432 \u0441\u0430\u043c\u043e\u043c \u043a\u0440\u0430\u0439\u043d\u0435\u043c \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0432\u0437\u044f\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0439 \u0431\u0438\u0442 \u0438\u0437 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 10001, \u0442\u043e\u0433\u0434\u0430 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e 4.<\/p>\n
    \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0431\u0438\u0442, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0418 <\/strong>\u0438 \u0441\u0434\u0432\u0438\u0433\u0430,<\/strong> \u043f\u0440\u043e\u0449\u0435 \u0433\u043e\u0432\u043e\u0440\u044f \u0435\u0441\u043b\u0438 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0431\u0438\u0442\u043e\u0432\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 ‘1’, \u0442\u043e currentBit = true<\/code>, \u0435\u0441\u043b\u0438 ‘0’, \u0442\u043e false<\/code>.<\/p>\n
    \u0417\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0434\u0432\u0438\u0433\u0430\u0442\u044c \u0435\u0435. \u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0435\u0440\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0418\u0437 \u043c\u0435\u0442\u043e\u0434\u0430 Search \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c currentNode<\/code>, \u043a\u043e\u0433\u0434\u0430 \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0443\u0434\u0435\u0442 <= \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u041f\u043e\u043b\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n
    Patricia::Node* Patricia::Search(const std::string& findKey) const{     Node *currentNode = root->left, *prevNode = root;      while(currentNode->index > prevNode->index){         \/\/ Index of char that we need to check         size_t charIndex = (currentNode->index - 1) \/ BIT_COUNT;          \/\/ findKey is less than need char         if(charIndex >= findKey.size()){           \/\/ Remember prevNode             prevNode = currentNode;             \/\/ Only '0'             currentNode = currentNode->left;             continue;         }          char currentChar = findKey[charIndex];         \/\/ How many times should we shift to the right         int offset = (BIT_COUNT - 1 - ((currentNode->index - 1) % BIT_COUNT));         \/\/ Get current bit         bool currentBit = (currentChar >> offset) & 1;          \/\/ Remember prevNode         prevNode = currentNode;         \/\/ If '1' go right, '0' go left         currentBit  ? currentNode = currentNode->right                     : currentNode = currentNode->left;     }     return currentNode; }<\/code><\/pre>\n
    \u0421\u0442\u043e\u0438\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u044f \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u044e \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043a\u043e\u0440\u043d\u044f, \u0432\u0441\u0435 \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0432 \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u043e\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u0435, \u0438 \u043a\u0430\u0436\u0434\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u0434 \u0432\u044b\u0437\u043e\u0432\u043e\u043c Search \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043a\u043e\u0440\u043d\u044f. \u0415\u0441\u043b\u0438 \u0432\u044b \u0434\u0435\u043b\u0430\u0435\u0442\u0435 \u0434\u0440\u0443\u0433\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e, \u0442\u043e \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 left, \u0435\u0441\u043b\u0438 root = nullptr, \u0442\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u043a\u0440\u0430\u0448\u043d\u0435\u0442\u0441\u044f»>\u0441\u043b\u043e\u043c\u0430\u0442\u044c \u0432\u0430\u0448\u0443 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443<\/abbr> :\u0441<\/p>\n
    \u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043f\u0430\u0440\u044b \u0432 \u0434\u0435\u0440\u0435\u0432\u043e<\/h2>\n
    \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u0430\u0440\u044b \u0432 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n
      \n
    1. \n
      \u041d\u0430\u0439\u0442\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u0432\u044b\u0434\u0430\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0443, \u0435\u0441\u043b\u0438 \u043d\u0435\u0442, \u0442\u043e (2).<\/p>\n<\/li>\n
    2. \n
      \u041d\u0430\u0439\u0442\u0438 \u0431\u0438\u0442\u043e\u0432\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0439.<\/p>\n<\/li>\n
    3. \n
      \u041f\u0440\u043e\u0439\u0442\u0438\u0441\u044c \u0441\u043d\u043e\u0432\u0430 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f, \u043d\u0430\u0439\u0442\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0439<\/abbr><\/strong>.<\/p>\n<\/li>\n
    4. \n
      \u0412\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u043c\u0435\u0436\u0434\u0443 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0438 \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u043c.<\/p>\n<\/li>\n
    5. \n
      \u0421\u0432\u044f\u0437\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438, \u043e\u0434\u0438\u043d \u0438\u0437 \u043d\u0438\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d \u043d\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0434\u0440\u0443\u0433\u043e\u0439 \u043d\u0430 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0443\u044e(\u0438\u0437 \u043f. 3). <\/p>\n<\/li>\n<\/ol>\n
      void Patricia::Add(const std::string& key, int value){     if(!root){         root = new Node(key, value, 0);         root->left = root;         return;     }      Node *foundNode = Search(key);     if(foundNode->key == key)         throw std::runtime_error(\"\\t\\\"\" + key + \"\\\" already exist!\\n\");<\/code><\/pre>\n
      \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u043c\u0435\u0442\u043e\u0434\u0435 \u044f \u0443\u0436\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u044e \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043a\u043e\u0440\u043d\u044f, \u0435\u0441\u043b\u0438 \u043e\u043d \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u0441\u043e\u0437\u0434\u0430\u044e \u0438 \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e, \u0438\u043d\u0430\u0447\u0435 \u043d\u0430\u0445\u043e\u0436\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u044e \u043a\u043b\u044e\u0447 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0441 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0439, \u0435\u0441\u043b\u0438 \u0440\u0430\u0432\u043d\u044b, \u0442\u043e \u0432\u044b\u0434\u0430\u044e \u043e\u0448\u0438\u0431\u043a\u0443.<\/p>\n
      bool run = true;     size_t charIndex = 0;     while(run){         char foundedKey = (foundNode->key.size() > charIndex                             ? foundNode->key[charIndex] : '\\0');         char inputKey   = (key.size() > charIndex ? key[charIndex] : '\\0');         for(size_t i = 0; i < BIT_COUNT; ++i){             bool foundedKeyBit = foundedKey >> (BIT_COUNT - 1 - i) & 1;             bool inputKeyBit = inputKey >> (BIT_COUNT - 1 - i) & 1;             if(foundedKeyBit != inputKeyBit){                 Insert(key, value, charIndex * BIT_COUNT + i + 1);                 run = false;                 break;             }         }         ++charIndex;     }<\/code><\/pre>\n
      Run \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0444\u043b\u0430\u0433\u043e\u043c \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0446\u0438\u043a\u043b\u0430 while, charIndex<\/code> — \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0434\u043e \u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u043a\u043b\u044e\u0447\u0435\u0439, \u043d\u0443\u0436\u0435\u043d, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0432\u0441\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0438\u0437 \u043a\u043b\u044e\u0447\u0435\u0439. foundedKey<\/code> — \u0431\u0435\u0440\u0435\u0442 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0437 \u043a\u043b\u044e\u0447\u0430 \u0443\u0437\u043b\u0430, \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0435\u0440\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u043b\u0438 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u043a\u043b\u044e\u0447\u0430, \u0435\u0441\u043b\u0438 \u043d\u0435\u0442, \u0442\u043e \u0431\u0435\u0440\u0435\u043c \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443, \u0438\u043d\u0430\u0447\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b '\\0'<\/code>. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0441 inputKey<\/code> — \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0435\u0440\u0435\u0442 \u0441\u0438\u043c\u0432\u043e\u043b \u0438\u0437 \u0432\u0445\u043e\u0434\u044f\u0449\u0435\u0433\u043e \u043a\u043b\u044e\u0447\u0430. <\/p>\n
      \u0412 \u0446\u0438\u043a\u043b\u0435 for \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043f\u043e \u0431\u0438\u0442\u0430\u043c, \u0432\u0437\u044f\u0442\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0438 \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f. bool foundedKeyBit<\/code> — \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u0442 \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418<\/strong> \u0441 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0441 inputKeyBit<\/code>.<\/p>\n
      \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0431\u0438\u0442\u0430\u043c\u0438, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u0435\u0441\u0442\u044c, \u0442\u043e \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e Insert, \u043e\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0434\u0432\u0430 \u0446\u0438\u043a\u043b\u0430. \u0417\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u043c \u043d\u0430 \u044d\u0442\u043e\u043c \u043c\u0435\u0442\u043e\u0434 Add.<\/p>\n
      \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0443\u0437\u043b\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e<\/h2>\n
      \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u0435 \u043e\u0441\u043e\u0431\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043f\u043e\u0438\u0441\u043a\u0430, \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d \u043e\u0434\u0438\u043d \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043e\u0431 \u0438\u043d\u0434\u0435\u043a\u0441\u0435 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0431\u0438\u0442\u043e\u0432 \u0438 \u043e\u0434\u043d\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0430\u0441\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430:<\/p>\n
      void Patricia::Insert(const std::string& key, const int& value,                       const size_t& index){     Node *currentNode = root->left, *prevNode = root;      while(currentNode->index > prevNode->index && currentNode->index <= index){         size_t charIndex = (currentNode->index - 1) \/ BIT_COUNT;         \/\/ FindKey is less than need char         if(charIndex >= key.size()){             prevNode = currentNode;             \/\/ Only '0'             currentNode = currentNode->left;             continue;         }         char currentChar = key[charIndex]; \/\/ If findkey.size less than currentNode->index         int offset = (BIT_COUNT - 1 - ((currentNode->index - 1) % BIT_COUNT));         bool currentBit = (currentChar >> offset) & 1;          \/\/ Remember prevNode         prevNode = currentNode;         \/\/ If '1' go right, '0' go left         currentBit  ? currentNode = currentNode->right                     : currentNode = currentNode->left;     }<\/code><\/pre>\n
      \u0412 \u0438\u0442\u043e\u0433\u0435, \u043f\u043e\u043b\u0443\u0447\u0438\u043c, \u0447\u0442\u043e currentNode<\/code> — \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u0438\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u044b\u0448\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0430 prevNode<\/code> — \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u0438\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0438\u0436\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u0441\u0432\u044f\u0437\u0430\u0442\u044c \u0438\u0445:<\/p>\n
      char getCharFromKey = key[(index - 1) \/ BIT_COUNT];     bool getBit= getCharFromKey >> (BIT_COUNT - 1 - (index - 1) % BIT_COUNT) & 1;     Node *newNode = new Node(key, value, index);      if(prevNode->left == currentNode)         prevNode->left = newNode;     else         prevNode->right = newNode;      getBit  ? (newNode->right = newNode, newNode->left = currentNode)             : (newNode->left = newNode, newNode->right = currentNode); }<\/code><\/pre>\n
      \u0422\u0430\u043a \u043a\u0430\u043a \u0443 \u043d\u0430\u0441 \u0432 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u0445 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0432\u0441\u0435 3 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u044b, \u0442\u043e getCharFromKey<\/code> \u0440\u0430\u0432\u0435\u043d \u0441\u0438\u043c\u0432\u043e\u043b\u0443 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 (index - 1) \/ BIT_COUNT<\/code>. \u0422\u0430\u043a\u0436\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0438 \u0431\u0438\u0442 \u0438\u0437 \u0441\u0438\u043c\u0432\u043e\u043b\u0430. \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u0442\u0440\u0435\u043c\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438.<\/p>\n
      prevNode<\/code> — \u044d\u0442\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u0430-\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u0434\u043e \u0435\u0433\u043e \u0441\u0432\u044f\u0437\u0430\u0442\u044c \u0441 \u0440\u0435\u0431\u0435\u043d\u043a\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e prevNode->left == currentNode<\/code>, \u0435\u0441\u043b\u0438 true<\/code>, \u0442\u043e \u043e\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0443\u0445\u043e\u0434\u0438\u043c \u0432\u043b\u0435\u0432\u043e \u0438 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u043c \u0432 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b, \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0441 \u043d\u043e\u0432\u044b\u043c \u0443\u0437\u043b\u043e\u043c.<\/p>\n
      \u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0430\u0434\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0438\u0437 getBit<\/code>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442 \u0431\u0438\u0442 \u0438\u0437 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0438\u043d\u0434\u0435\u043a\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b\u0441\u0447\u0438\u0442\u0430\u043b\u0438 \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 Add, \u0440\u0430\u0432\u0435\u043d true<\/code>, \u0442\u043e \u0442\u043e\u0433\u0434\u0430 \u043f\u0440\u0430\u0432\u044b\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d \u043d\u0430 \u0441\u0430\u043c\u043e\u0433\u043e \u0441\u0435\u0431\u044f, \u0430 \u043b\u0435\u0432\u044b\u0439 \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0438\u0439, \u0442\u043e \u0435\u0441\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0443-\u0440\u0435\u0431\u0435\u043d\u043a\u0430. \u0418\u043d\u0430\u0447\u0435 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442. \u041f\u0440\u0438\u0432\u0435\u0434\u0443 \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e:<\/p>\n
      \u041c\u044b \u0445\u043e\u0442\u0438\u043c \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u044e_1 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u043a\u043b\u044e\u0447\u043e\u043c «n» — 01110.<\/p>\n
      \"\u0421\u0438\u043d\u0438\u043c
      \u0421\u0438\u043d\u0438\u043c — \u0441\u0442\u0440\u0435\u043b\u043a\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u043f\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c \u041a\u0440\u0430\u0441\u043d\u044b\u043c — \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430<\/figcaption><\/figure>\n
      \u041f\u043e\u0438\u0441\u043a \u0432\u044b\u0434\u0430\u043b \u043d\u0430\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 — \u0432\u0435\u0440\u0448\u0438\u043d\u0443 «l» \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 2. \u0418\u0449\u0435\u043c \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u044f \u0432 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u043c \u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0431\u0438\u0442\u0430\u0445. l — 01100, n — 01110, \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0435 \u0432 4 \u0431\u0438\u0442\u0435. \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e Insert.<\/p>\n
      \"\u0421\u0438\u043d\u0438\u043c
      \u0421\u0438\u043d\u0438\u043c — \u0441\u0442\u0440\u0435\u043b\u043a\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u0416\u0435\u043b\u0442\u044b\u0439 — \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0417\u0435\u043b\u0435\u043d\u044b\u0439 — \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0440\u0435\u0431\u0435\u043d\u043e\u043a<\/figcaption><\/figure>\n
      \u0424\u0443\u043d\u043a\u0446\u0438\u044f Insert \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0434\u0432\u0435 \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043c\u0435\u0436\u0434\u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043d\u0430\u0434\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u0443\u044e. \u0417\u0435\u043b\u0435\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0438\u043c\u0435\u0435\u0442 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432\u044b\u0448\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e(4), \u0430 \u0436\u0435\u043b\u0442\u0430\u044f — \u043d\u0438\u0436\u0435.<\/p>\n
      <\/figcaption><\/figure>\n
      \u0424\u0443\u0445… \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u043c\u043d\u043e\u0436\u043a\u043e \u043e\u0442\u0434\u043e\u0445\u043d\u0435\u043c, \u0431\u0443\u043a\u0432\u0430\u043b\u044c\u043d\u043e \u043d\u0430 5 \u0441\u0435\u043a\u0443\u043d\u0434, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0437 \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n
      \u0424\u0443\u043d\u043a\u0446\u0438\u044f At<\/h2>\n
      int& Patricia::At(const std::string& findKey) const{     if(!root)         throw std::runtime_error(\"\\t\\\"\" + findKey + \"\\\" hadn't found!\\n\");      Node* get = Search(findKey);      if(get->key == findKey)         return get->value;      throw std::runtime_error(\"\\t\\\"\" + findKey + \"\\\" hadn't found!\\n\"); }<\/code><\/pre>\n
      \u042f \u0434\u0443\u043c\u0430\u044e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u043d\u0435\u0447\u0435\u0433\u043e, \u043c\u044b \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c, \u0434\u0430\u043b\u044c\u0448\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e\u0438\u0441\u043a\u0430, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u0438 — \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043d\u0430\u0447\u0435 \u043e\u0448\u0438\u0431\u043a\u0443.<\/p>\n
      \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435, \u0442\u0430\u043a \u043a\u0430\u043a \u044f \u0443\u0432\u0435\u0440\u0435\u043d \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c, \u0430 \u043d\u0435 \u0443\u0434\u0430\u043b\u0438\u0442\u0441\u044f.<\/p>\n
      \u041d\u0443, \u043e\u0442\u0434\u043e\u0445\u043d\u0443\u043b\u0438, \u0442\u0435\u043f\u0435\u0440\u044c \u0441\u0430\u043c\u043e\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u0435 — \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435. \u0417\u0434\u0435\u0441\u044c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 4 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430:<\/p>\n
        \n
      1. \n
        \u0415\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b — \u043a\u043e\u0440\u0435\u043d\u044c \u0438 \u043e\u043d \u043e\u0434\u0438\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u0442\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u0438 \u0434\u0435\u043b\u0430\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c nullptr<\/code>.<\/p>\n<\/li>\n
      2. \n
        \u0415\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b — \u043b\u0438\u0441\u0442<\/abbr>, \u0442\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0441 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u043c\u0441\u044f \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443.<\/p>\n<\/li>\n
      3. \n
        \u0415\u0441\u043b\u0438 \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446<\/abbr> \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 — \u043b\u0438\u0441\u0442, \u0442\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0432\u043b\u0430\u0434\u0435\u043b\u044c\u0446\u0430 \u0441 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c.<\/p>\n<\/li>\n
      4. \n
        \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043d\u0430\u0439\u0442\u0438 3 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0410 — \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b, \u0411 — \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0412 — \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446 \u0432\u043b\u0430\u0434\u0435\u043b\u044c\u0446\u0430 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<\/p>\n<\/li>\n<\/ol>\n
        <\/figcaption><\/figure>\n
        \u0412 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0432\u044b\u0448\u0435 \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443 «t», \u0435\u0435 \u0436\u0435 \u0431\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0410, \u0435\u0435 \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 «z», \u043e\u043d\u0430 \u0436\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0411, \u0435\u0435 \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 «y», \u043e\u043d\u0430 \u0436\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0412. \u0422\u0435\u043f\u0435\u0440\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0410:<\/p>\n
          \n
        1. \n
          \u041a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0411 \u0432 \u0443\u0437\u0435\u043b \u0410.<\/p>\n<\/li>\n
        2. \n
          \u0421\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0443\u0437\u043b\u0430 \u0411 \u0441 \u0440\u0435\u0431\u0435\u043d\u043a\u043e\u043c \u0443\u0437\u043b\u0430 \u0411.<\/p>\n<\/li>\n
        3. \n
          \u041f\u0435\u0440\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0412 \u0441 \u0411 \u043d\u0430 \u0410.<\/p>\n<\/li>\n
        4. \n
          \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0411.<\/p>\n<\/li>\n<\/ol>\n
          <\/figcaption><\/figure>\n
          \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0442\u0430\u043a\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e. \u041d\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u0430 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043d\u0430\u0434\u043e \u043b\u0438\u0431\u043e \u0438\u043c\u0435\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0432 \u0441\u0430\u043c\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043b\u0438\u0431\u043e \u043a\u0430\u043a-\u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f. \u0422\u0430\u043a \u043a\u0430\u043a \u044f \u0434\u0435\u043b\u0430\u043b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u044e, \u0442\u043e \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0435 \u0434\u0435\u043b\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u0432\u0435\u0434\u044c \u0442\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 3 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0447\u0435\u0440\u0435\u0437 \u043a\u043e\u0440\u0442\u0435\u0436\u0438, \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0438\u043a\u0430\u043a \u043e\u0441\u043e\u0431\u043e \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u043b\u0430\u0441\u044c:<\/p>\n
          std::tuple<Patricia::Node*, Patricia::Node*, Patricia::Node*>                       Patricia::SearchE(const std::string& findKey) const{     Node *currentNode = root->left, *prevNode = root, *prevPrevNode = root;     while(currentNode->index > prevNode->index){         size_t charIndex = (currentNode->index - 1) \/ BIT_COUNT;      \/\/ FindKey is less than need char     if(charIndex &gt;= findKey.size()){         prevPrevNode = prevNode;         prevNode = currentNode;         \/\/ Only '0'         currentNode = currentNode-&gt;left;         continue;     }      char currentChar = findKey[charIndex];\/\/ If findkey.size less than currentNode-&gt;index     int offset = (BIT_COUNT - 1 - ((currentNode-&gt;index - 1) % BIT_COUNT));     bool currentBit = (currentChar &gt;&gt; offset) &amp; 1;      \/\/ Remember prevNode &amp; prevPrevNove     prevPrevNode = prevNode;     prevNode = currentNode;     \/\/ If '1' go right, '0' go left     currentBit  ? currentNode = currentNode-&gt;right                 : currentNode = currentNode-&gt;left; }  return std::make_tuple(currentNode, prevNode, prevPrevNode);  }<\/code><\/pre>\n
          \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, \u0447\u0442\u043e\u0431 \u043d\u0435 \u0441\u043b\u043e\u043c\u0430\u0442\u044c \u043f\u0441\u0438\u0445\u0438\u043a\u0443 \u0441:<\/p>\n
          void Patricia::Erase(const std::string& key){     if(!root)         throw std::runtime_error(\"\\t\\\"\" + key + \"\\\" hadn't found!\\n\");      \/\/ Get delete node, owner delete node and parent owner     std::tuple<Node*, Node*, Node*> delOwnerParentTuple = SearchE(key);     \/\/ A     Node *deleteNode = std::get<0>(delOwnerParentTuple);     \/\/ \u0411     Node *ownerDeleteNode = std::get<1>(delOwnerParentTuple);     \/\/ \u0411 parent     Node *parentOwnerDeleteNode = std::get<2>(delOwnerParentTuple);      if(deleteNode->key != key)         throw std::runtime_error(\"\\t\\\"\" + key + \"\\\" hadn't found!\\n\");          \/\/ If delete node is root and it's one     if(deleteNode == root && root->left == root){         delete root;         root = nullptr;         return;     }<\/code><\/pre>\n
          \u041f\u043e\u043a\u0430 \u0447\u0442\u043e \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0449\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043a\u043e\u0440\u0442\u0435\u0436 \u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0435\u0433\u043e \u0432\u043b\u0430\u0434\u0435\u043b\u044c\u0446\u0430 \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0432\u043b\u0430\u0434\u0435\u043b\u044c\u0446\u0430, \u0438\u0445 \u0436\u0435 \u0440\u0430\u0437\u044b\u043c\u0435\u043d\u043e\u0432\u044b\u0432\u0430\u0435\u043c \u0432 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438. \u0414\u0430\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043d\u0443\u0436\u043d\u044b\u0439 \u043a\u043b\u044e\u0447. \u0414\u0430\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 1 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435, \u043a\u043e\u0433\u0434\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u043e\u0434\u0438\u043d \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u0435\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u0434\u0430\u043b\u0438\u0442\u044c.<\/p>\n
              \/\/ If delete node is leaf     if(ownerDeleteNode == deleteNode){         if(parentOwnerDeleteNode->right == deleteNode)             if(deleteNode->right == deleteNode)                 parentOwnerDeleteNode->right = deleteNode->left;             else                 parentOwnerDeleteNode->right = deleteNode->right;         else             if(deleteNode->right == deleteNode)                 parentOwnerDeleteNode->left = deleteNode->left;             else                 parentOwnerDeleteNode->left = deleteNode->right;         delete deleteNode;         return;     }      \/\/ Get owner owner delete node     std::tuple<Node*, Node*, Node*> ownerOwnerTuple =                                                 SearchE(ownerDeleteNode->key);     Node *ownerOwnerDelNode = std::get<1>(ownerOwnerTuple);      \/\/ Change item from owner delete node to delete node     deleteNode->key = ownerDeleteNode->key;     deleteNode->value = ownerDeleteNode->value;<\/code><\/pre>\n
          \u0415\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b — \u043b\u0438\u0441\u0442, \u0442\u043e \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0438 \u043f\u0440\u0435\u0434\u043a\u0430. \u0418\u043d\u0430\u0447\u0435 \u043e\u043f\u044f\u0442\u044c \u0438\u0449\u0435\u043c, \u043d\u043e \u0443\u0436\u0435 \u0443\u0437\u0435\u043b \u0411, \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0435\u0433\u043e \u0432\u043b\u0430\u0434\u0435\u043b\u0435\u0446, \u0432 \u043a\u043e\u0440\u0442\u0435\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u0448\u044c 2 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438 \u0440\u0430\u0437\u044b\u043c\u0435\u043d\u043e\u0432\u0430\u043d\u0438\u0438, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e std::get<1> \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 20. \u041c\u0435\u043d\u044f\u0435\u043c \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0410<\/abbr> \u043d\u0430 \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0411<\/abbr>.<\/p>\n
              \/\/ If owner delete node is leaf     if(ownerOwnerDelNode == ownerDeleteNode){         if(parentOwnerDeleteNode->right == ownerDeleteNode)             parentOwnerDeleteNode->right = deleteNode;         else             parentOwnerDeleteNode->left = deleteNode;     }     else{         \/\/ Tie parent owner delete node with child         if(parentOwnerDeleteNode->right == ownerDeleteNode)             if(ownerDeleteNode->right == deleteNode)                 parentOwnerDeleteNode->right = ownerDeleteNode->left;             else                 parentOwnerDeleteNode->right = ownerDeleteNode->right;         else             if(ownerDeleteNode->right == deleteNode)                 parentOwnerDeleteNode->left = ownerDeleteNode->left;             else                 parentOwnerDeleteNode->left = ownerDeleteNode->right;          if(ownerOwnerDelNode->right == ownerDeleteNode)             ownerOwnerDelNode->right = deleteNode;         else             ownerOwnerDelNode->left = deleteNode;     }     delete ownerDeleteNode; }<\/code><\/pre>\n
          \u0415\u0441\u043b\u0438 \u0443\u0437\u0435\u043b \u0411 — \u043b\u0438\u0441\u0442, \u0442\u043e \u0442\u043e\u0433\u0434\u0430 \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0441 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c. \u0418\u043d\u0430\u0447\u0435 \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0438 \u0440\u0435\u0431\u0435\u043d\u043a\u0430 \u0443\u0437\u043b\u0430 \u0411, \u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0412 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c \u043a \u0443\u0437\u043b\u0443 \u0410, \u0432 \u043a\u043e\u043d\u0446\u0435 \u0434\u0432\u0443\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0411.<\/p>\n
          \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0441\u0430\u043c\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 — \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043a\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0445\u043e\u0434\u0438\u0442\u044c \u0438\u0437 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u0447\u0442\u043e\u0431 \u043d\u0435 \u0431\u044b\u043b\u043e \u0443\u0442\u0435\u0447\u0435\u043a \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n
          \u0424\u0443\u043d\u043a\u0446\u0438\u044f Clear<\/h2>\n
          \u041e\u0434\u043d\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0443 \u043c\u0435\u043d\u044f \u0432 \u043f\u0443\u0431\u043b\u0438\u0447\u043d\u043e\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u0435, \u0434\u0440\u0443\u0433\u0430\u044f \u0432 \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u043e\u043c, \u044f \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b \u0432\u0441\u0435 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438:<\/p>\n
          void Patricia::Clear(){     if(!root)         return;     if(root != root->left)         ClearNode(root->left);     delete root;     root = nullptr; }<\/code><\/pre>\n
          \u041f\u0443\u0431\u043b\u0438\u0447\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u043a\u043e\u0440\u0435\u043d\u044c, \u0447\u0442\u043e \u043e\u043d \u043d\u0435 \u043e\u0434\u0438\u043d \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u0435\u0441\u043b\u0438 \u043d\u0435 \u043e\u0434\u0438\u043d, \u0442\u043e \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442 \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u043e\u0447\u0438\u0449\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430:<\/p>\n
          void Patricia::ClearNode(Node *node){     if(node->left->index > node->index)         ClearNode(node->left);     if(node->right->index > node->index)         ClearNode(node->right);      delete node; }<\/code><\/pre>\n
          \u041f\u0440\u0438\u0432\u0430\u0442\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430, \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442 \u0442\u0430\u043a\u043e\u0435 \u0436\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0434\u0435\u0442\u0435\u0439 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430, \u0430 \u043f\u043e\u0442\u043e\u043c \u0443\u0434\u0430\u043b\u044f\u0435\u0442 \u0441\u0430\u043c\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0443.<\/p>\n
          \u0424\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441<\/h2>\n
          \u0411\u0440\u0430\u0432\u043e, \u0442\u044b \u0434\u043e\u0448\u0435\u043b \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u043c\u0435\u043d\u0442\u0430 \u0438 \u043f\u043e\u0447\u0442\u0438 \u043d\u0435 \u0432\u044b\u0441\u0442\u0440\u0435\u043b\u0438\u043b \u0441\u0435\u0431\u0435 \u0432 \u043d\u043e\u0433\u0443, \u0434\u0430\u0432\u0430\u0439 \u043f\u043e\u0440\u0430\u0434\u0443\u0435\u043c\u0441\u044f, \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043d\u0430\u0448\u0435\u0439 \u043f\u0430\u0442\u0440\u0438\u0446\u0438\u0438:<\/p>\n
          \/\/ patr.hpp #pragma once #include <string> #include <tuple>  \/\/ Bits u need in one char const int BIT_COUNT = 5;  typedef class Patricia{ private:     struct Node;     Node *root = nullptr;     \/\/ Search but return 3 nodes     std::tuple<Node*, Node*, Node*> SearchE(const std::string& findKey) const;     \/\/ Search return only 1 node     Node* Search(const std::string& findKey) const;     \/\/ Insert node to tree     void Insert(const std::string& key, const int& value, const size_t& index);     void ClearNode(Node *node); public:     \/\/ Get value from map     int& At(const std::string& findKey) const;     \/\/ Create node with key value and insert to tree     void Add(const std::string& key, int value);     \/\/ Delete node from tree     void Erase(const std::string& key);     void Clear();     ~Patricia(){ Clear(); } } patr;<\/code><\/pre>\n
          \u0421\u043e\u0432\u043c\u0435\u0449\u0430\u0435\u043c \u0441 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c<\/h2>\n
          #include \"patr.hpp\" #include <iostream> #include <time.h>  int main(){     patr test;     std::string command;     time_t start = clock();     while(std::cin >> command && command != \"\\x4\"){         if(command == \"+\"){             std::string key; std::cin >> key;             int value; std::cin >> value;             try{                 test.Add(key, value);                 std::cout << \"\\tSuccessfully!\\n\";             }             catch(const std::runtime_error& e){                 std::cout << e.what();             }         }         else if(command == \"-\"){             std::string key; std::cin >> key;             try{                 test.Erase(key);                 std::cout << \"\\tSuccessfully!\\n\";             }             catch(const std::runtime_error& e){                 std::cout << e.what();             }         }         else if(command == \"clear\" || command == \"new\"){             test.Clear();         }         else if(command == \"get\"){             try{                 std::string key; std::cin >> key;                 std::cout << test.At(key) << '\\n';             }             catch(const std::runtime_error& e){                 std::cout << e.what();             }         }         else if(command != \"\\n\"){             std::cout << \"\\tCommand \\\"\" + command + \"\\\" isn't available\\n\";         }     }     std::cout << \"Time: \" << (double)(clock() - start)\/CLOCKS_PER_SEC << '\\n';     return 0; } <\/code><\/pre>\n
          \u0412\u0432\u043e\u0434\u0438\u043c \u043a\u043e\u043c\u0430\u043d\u0434\u044b(\u043c\u043e\u0436\u0435\u0442\u0435 \u0432\u0432\u0435\u0441\u0442\u0438 \u0441\u0432\u043e\u0438) \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0432\u0432\u0435\u0434\u0435\u043c Ctrl+D. \u041a\u043e\u043c\u0430\u043d\u0434\u044b:<\/p>\n