# SquareData

**Repository Path**: SeaLandShell/square-data

## Basic Information

- **Project Name**: SquareData
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-06-26
- **Last Updated**: 2024-06-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 内存版
1.  **TreeNode 类**：

    -   `TreeNode` 类定义了存放在 AVL 树中的节点。每个节点包含数据 (`data`)、平衡因子 (`bf`)、父节点 (`parent_node`)、左右子节点 (`left_child`, `right_child`) 以及重复插入次数计数 (`count`)。
    -   `toString()` 方法用于以字符串形式输出节点信息，避免打印导致的循环引用问题。
    -   `equals()` 和 `hashCode()` 方法确保节点值的唯一性。

1.  **AVLTree 类**：

    -   `AVLTree` 类实现了 AVL 树的核心功能。
    -   使用 `LinkedList` 实现了存储树节点的队列 `tree`。
    -   `getRootNode()` 方法获取根节点。
    -   `reCountNodeBF()` 方法重新计算所有节点的平衡因子。
    -   `getHeight(TreeNode node)` 方法计算节点的高度。
    -   `insertNode(int data)` 方法用于插入新节点，执行插入后重新计算平衡因子并检查是否需要执行旋转操作。
    -   `countMinUnBalanceNode(TreeNode node)` 方法计算最小不平衡子树。
    -   旋转操作包括 `rightRotate(TreeNode node)` 和 `leftRotate(TreeNode node)`，分别用于处理 LL、RR、LR、RL 四种不平衡情况。
    -   `searchNode(int data)` 方法用于查找节点。
    -   `deleteNode(int data)` 方法用于删除节点，根据节点的子树情况分为四种情况处理：叶子节点、只有左子树、只有右子树、有左右子树，并在需要时进行节点重建和旋转操作。

## 磁盘存储版
-   **AVLTreeOnDisk 类**：

    -   使用 `RandomAccessFile` 实现节点的随机访问和持久化存储。
    -   `FILE_PATH` 常量指定了存储AVL树节点数据的文件路径。

-   **TreeNode 静态内部类**：

    -   表示AVL树的节点结构，每个节点包含数据 (`data`)、平衡因子 (`bf`)、左子节点、右子节点和父节点的位置信息。
    -   `writeNode` 方法将节点信息写入文件。
    -   `readNode` 方法从文件中读取节点信息。

-   **AVLTreeOnDisk 类的主要方法**：

    -   **构造方法 `AVLTreeOnDisk()`** ：

        -   初始化时，如果文件已存在则删除重新创建，以确保数据清空。
        -   打开文件准备读写操作。

    -   **insertNode 方法**：

        -   插入新节点到AVL树中，递归方式实现。
        -   若树为空则直接插入，否则根据节点值大小递归向左或右子树插入。
        -   插入后进行平衡操作 (`rebalance`)。

    -   **deleteNode 方法**：

        -   删除指定节点，若节点存在两个子节点则找到后继节点替换，再删除后继节点。
        -   删除后进行平衡操作 (`rebalance`)。

    -   **rebalance 方法**：

        -   平衡树的核心方法，根据节点的平衡因子进行左旋 (`leftRotate`) 或右旋 (`rightRotate`)。
        -   在插入或删除后调用此方法来维护AVL树的平衡性。

    -   **leftRotate 和 rightRotate 方法**：

        -   分别执行左旋和右旋操作，保持或恢复AVL树的平衡性。

    -   **searchNode 方法**：

        -   搜索指定值的节点，从根节点开始递归搜索。

    -   **getHeight 方法**：

        -   获取节点的高度，用于计算节点的平衡因子。

-   **数据存储和文件操作**：

    -   每个节点的信息以二进制形式存储在文件中，通过 `RandomAccessFile` 实现节点数据的随机访问和修改。
    -   操作文件时，通过 `seek` 方法定位到指定位置读取或写入节点信息。

## 磁盘存储UT case结果图
![磁盘存储测试效果图](./UT_case.png)