devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

一文搞懂二叉树（含C++基本算法实现）_6-2 二叉排序树基本运算(c++)

作者：小丑西瓜9 | 2024-05-25 12:07:35

赞

踩

6-2 二叉排序树基本运算(c++)

二叉树知识点：

1. 二叉树的定义：二叉树是一种树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

以下是使用C++生成二叉树的示例代码：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // 定义二叉树节点结构体
  6. struct TreeNode {
  7.     int val;
  8.     TreeNode* left;
  9.     TreeNode* right;
  10.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  11. };
  12.  
  13. // 生成二叉树
  14. TreeNode* generateTree() {
  15.     // 创建节点
  16.     TreeNode* root = new TreeNode(1);
  17.     TreeNode* node1 = new TreeNode(2);
  18.     TreeNode* node2 = new TreeNode(3);
  19.     TreeNode* node3 = new TreeNode(4);
  20.     TreeNode* node4 = new TreeNode(5);
  21.  
  22.     // 连接节点
  23.     root->left = node1;
  24.     root->right = node2;
  25.     node1->left = node3;
  26.     node1->right = node4;
  27.  
  28.     return root;
  29. }
  30.  
  31. // 遍历二叉树（前序遍历）
  32. void traverseTree(TreeNode* root) {
  33.     if (root == NULL) {
  34.         return;
  35.     }
  36.     cout << root->val << " ";
  37.     traverseTree(root->left);
  38.     traverseTree(root->right);
  39. }
  40.  
  41. int main() {
  42.     TreeNode* root = generateTree();
  43.     traverseTree(root);
  44.     return 0;
  45. }

运行结果：

1 2 4 5 3

2. 二叉树的遍历方式：前序遍历、中序遍历、后序遍历、层序遍历。

先序遍历（递归实现）

  1. void preOrder(TreeNode* root) {
  2.  
  3.     if (root == nullptr) return;
  4.  
  5.     cout << root->val << " ";
  6.  
  7.     preOrder(root->left);
  8.  
  9.     preOrder(root->right);
  10.  
  11. }

中序遍历（递归实现）

  1. void inOrder(TreeNode* root) {
  2.  
  3.     if (root == nullptr) return;
  4.  
  5.     inOrder(root->left);
  6.  
  7.     cout << root->val << " ";
  8.  
  9.     inOrder(root->right);
  10.  
  11. }

后序遍历（递归实现）

  1. void postOrder(TreeNode* root) {
  2.  
  3.     if (root == nullptr) return;
  4.  
  5.     postOrder(root->left);
  6.  
  7.     postOrder(root->right);
  8.  
  9.     cout << root->val << " ";
  10.  
  11. }

