排序算法之：Tree Sort（树排序）的构建与遍历优化

题目描述
给定一个整数数组 [3, 1, 4, 1, 5, 9, 2, 6]，要求使用 树排序（Tree Sort） 对数组进行升序排序。树排序的核心思想是：将数组元素依次插入二叉搜索树（BST）中，再通过中序遍历 BST 得到有序序列。需要分析时间复杂度、空间复杂度，并讨论如何处理重复元素和优化树结构（如平衡二叉搜索树）。

解题过程

1. 二叉搜索树（BST）的构建

• 步骤：
  • 从空树开始，依次插入数组中的每个元素。
  • 插入规则：若当前节点值大于待插入值，向左子树递归插入；若小于，向右子树递归插入；若相等，根据需求处理重复元素（如计数或作为右子树）。
• 示例：
  插入顺序：3 → 1 → 4 → 1 → 5 → 9 → 2 → 6
  • 插入 3：根节点为 3。
  • 插入 1：1 < 3，作为左子节点。
  • 插入 4：4 > 3，作为右子节点。
  • 插入 1：重复值，可存储在右子树（或计数），此处作为左子树的右子节点（需保持 BST 性质）。
  • 继续插入剩余元素，最终 BST 结构如下：

          3
         / \
        1   4
       / \   \
      1   2   5
             / \
            9   6
    

  注：实际插入顺序可能影响树的高度，导致最坏情况退化为链表（如输入已排序数组）。

2. 中序遍历与排序输出

• 规则：按 左子树 → 根节点 → 右子树 的顺序遍历，自然得到升序序列。
• 示例遍历过程：
  1. 从根节点 3 开始，递归遍历左子树（以 1 为根的子树）。
  2. 左子树 1 的左子节点为 1，输出 1（第一个 1）。
  3. 回到根节点 1，输出 1（第二个 1）。
  4. 遍历 1 的右子树 2，输出 2。
  5. 回到根节点 3，输出 3。
  6. 遍历右子树（以 4 为根的子树），依次输出 4, 5, 6, 9。
• 最终有序序列：[1, 1, 2, 3, 4, 5, 6, 9]。

3. 处理重复元素的策略

• 方法一：在 BST 节点中增加计数域（如 count），遇到重复值时计数加一，遍历时按计数重复输出。
• 方法二：将重复值插入右子树（或左子树），但需保证中序遍历顺序不变（如统一作为右子树的最小节点）。
• 优化选择：计数法更节省空间，避免树深度增加。

4. 时间复杂度与优化

• 平均情况（平衡 BST）：
  • 构建 BST：O(n log n)。
  • 中序遍历：O(n)。
  • 总复杂度：O(n log n)。
• 最坏情况（输入已排序）：树退化为链表，构建复杂度 O(n²)。
• 优化方案：使用 平衡二叉搜索树（如 AVL 树、红黑树），确保插入操作始终保持树平衡，将最坏复杂度优化至 O(n log n)。

5. 空间复杂度分析

• 需要 O(n) 额外空间存储树节点（每个节点包含值、左右子指针及可选计数域）。
• 若输入数据基本有序，平衡 BST 的额外空间开销仍为 O(n)。

总结
树排序结合了 BST 的动态插入和中序遍历的有序性，适合需要动态维护有序数据的场景。通过平衡树优化，可避免性能退化，而重复元素处理策略需根据实际需求选择计数或结构调整。