树数据结构

1. 树的基础知识

树是一种由节点通过边连接组成的分层数据结构。一些关键术语：

根节点：树的最顶端节点
子节点：当远离根节点时，直接连接到另一个节点的节点
父节点：连接到子节点的节点
叶节点 (Leaf)：没有子节点的节点
内部节点：至少有一个子节点的节点
高度：从根节点到叶节点的最长路径的长度
深度：从根节点到特定节点的路径的长度

来源：src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java

2. 二叉树

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。本仓库中的BinaryTree实现提供了一个标准的二叉树，具有节点管理和遍历功能。

2.1 结构

来源：src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java

2.2 操作

BinaryTree类包含以下关键操作：

操作	描述	时间复杂度
`find(int key)`	查找具有指定键的节点，或返回它将要插入的父节点	O(log n) 平均，O(n) 最坏
`put(int value)`	向树中插入一个新值	O(log n) 平均，O(n) 最坏
`remove(int value)`	从树中删除一个值	O(log n) 平均，O(n) 最坏
`findSuccessor(Node n)`	查找节点的中序后继	O(log n) 平均，O(n) 最坏

2.3 遍历方法

BinaryTree类支持四种遍历方法：

中序遍历 (inOrder)：先访问左子树，然后是根节点，最后是右子树
前序遍历 (preOrder)：先访问根节点，然后是左子树，最后是右子树
后序遍历 (postOrder)：先访问左子树，然后是右子树，最后是根节点
广度优先遍历 (bfs)：使用队列进行逐层遍历

对于这棵树：

中序遍历: 1, 2, 3, 4, 5, 6, 7
前序遍历: 4, 2, 1, 3, 6, 5, 7
后序遍历: 1, 3, 2, 5, 7, 6, 4
广度优先遍历: 4, 2, 6, 1, 3, 5, 7

来源：src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java262-329

3. 自平衡树

自平衡树自动调整其结构以保持某些属性，从而保证效率。该仓库包含两种自平衡二叉搜索树的实现。

3.1 红黑树

红黑树是一种自平衡二叉搜索树，每个节点都有一个额外的颜色属性（红色或黑色）。这些树通过一系列属性和重新着色/旋转操作来保持平衡。

红黑树的属性

每个节点都是红色或黑色
根节点是黑色
所有叶子节点（NIL节点）都是黑色
如果一个节点是红色，则其两个子节点都是黑色
从一个节点到其任意后代NIL节点的每条路径都包含相同数量的黑色节点

来源：src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java

RedBlackBST实现包括：

节点结构：每个节点都有一个键、颜色（红色或黑色），以及指向左、右和父节点的指针
旋转操作：左旋转和右旋转以维护树的平衡
插入和删除：在保留红黑树属性的同时添加和删除节点

主要方法包括

fixTree()：插入后恢复红黑树属性
rotateLeft() 和 rotateRight()：旋转操作
transplant()：用一个子树替换另一个子树
deleteFixup()：删除后恢复红黑树属性

来源：src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java137-162 src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java162-186

3.2 AVL树

AVL树（以发明者 Adelson-Velsky 和 Landis 命名）是一种自平衡二叉搜索树，它保持高度平衡属性：对于每个节点，其左子树和右子树的高度差最多为1。

来源：src/main/java/com/thealgorithms/datastructures/trees/AVLSimple.java

AVLSimple实现包括：

节点结构：每个节点都包含数据、高度以及指向左、右子节点的指针
平衡因子：左子树和右子树的高度差
旋转操作:
- 左旋转（LL情况）
- 右旋转（RR情况）
- 左右旋转（LR情况）
- 右左旋转（RL情况）

来源：src/main/java/com/thealgorithms/datastructures/trees/AVLSimple.java125-145

4. 特殊用途树

该仓库还包括用于高效解决特定问题的专用树形数据结构。

4.1 线段树

线段树是一种用于存储区间或线段的树形数据结构，可对数组的区间进行高效查询。它特别适用于范围查询，例如查找特定范围内的最小值、最大值、总和或最大公约数。

来源：src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java

SegmentTree实现包括：

构建：从输入数组构建线段树
更新操作：高效地更新树中的值
查询操作：返回区间查询的结果（例如，某个范围内的总和）

SegmentTree类包含以下关键方法：

constructTree()：创建线段树
updateTree()：更新线段树中的值
getSumTree()：获取一个范围内的元素总和

来源：src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java22-31 src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java35-46 src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java61-72

4.2 树状数组（二叉索引树）

树状数组或二叉索引树是一种数据结构，可以高效地更新元素并计算数字表中的前缀和。

来源：src/main/java/com/thealgorithms/datastructures/trees/FenwickTree.java

FenwickTree实现包括：

更新操作：高效更新值
查询操作：计算给定索引的前缀和

FenwickTree类包含以下关键方法：

update(i, val)：在索引i处添加值
query(i)：返回从索引0到索引i的元素总和

该实现使用位操作技术高效地遍历树：

i += i & (-i)：在更新操作中移动到下一个元素
i -= i & (-i)：在查询操作中移动到下一个元素

来源：src/main/java/com/thealgorithms/datastructures/trees/FenwickTree.java14-34

5. 树形数据结构比较

树类型	优点	缺点	最佳用例
二叉树	实现简单	无平衡保证	基本分层数据表示
红黑树	保证O(log n)操作	实现复杂	数据库索引，Java的TreeMap和TreeSet
AVL 树	严格平衡以实现最佳搜索	插入/删除时旋转成本更高	查找密集型应用
线段树	快速范围查询	更高的空间复杂度	范围查询问题（最小值、最大值、总和等）
Fenwick 树	高效的更新和查询	仅限于前缀和类型查询	累积频率表、范围和查询

来源：src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java src/main/java/com/thealgorithms/datastructures/trees/AVLSimple.java src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java src/main/java/com/thealgorithms/datastructures/trees/FenwickTree.java

6. 树遍历可视化

各种遍历方法可用于按特定顺序访问树中的节点