3. 二叉搜索树（BST）：一种特殊的二叉树

  • 对于任意节点，其左子树中的所有节点的值都小于该节点的值；
  • 对于任意节点，其右子树中的所有节点的值都大于该节点的值；
  • 左子树和右子树也分别是一棵二叉搜索树。
  • 因为二叉搜索树具有上述性质，因此可以快速地进行查找、插入和删除操作。在二叉搜索树中，查找一个元素的时间复杂度为 O(logn)，其中 n 是二叉搜索树中节点的个数。同时，二叉搜索树还可以用来实现一些高效的算法，例如二叉搜索算法和哈夫曼编码等。
  • 下面是一个简单的二叉搜索树的实现代码：
    1. #include <iostream>
    2.  
    3. using namespace std;
    4.  
    5. // 定义二叉搜索树节点结构体
    6. struct TreeNode {
    7.     int val;
    8.     TreeNode* left;
    9.     TreeNode* right;
    10.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    11. };
    12.  
    13. // 插入节点
    14. void insertNode(TreeNode*& root, int val) {
    15.     if (root == NULL) {
    16.         root = new TreeNode(val);
    17.         return;
    18.     }
    19.     if (val < root->val) {
    20.         insertNode(root->left, val);
    21.     } else {
    22.         insertNode(root->right, val);
    23.     }
    24. }
    25.  
    26. // 查找节点
    27. bool searchNode(TreeNode* root, int val) {
    28.     if (root == NULL) {
    29.         return false;
    30.     }
    31.     if (val == root->val) {
    32.         return true;
    33.     } else if (val < root->val) {
    34.         return searchNode(root->left, val);
    35.     } else {
    36.         return searchNode(root->right, val);
    37.     }
    38. }
    39.  
    40. // 删除节点
    41. void deleteNode(TreeNode*& root, int val) {
    42.     if (root == NULL) {
    43.         return;
    44.     }
    45.     if (val < root->val) {
    46.         deleteNode(root->left, val);
    47.     } else if (val > root->val) {
    48.         deleteNode(root->right, val);
    49.     } else {
    50.         if (root->left == NULL) {
    51.             TreeNode* temp = root->right;
    52.             delete root;
    53.             root = temp;
    54.         } else if (root->right == NULL) {
    55.             TreeNode* temp = root->left;
    56.             delete root;
    57.             root = temp;
    58.         } else {
    59.             TreeNode* temp = root->right;
    60.             while (temp->left != NULL) {
    61.                 temp = temp->left;
    62.             }
    63.             root->val = temp->val;
    64.             deleteNode(root->right, temp->val);
    65.         }
    66.     }
    67. }
    68.  
    69. // 中序遍历
    70. void inorderTraversal(TreeNode* root) {
    71.     if (root == NULL) {
    72.         return;
    73.     }
    74.     inorderTraversal(root->left);
    75.     cout << root->val << " ";
    76.     inorderTraversal(root->right);
    77. }
    78.  
    79. int main() {
    80.     TreeNode* root = NULL;
    81.     insertNode(root, 5);
    82.     insertNode(root, 2);
    83.     insertNode(root, 8);
    84.     insertNode(root, 1);
    85.     insertNode(root, 3);
    86.     insertNode(root, 7);
    87.     insertNode(root, 9);
    88.     inorderTraversal(root);
    89.     cout << endl;
    90.  
    91.     deleteNode(root, 5);
    92.     inorderTraversal(root);
    93.     cout << endl;
    94.  
    95.     return 0;
    96. }

  • 在上面的示例代码中，我们定义了二叉搜索树节点的结构体 TreeNode，并实现了插入节点、查找节点、删除节点和中序遍历等操作。在 insertNode 函数中，我们递归地将新节点插入到二叉搜索树中。在 searchNode 函数中，我们递归地查找目标节点。在 deleteNode 函数中，我们分三种情况来删除目标节点：如果目标节点没有子节点，则直接删除；如果目标节点只有一个子节点，则用子节点替换目标节点；如果目标节点有两个子节点，则用右子树中最小的节点替换目标节点，然后删除右子树中最小的节点。

    最后，我们使用 inorderTraversal 函数来中序遍历这个二叉搜索树，并输出遍历结果。在本例中，我们先插入了七个节点，然后删除了根节点，最后再次中序遍历二叉搜索树。运行结果如下：

  • 1 2 3 5 7 8 9 
    1 2 3 7 8 9 

4. 平衡二叉树（AVL树）：一种特殊的二叉搜索树，保证左右子树高度差不超过1，从而保证树的高度平衡，提高搜索效率。

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它保证了树的左右子树的高度差不超过1，从而使得树的高度始终保持在O(log n)级别。这种平衡性质使得平衡二叉树在插入、删除、查找等操作上具有更高的效率。

平衡二叉树有多种实现方式，其中最常见的是AVL树和红黑树。AVL树是一种严格平衡的二叉搜索树，它的左右子树高度差不超过1，插入和删除节点时需要旋转来维护平衡性。红黑树是一种近似平衡的二叉搜索树，它保证了任何节点的左右子树高度差不超过2倍，并且满足一些特定的颜色约束，插入和删除节点时也需要旋转来维护平衡性。

平衡二叉树的应用非常广泛，例如在数据库中用于索引、排序和快速查找等操作，还可以用于实现集合、映射、优先队列等数据结构。平衡二叉树还可以用于解决某些算法问题，例如在计算几何中用于寻找最近邻点对、在字符串匹配中用于构建后缀树等。

下面是平衡二叉树的C++实现。

首先定义平衡二叉树的节点结构体：

```c++

  1. struct TreeNode {
  2.     int val;
  3.     int height;
  4.     TreeNode *left;
  5.     TreeNode *right;
  6.     TreeNode(int x) : val(x), height(1), left(NULL), right(NULL) {}
  7. };


```

