Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 1 trên tổng số 1 kết quả

Đề tài: Treap

Threaded View

  1. #1
    Ngày gia nhập
    11 2016
    Bài viết
    14

    Mặc định Treap

    C++ Code:
    1. #include <iostream>
    2. #include <queue> //// Use Queue is available in C ++
    3.  
    4. using namespace std;
    5.  
    6. // Node Cartesian tree.
    7. struct CTreapNode {
    8.     int Key; // Ключ.
    9.     int Priority; // Приоритет узла.
    10.     CTreapNode* Left; // Левый дочерний узел.
    11.     CTreapNode* Right; // Правый дочерний узел.
    12.  
    13.     CTreapNode(int _key, int _priority) : Key(_key), Priority(_priority),
    14.         Left(0), Right(0) {}
    15. };
    16.  
    17. // Class Cartesian tree.
    18. class CTreap {
    19. public:
    20.     // Constructor creates an empty tree.
    21.     CTreap() : root(0) {}
    22.     // The destructor deletes all the elements of the tree.
    23.     ~CTreap();
    24.  
    25.     // Add a node (key, priority) in the tree.
    26.     // key and priority should be unique by definition, the Cartesian tree.
    27.     void Insert(int key, int priority);
    28.     // Print the tree traversal console from left to right.
    29.  
    30.     int getMaxWidth();
    31.  
    32. private:
    33.     CTreapNode* root; // Tree root.
    34.  
    35.     void deleteSubTree(CTreapNode* node);
    36.     void split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree);
    37.     CTreapNode* merge(CTreapNode* leftTree, CTreapNode* rightTree);
    38.     int getWidth(CTreapNode* root, int level);
    39.     int height(CTreapNode* node);
    40.  
    41. };
    42.  
    43. CTreap::~CTreap()
    44. {
    45.     deleteSubTree(root);
    46. }
    47.  
    48. // destroy the subtree whose root is node.
    49. void CTreap::deleteSubTree(CTreapNode* node)
    50. {
    51.     if (node == 0) {
    52.         // We got to the end of the tree.
    53.         return;
    54.     }
    55.  
    56.     deleteSubTree(node->Left);
    57.     node->Left = 0;
    58.     deleteSubTree(node->Right);
    59.     node->Right = 0;
    60.  
    61.     delete node;
    62. }
    63.  
    64. // Splits bunch into two parts.
    65. void CTreap::split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree)
    66. {
    67.     if (node == 0) {
    68.         leftTree = 0;
    69.         rightTree = 0;
    70.         return;
    71.     }
    72.  
    73.     if (node->Key < key) {
    74.         split(node->Right, key, node->Right, rightTree);
    75.         leftTree = node;
    76.     }
    77.     else {
    78.         split(node->Left, key, leftTree, node->Left);
    79.         rightTree = node;
    80.     }
    81. }
    82.  
    83. //merges the two Cartesian tree into one.Elements in leftTree elements should be less rightTree.
    84. CTreapNode* CTreap::merge(CTreapNode* leftTree, CTreapNode* rightTree)
    85. {
    86.     if (leftTree == 0) {
    87.         return rightTree;
    88.     }
    89.     if (rightTree == 0) {
    90.         return leftTree;
    91.     }
    92.  
    93.     if (rightTree->Priority > leftTree->Priority) {
    94.         rightTree->Left = merge(leftTree, rightTree->Left);
    95.         return rightTree;
    96.     }
    97.     else {
    98.         leftTree->Right = merge(leftTree->Right, rightTree);
    99.         return leftTree;
    100.     }
    101. }
    102.  
    103. // Implemented inefficient version of the insert.
    104. void CTreap::Insert(int key, int priority)
    105. {
    106.     if (root == 0) {
    107.         root = new CTreapNode(key, priority);
    108.         return;
    109.     }
    110.  
    111.     CTreapNode* leftTree;
    112.     CTreapNode* rightTree;
    113.     split(root, key, leftTree, rightTree);
    114.  
    115.     root = merge(leftTree, new CTreapNode(key, priority));
    116.     root = merge(root, rightTree);
    117. }
    118.  
    119.  
    120. int CTreap::height(CTreapNode* node)
    121. {
    122.     if (node == NULL)
    123.         return 0;
    124.     else
    125.     {
    126.         // compute the height of each subtree.
    127.         int lHeight = height(node->Left);
    128.         int rHeight = height(node->Right);
    129.         // use the larger one.
    130.  
    131.         return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);
    132.     }
    133. }
    134.  
    135. int CTreap::getMaxWidth()
    136. {
    137.     int maxWidth = 0;
    138.     int width;
    139.     int h = height(root);
    140.     int i;
    141.  
    142. // Get width of each level and compare the width with maximum width so far.
    143.     for (i = 1; i <= h; i++)
    144.     {
    145.         width = getWidth(root, i);
    146.         if (width > maxWidth)
    147.             maxWidth = width;
    148.     }
    149.  
    150.     return maxWidth;
    151. }
    152.  
    153. // Get width of a given level
    154. int CTreap::getWidth(CTreapNode* root, int level)
    155. {
    156.  
    157.     if (root == NULL)
    158.         return 0;
    159.  
    160.     if (level == 1)
    161.         return 1;
    162.  
    163.     else if (level > 1)
    164.         return getWidth(root->Left, level - 1) +
    165.         getWidth(root->Right, level - 1);
    166. }
    Đã được chỉnh sửa lần cuối bởi MHoang : 30-11-2016 lúc 09:40 AM. Lý do: Đưa vào khung mã

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn