树状数组笔记

**树状数组笔记**

树状数组是一种用于解决动态数据集问题的高效数据结构。它通过将数据组织成一个二叉树来实现快速查找、插入和删除操作。树状数组在许多应用中都有重要作用，例如数据库索引、缓存管理和计算机图形学等。

**树状数组的基本概念**

树状数组是一种特殊的二叉树，每个结点代表一个整数值。每个结点的左子树包含所有小于该结点值的整数，而右子树包含所有大于该结点值的整数。这样，通过遍历树状数组，我们可以快速找到满足某些条件的整数。

**树状数组的基本操作**

树状数组支持以下基本操作：

* **查找（Find）**: 给定一个整数值，返回该值在树状数组中的位置。
* **插入（Insert）**: 将一个新整数值添加到树状数组中。
* **删除（Delete）**: 从树状数组中移除一个整数值。

**树状数组的实现**

下面是树状数组的一种简单实现：

cppclass TreeNode {
public:
 int value;
 TreeNode *left;
 TreeNode *right;

 TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

class TreeArray {
private:
 TreeNode *root;

public:
 TreeArray() : root(nullptr) {}

 ~TreeArray() {
 destroyTree(root);
 }

 void insert(int val) {
 if (root == nullptr) {
 root = new TreeNode(val);
 } else {
 insertNode(root, val);
 }
 }

 int find(int val) {
 return findNode(root, val);
 }

 void deleteValue(int val) {
 root = deleteNode(root, val);
 }

private:
 void destroyTree(TreeNode *node) {
 if (node != nullptr) {
 destroyTree(node->left);
 destroyTree(node->right);
 delete node;
 }
 }

 int findNode(TreeNode *node, int val) {
 if (node == nullptr) {
 return -1; // not found } else if (val < node->value) {
 return findNode(node->left, val);
 } else if (val > node->value) {
 return findNode(node->right, val);
 } else {
 return node->value;
 }
 }

 void insertNode(TreeNode *node, int val) {
 if (val < node->value) {
 if (node->left == nullptr) {
 node->left = new TreeNode(val);
 } else {
 insertNode(node->left, val);
 }
 } else if (val > node->value) {
 if (node->right == nullptr) {
 node->right = new TreeNode(val);
 } else {
 insertNode(node->right, val);
 }
 }
 }

 int deleteNode(TreeNode *node, int val) {
 if (node == nullptr) {
 return nullptr;
 } else if (val < node->value) {
 node->left = deleteNode(node->left, val);
 return node;
 } else if (val > node->value) {
 node->right = deleteNode(node->right, val);
 return node;
 } else {
 // found the node to be deleted if (node->left == nullptr && node->right == nullptr) {
 delete node;
 return nullptr;
 } else if (node->left == nullptr) {
 TreeNode *temp = node->right;
 delete node;
 return temp;
 } else if (node->right == nullptr) {
 TreeNode *temp = node->left;
 delete node;
 return temp;
 } else {
 // find the smallest value in the right subtree TreeNode *smallest = findSmallest(node->right);
 node->value = smallest->value;
 node->right = deleteNode(node->right, smallest->value);
 return node;
 }
 }
 }

 TreeNode *findSmallest(TreeNode *node) {
 while (node->left != nullptr) {
 node = node->left;
 }
 return node;
 }
};