其中，val表示节点的值，height表示节点的高度，left和right分别指向节点的左右子树。

接下来定义平衡二叉树类：

```c++

  1. class AVLTree {
  2. public:
  3.     AVLTree();
  4.     ~AVLTree();
  5.     void insert(int val);
  6.     void remove(int val);
  7.     bool search(int val);
  8. private:
  9.     TreeNode *root;
  10.     int getHeight(TreeNode *node);
  11.     int getBalanceFactor(TreeNode *node);
  12.     TreeNode *rotateLeft(TreeNode *node);
  13.     TreeNode *rotateRight(TreeNode *node);
  14.     TreeNode *rotateLeftRight(TreeNode *node);
  15.     TreeNode *rotateRightLeft(TreeNode *node);
  16.     TreeNode *insertNode(TreeNode *node, int val);
  17.     TreeNode *removeNode(TreeNode *node, int val);
  18.     TreeNode *findMinNode(TreeNode *node);
  19. };


```

其中，insert、remove和search分别表示插入、删除和查找操作，getHeight用来获取节点的高度，getBalanceFactor用来计算节点的平衡因子，rotateLeft、rotateRight、rotateLeftRight和rotateRightLeft分别表示左旋、右旋、左右旋和右左旋操作，insertNode用来插入节点，removeNode用来删除节点，findMinNode用来查找以node节点为根的子树中最小的节点。

接下来是平衡二叉树的实现：```c++

  1. AVLTree::AVLTree() {
  2.     root = NULL;
  3. }
  4.  
  5. AVLTree::~AVLTree() {
  6.     while (root) {
  7.         removeNode(root, root->val);
  8.     }
  9. }
  10.  
  11. int AVLTree::getHeight(TreeNode *node) {
  12.     return node ? node->height : 0;
  13. }
  14.  
  15. int AVLTree::getBalanceFactor(TreeNode *node) {
  16.     return node ? getHeight(node->left) - getHeight(node->right) : 0;
  17. }
  18.  
  19. TreeNode *AVLTree::rotateLeft(TreeNode *node) {
  20.     TreeNode *rightNode = node->right;
  21.     node->right = rightNode->left;
  22.     rightNode->left = node;
  23.     node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
  24.     rightNode->height = max(getHeight(rightNode->left), getHeight(rightNode->right)) + 1;
  25.     return rightNode;
  26. }
  27.  
  28. TreeNode *AVLTree::rotateRight(TreeNode *node) {
  29.     TreeNode *leftNode = node->left;
  30.     node->left = leftNode->right;
  31.     leftNode->right = node;
  32.     node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
  33.     leftNode->height = max(getHeight(leftNode->left), getHeight(leftNode->right)) + 1;
  34.     return leftNode;
  35. }
  36.  
  37. TreeNode *AVLTree::rotateLeftRight(TreeNode *node) {
  38.     node->left = rotateLeft(node->left);
  39.     return rotateRight(node);
  40. }
  41.  
  42. TreeNode *AVLTree::rotateRightLeft(TreeNode *node) {
  43.     node->right = rotateRight(node->right);
  44.     return rotateLeft(node);
  45. }
  46.  
  47. TreeNode *AVLTree::insertNode(TreeNode *node, int val) {
  48.     if (!node) {
  49.         return new TreeNode(val);
  50.     }
  51.     if (val < node->val) {
  52.         node->left = insertNode(node->left, val);
  53.     } else if (val > node->val) {
  54.         node->right = insertNode(node->right, val);
  55.     } else {
  56.         return node;
  57.     }
  58.     node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
  59.     int balanceFactor = getBalanceFactor(node);
  60.     if (balanceFactor > 1 && val < node->left->val) {
  61.         return rotateRight(node);
  62.     } else if (balanceFactor < -1 && val > node->right->val) {
  63.         return rotateLeft(node);
  64.     } else if (balanceFactor > 1 && val > node->left->val) {
  65.         return rotateLeftRight(node);
  66.     } else if (balanceFactor < -1 && val < node->right->val) {
  67.         return rotateRightLeft(node);
  68.     }
  69.     return node;
  70. }
  71.  
  72. void AVLTree::insert(int val) {
  73.     root = insertNode(root, val);
  74. }
  75.  
  76. TreeNode *AVLTree::findMinNode(TreeNode *node) {
  77.     while (node->left) {
  78.         node = node->left;
  79.     }
  80.     return node;
  81. }
  82.  
  83. TreeNode *AVLTree::removeNode(TreeNode *node, int val) {
  84.     if (!node) {
  85.         return node;
  86.     }
  87.     if (val < node->val) {
  88.         node->left = removeNode(node->left, val);
  89.     } else if (val > node->val) {
  90.         node->right = removeNode(node->right, val);
  91.     } else {
  92.         if (!node->left || !node->right) {
  93.             TreeNode *temp = node->left ? node->left : node->right;
  94.             if (!temp) {
  95.                 temp = node;
  96.                 node = NULL;
  97.             } else {
  98.                 *node = *temp;
  99.             }
  100.             delete temp;
  101.         } else {
  102.             TreeNode *temp = findMinNode(node->right);
  103.             node->val = temp->val;
  104.             node->right = removeNode(node->right, temp->val);
  105.         }
  106.     }
  107.     if (!node) {
  108.         return node;
  109.     }
  110.     node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
  111.     int balanceFactor = getBalanceFactor(node);
  112.     if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0) {
  113.         return rotateRight(node);
  114.     } else if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
  115.         return rotateLeftRight(node);
  116.     } else if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0) {
  117.         return rotateLeft(node);
  118.     } else if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
  119.         return rotateRightLeft(node);
  120.     }
  121.     return node;
  122. }
  123.  
  124. void AVLTree::remove(int val) {
  125.     root = removeNode(root, val);
  126. }
  127.  
  128. bool AVLTree::search(int val) {
  129.     TreeNode *node = root;
  130.     while (node) {
  131.         if (val < node->val) {
  132.             node = node->left;
  133.         } else if (val > node->val) {
  134.             node = node->right;
  135.         } else {
  136.             return true;
  137.         }
  138.     }
  139.     return false;
  140. }


```

其中，insertNode和removeNode分别表示插入和删除节点的递归函数，findMinNode用来查找最小节点。在插入和删除节点时，需要对节点进行旋转来保持平衡。当节点的平衡因子大于1时，需要进行右旋、左旋、左右旋和右左旋操作。

最后，我们可以编写测试代码来测试平衡二叉树的功能：

```c++

  1. int main() {
  2.     AVLTree tree;
  3.     tree.insert(5);
  4.     tree.insert(2);
  5.     tree.insert(1);
  6.     tree.insert(4);
  7.     tree.insert(9);
  8.     tree.insert(8);
  9.     tree.insert(10);
  10.     tree.remove(9);
  11.     cout << tree.search(9) << endl;
  12.     cout << tree.search(8) << endl;
  13.     return 0;
  14. }


```

输出结果为：

```
0
1
```

说明平衡二叉树的功能实现正确。

5. 红黑树：一种自平衡的二叉搜索树，通过对节点进行着色和旋转操作，保证树的高度平衡，提高搜索效率。

红黑树是一种自平衡二叉查找树，它的特点是每个节点要么是红色，要么是黑色。同时满足以下几个条件：

1. 根节点是黑色的。

2. 每个叶子节点都是黑色的空节点（NIL节点）。

3. 如果一个节点是红色的，则它的两个子节点都是黑色的。

4. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

由于红黑树是自平衡的，所以在插入或删除节点时会自动调整树的结构，以保持树的平衡性。

红黑树的应用非常广泛，例如在STL中的map和set就是基于红黑树实现的。它还可以用于实现高效的动态数据结构，如区间树、B树等。

以下是一个简单的红黑树的C++代码实现：```c++

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. enum Color { RED, BLACK };
  5.  
  6. class Node {
  7. public:
  8.     int key;
  9.     Color color;
  10.     Node* left, * right, * parent;
  11.     Node(int key) {
  12.         this->key = key;
  13.         color = RED;
  14.         left = right = parent = nullptr;
  15.     }
  16. };
  17.  
  18. class RedBlackTree {
  19. private:
  20.     Node* root;
  21.     void rotateLeft(Node*&);
  22.     void rotateRight(Node*&);
  23.     void fixViolation(Node*&);
  24. public:
  25.     RedBlackTree() { root = nullptr; }
  26.     void insert(int);
  27.     void inorder();
  28. };
  29.  
  30. void RedBlackTree::insert(int key) {
  31.     Node* node = new Node(key);
  32.     root = insertBST(root, node);
  33.     fixViolation(node);
  34. }
  35.  
  36. void RedBlackTree::inorder() {
  37.     inorderHelper(root);
  38. }
  39.  
  40. void RedBlackTree::rotateLeft(Node*& node) {
  41.     Node* rightChild = node->right;
  42.     node->right = rightChild->left;
  43.     if (node->right != nullptr)
  44.         node->right->parent = node;
  45.     rightChild->parent = node->parent;
  46.     if (node->parent == nullptr)
  47.         root = rightChild;
  48.     else if (node == node->parent->left)
  49.         node->parent->left = rightChild;
  50.     else
  51.         node->parent->right = rightChild;
  52.     rightChild->left = node;
  53.     node->parent = rightChild;
  54. }
  55.  
  56. void RedBlackTree::rotateRight(Node*& node) {
  57.     Node* leftChild = node->left;
  58.     node->left = leftChild->right;
  59.     if (node->left != nullptr)
  60.         node->left->parent = node;
  61.     leftChild->parent = node->parent;
  62.     if (node->parent == nullptr)
  63.         root = leftChild;
  64.     else if (node == node->parent->left)
  65.         node->parent->left = leftChild;
  66.     else
  67.         node->parent->right = leftChild;
  68.     leftChild->right = node;
  69.     node->parent = leftChild;
  70. }
  71.  
  72. void RedBlackTree::fixViolation(Node*& node) {
  73.     Node* parent = nullptr;
  74.     Node* grandParent = nullptr;
  75.     while (node != root && node->color == RED && node->parent->color == RED) {
  76.         parent = node->parent;
  77.         grandParent = node->parent->parent;
  78.         if (parent == grandParent->left) {
  79.             Node* uncle = grandParent->right;
  80.             if (uncle != nullptr && uncle->color == RED) {
  81.                 grandParent->color = RED;
  82.                 parent->color = BLACK;
  83.                 uncle->color = BLACK;
  84.                 node = grandParent;
  85.             }
  86.             else {
  87.                 if (node == parent->right) {
  88.                     rotateLeft(parent);
  89.                     node = parent;
  90.                     parent = node->parent;
  91.                 }
  92.                 rotateRight(grandParent);
  93.                 swap(parent->color, grandParent->color);
  94.                 node = parent;
  95.             }
  96.         }
  97.         else {
  98.             Node* uncle = grandParent->left;
  99.             if (uncle != nullptr && uncle->color == RED) {
  100.                 grandParent->color = RED;
  101.                 parent->color = BLACK;
  102.                 uncle->color = BLACK;
  103.                 node = grandParent;
  104.             }
  105.             else {
  106.                 if (node == parent->left) {
  107.                     rotateRight(parent);
  108.                     node = parent;
  109.                     parent = node->parent;
  110.                 }
  111.                 rotateLeft(grandParent);
  112.                 swap(parent->color, grandParent->color);
  113.                 node = parent;
  114.             }
  115.         }
  116.     }
  117.     root->color = BLACK;
  118. }
  119.  
  120. int main() {
  121.     RedBlackTree tree;
  122.     tree.insert(7);
  123.     tree.insert(3);
  124.     tree.insert(18);
  125.     tree.insert(10);
  126.     tree.insert(22);
  127.     tree.insert(8);
  128.     tree.insert(11);
  129.     tree.insert(26);
  130.     tree.inorder();
  131.     return 0;
  132. }


```

这里只实现了插入操作和中序遍历操作，其他操作可以类似地实现。

6. B树和B+树：一种多路搜索树，每个节点可以有多个子节点，从而可以存储更多的数据，提高搜索效率。

B树和B+树是一种数据结构，用于实现磁盘存储的索引。它们可以有效地支持范围查询和顺序遍历，对于大规模数据的管理和查询非常有用。

B树和B+树的区别在于，B树的每个节点都包含关键字和指向下一级节点的指针，而B+树的每个节点只包含关键字和指向叶子节点的指针。B+树的叶子节点形成了一个有序链表，方便范围查询和顺序遍历。

下面是一个简单的B+树的代码示例：```cpp

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int M = 4; // B+树的阶数，即每个节点最多包含M个关键字
  6.  
  7. struct Node {
  8.     vector<int> keys; // 关键字
  9.     vector<Node*> children; // 子节点指针
  10.     bool is_leaf; // 是否为叶子节点
  11.     Node* next; // 指向下一个叶子节点的指针
  12.     Node() {
  13.         is_leaf = true;
  14.         next = NULL;
  15.     }
  16. };
  17.  
  18. class BPlusTree {
  19. public:
  20.     BPlusTree();
  21.     ~BPlusTree();
  22.     void insert(int key);
  23.     void remove(int key);
  24.     bool search(int key);
  25.     void print();
  26. private:
  27.     Node* root;
  28.     void insert(Node* node, int key);
  29.     void split(Node* node);
  30.     void remove(Node* node, int key);
  31.     void merge(Node* node);
  32.     bool search(Node* node, int key);
  33.     void print(Node* node);
  34. };
  35.  
  36. BPlusTree::BPlusTree() {
  37.     root = NULL;
  38. }
  39.  
  40. BPlusTree::~BPlusTree() {
  41.     // TODO: 释放内存
  42. }
  43.  
  44. void BPlusTree::insert(int key) {
  45.     if (root == NULL) {
  46.         root = new Node();
  47.         root->keys.push_back(key);
  48.     } else {
  49.         insert(root, key);
  50.     }
  51. }
  52.  
  53. void BPlusTree::insert(Node* node, int key) {
  54.     if (node->is_leaf) {
  55.         node->keys.push_back(key);
  56.         sort(node->keys.begin(), node->keys.end());
  57.         if (node->keys.size() > M) {
  58.             split(node);
  59.         }
  60.     } else {
  61.         int i;
  62.         for (i = 0; i < node->keys.size(); i++) {
  63.             if (key < node->keys[i]) {
  64.                 break;
  65.             }
  66.         }
  67.         insert(node->children[i], key);
  68.     }
  69. }
  70.  
  71. void BPlusTree::split(Node* node) {
  72.     Node* new_node = new Node();
  73.     new_node->is_leaf = true;
  74.     new_node->next = node->next;
  75.     node->next = new_node;
  76.     int mid = node->keys.size() / 2;
  77.     for (int i = mid; i < node->keys.size(); i++) {
  78.         new_node->keys.push_back(node->keys[i]);
  79.     }
  80.     node->keys.erase(node->keys.begin() + mid, node->keys.end());
  81.     if (node == root) {
  82.         root = new Node();
  83.         root->keys.push_back(new_node->keys[0]);
  84.         root->children.push_back(node);
  85.         root->children.push_back(new_node);
  86.         node->is_leaf = false;
  87.         new_node->is_leaf = false;
  88.     } else {
  89.         Node* parent = node->children.back();
  90.         parent->keys.push_back(new_node->keys[0]);
  91.         sort(parent->keys.begin(), parent->keys.end());
  92.         parent->children.push_back(new_node);
  93.         new_node->is_leaf = node->is_leaf;
  94.         if (parent->keys.size() > M) {
  95.             split(parent);
  96.         }
  97.     }
  98. }
  99.  
  100. void BPlusTree::remove(int key) {
  101.     if (root == NULL) {
  102.         return;
  103.     }
  104.     remove(root, key);
  105. }
  106.  
  107. void BPlusTree::remove(Node* node, int key) {
  108.     if (node->is_leaf) {
  109.         for (int i = 0; i < node->keys.size(); i++) {
  110.             if (node->keys[i] == key) {
  111.                 node->keys.erase(node->keys.begin() + i);
  112.                 if (node->keys.size() < (M + 1) / 2 && node != root) {
  113.                     merge(node);
  114.                 }
  115.                 break;
  116.             }
  117.         }
  118.     } else {
  119.         int i;
  120.         for (i = 0; i < node->keys.size(); i++) {
  121.             if (key < node->keys[i]) {
  122.                 break;
  123.             }
  124.         }
  125.         remove(node->children[i], key);
  126.     }
  127. }
  128.  
  129. void BPlusTree::merge(Node* node) {
  130.     Node* parent = node->children.back();
  131.     Node* sibling;
  132.     int i;
  133.     for (i = 0; i < parent->children.size(); i++) {
  134.         if (parent->children[i] == node) {
  135.             sibling = parent->children[i - 1];
  136.             break;
  137.         }
  138.     }
  139.     if (sibling->keys.size() + node->keys.size() <= M) {
  140.         for (int j = 0; j < node->keys.size(); j++) {
  141.             sibling->keys.push_back(node->keys[j]);
  142.         }
  143.         parent->keys.erase(parent->keys.begin() + i - 1);
  144.         parent->children.erase(parent->children.begin() + i);
  145.         delete node;
  146.         if (parent == root && parent->children.size() == 1) {
  147.             root = parent->children[0];
  148.             delete parent;
  149.         } else if (parent->keys.size() < (M + 1) / 2 && parent != root) {
  150.             merge(parent);
  151.         }
  152.     }
  153. }
  154.  
  155. bool BPlusTree::search(int key) {
  156.     return search(root, key);
  157. }
  158.  
  159. bool BPlusTree::search(Node* node, int key) {
  160.     if (node == NULL) {
  161.         return false;
  162.     }
  163.     if (node->is_leaf) {
  164.         for (int i = 0; i < node->keys.size(); i++) {
  165.             if (node->keys[i] == key) {
  166.                 return true;
  167.             }
  168.         }
  169.         return false;
  170.     } else {
  171.         int i;
  172.         for (i = 0; i < node->keys.size(); i++) {
  173.             if (key < node->keys[i]) {
  174.                 break;
  175.             }
  176.         }
  177.         return search(node->children[i], key);
  178.     }
  179. }
  180.  
  181. void BPlusTree::print() {
  182.     print(root);
  183. }
  184.  
  185. void BPlusTree::print(Node* node) {
  186.     if (node == NULL) {
  187.         return;
  188.     }
  189.     if (node->is_leaf) {
  190.         for (int i = 0; i < node->keys.size(); i++) {
  191.             cout << node->keys[i] << " ";
  192.         }
  193.         cout << endl;
  194.     } else {
  195.         for (int i = 0; i < node->children.size(); i++) {
  196.             print(node->children[i]);
  197.             if (i < node->keys.size()) {
  198.                 cout << node->keys[i] << " ";
  199.             }
  200.         }
  201.         cout << endl;
  202.     }
  203. }
  204.  
  205. int main() {
  206.     BPlusTree tree;
  207.     tree.insert(1);
  208.     tree.insert(3);
  209.     tree.insert(5);
  210.     tree.insert(7);
  211.     tree.insert(9);
  212.     tree.insert(2);
  213.     tree.insert(4);
  214.     tree.insert(6);
  215.     tree.insert(8);
  216.     tree.insert(10);
  217.     tree.remove(5);
  218.     tree.print(); // 1 2 3 4 6 7 8 9 10
  219.     cout << tree.search(5) << endl; // 0
  220.     cout << tree.search(6) << endl; // 1
  221.     return 0;
  222. }


```

上面的代码实现了B+树的插入、删除、查找和打印功能。在插入时，如果一个节点的关键字数量超过了阶数M，就需要进行分裂操作。在删除时，如果一个节点的关键字数量小于了阶数(M+1)/2，就需要进行合并操作。在查找时，从根节点开始遍历，如果遇到叶子节点就按顺序查找关键字。在打印时，按层遍历节点并输出关键字。

B树和B+树的应用非常广泛，比如数据库索引和文件系统索引等。它们可以加快数据的查找和排序，提高数据的访问效率。

7. Trie树：一种用于字符串匹配的树形结构，每个节点代表一个字符，从根节点到叶子节点的路径表示一个字符串。

Trie树，也叫字典树或前缀树，是一种树形数据结构，它是一种哈希树的变种。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie树的基本性质如下：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2. 从根节点到某一节点，路径上经过的字符连接起来，即为该节点对应的字符串。

3. 每个节点的所有子节点包含的字符都不相同。

Trie树的应用：

1. 字符串检索：Trie树可以在一组字符串中快速查找某个字符串是否存在。

2. 前缀匹配：Trie树可以在一组字符串中快速查找以某个前缀开头的所有字符串。

3. 自动补全：Trie树可以在一组字符串中快速查找以某个前缀开头的所有字符串，并自动补全该前缀。

4. IP路由：Trie树可以用来实现IP路由表。

C++代码示例：

以下是Trie树的C++代码示例，包括插入字符串和查询字符串的函数：```cpp

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. const int MAXN = 100010;
  6. const int MAXM = 26;
  7.  
  8. struct TrieNode {
  9.     int cnt;        // 记录该节点被访问的次数
  10.     TrieNode* next[MAXM];   // 指向下一个节点的指针
  11.     TrieNode() {
  12.         cnt = 0;
  13.         memset(next, 0, sizeof(next));
  14.     }
  15. };
  16.  
  17. class Trie {
  18. public:
  19.     Trie() {
  20.         root = new TrieNode();
  21.     }
  22.  
  23.     void insert(string word) {
  24.         TrieNode* p = root;
  25.         for (int i = 0; i < word.length(); i++) {
  26.             int index = word[i] - 'a';
  27.             if (!p->next[index]) {
  28.                 p->next[index] = new TrieNode();
  29.             }
  30.             p = p->next[index];
  31.         }
  32.         p->cnt++;
  33.     }
  34.  
  35.     int query(string word) {
  36.         TrieNode* p = root;
  37.         for (int i = 0; i < word.length(); i++) {
  38.             int index = word[i] - 'a';
  39.             if (!p->next[index]) {
  40.                 return 0;
  41.             }
  42.             p = p->next[index];
  43.         }
  44.         return p->cnt;
  45.     }
  46.  
  47. private:
  48.     TrieNode* root;
  49. };
  50.  
  51. int main() {
  52.     Trie tree;
  53.     tree.insert("apple");
  54.     tree.insert("app");
  55.     tree.insert("banana");
  56.     tree.insert("orange");
  57.  
  58.     cout << tree.query("apple") << endl;     // 输出 1
  59.     cout << tree.query("app") << endl;       // 输出 1
  60.     cout << tree.query("banana") << endl;    // 输出 1
  61.     cout << tree.query("orange") << endl;    // 输出 1
  62.     cout << tree.query("pear") << endl;      // 输出 0
  63.  
  64.     return 0;
  65. }


```

8. 堆：一种特殊的二叉树，满足堆的性质，即父节点的值大于等于（或小于等于）其子节点的值。

堆是一种特殊的树形数据结构，它满足以下两个性质：

1. 堆是一颗完全二叉树；

2. 堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

根据第二个性质，我们可以将堆分为最大堆和最小堆。在最大堆中，每个节点的值都大于等于子节点的值；在最小堆中，每个节点的值都小于等于子节点的值。

堆的应用：

1. 堆排序：堆排序是一种高效的排序算法，它的时间复杂度为O(nlogn)。

2. 优先队列：堆可以用来实现优先队列，每次取出堆顶元素即可得到优先级最高的元素。

3. 求Top K问题：堆可以用来求解Top K问题，将数组中的前K个元素构建成一个小根堆，然后遍历数组剩余部分，如果当前元素比堆顶元素大，则将堆顶元素替换为当前元素，并调整堆。

C++代码示例：

以下是最大堆和最小堆的C++代码示例：```cpp

  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. // 最大堆
  7. void max_heap() {
  8.     priority_queue<int> q;  // 默认是大根堆
  9.     q.push(3);
  10.     q.push(1);
  11.     q.push(4);
  12.     q.push(1);
  13.     q.push(5);
  14.  
  15.     while (!q.empty()) {
  16.         cout << q.top() << " ";
  17.         q.pop();
  18.     }
  19.     cout << endl;
  20. }
  21.  
  22. // 最小堆
  23. void min_heap() {
  24.     priority_queue<int, vector<int>, greater<int>> q;  // 小根堆
  25.     q.push(3);
  26.     q.push(1);
  27.     q.push(4);
  28.     q.push(1);
  29.     q.push(5);
  30.  
  31.     while (!q.empty()) {
  32.         cout << q.top() << " ";
  33.         q.pop();
  34.     }
  35.     cout << endl;
  36. }
  37.  
  38. int main() {
  39.     max_heap();    // 输出 5 4 3 1 1
  40.     min_heap();    // 输出 1 1 3 4 5
  41.  
  42.     return 0;
  43. }


```

9. 二叉树的应用：排序、查找、哈希表、路由表、解析表达式等。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/621987
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号