数据结构与算法 / 系统课时

二叉搜索树插入

二叉搜索树插入

二叉搜索树插入的关键不是把节点放进任意空位,而是沿比较结果向左或向右下降,直到找到唯一合法的空链接。本课将实现迭代插入,并用树高解释为什么相同数量的节点可能产生完全不同的插入成本。

学习目标

  • 掌握二叉搜索树的插入路径与重复键处理规则。
  • 实现完整的节点插入、中序遍历和查找程序。
  • 根据树高分析平均与最坏情况下的时间复杂度。

插入规则与执行路径

对当前节点 current 比较待插入键 key:

  • key < current.key 时进入左子树。
  • key > current.key 时进入右子树。
  • 两者相等时按既定策略处理;本例选择忽略重复键。
  • 目标方向的子链接为空时,在该位置创建新节点。

二叉搜索树插入路径与树高影响

一次插入只访问根到目标位置的一条路径,因此时间复杂度是 O(h)O(h),其中 hh 为树高。树较平衡时,hh 接近 log⁡2n\log_2 n;若键按单调顺序插入,树可能退化为链表,此时 h=nh=n。迭代实现只保存当前节点引用,额外空间为 O(1)O(1)。

完整可运行示例

将代码保存为 BstInsertDemo.java。程序依次插入多个整数,随后通过中序遍历验证有序性,并输出树高和查找结果。

java
import java.util.ArrayList;
import java.util.List;

public class BstInsertDemo {
    private static final class Node {
        int key;
        Node left;
        Node right;

        Node(int key) {
            this.key = key;
        }
    }

    public static void main(String[] args) {
        int[] keys = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        Node root = null;

        for (int key : keys) {
            root = insert(root, key);
        }

        System.out.println("中序遍历: " + inOrder(root));
        System.out.println("树高: " + height(root));
        System.out.println("查找 7: " + contains(root, 7));
    }

    private static Node insert(Node root, int key) {
        if (root == null) {
            return new Node(key);
        }

        Node current = root;
        while (true) {
            if (key < current.key) {
                if (current.left == null) {
                    current.left = new Node(key);
                    break;
                }
                current = current.left;
            } else if (key > current.key) {
                if (current.right == null) {
                    current.right = new Node(key);
                    break;
                }
                current = current.right;
            } else {
                break;
            }
        }
        return root;
    }

    private static boolean contains(Node root, int key) {
        Node current = root;
        while (current != null) {
            if (key == current.key) {
                return true;
            }
            current = key < current.key ? current.left : current.right;
        }
        return false;
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    private static List<Integer> inOrder(Node root) {
        List<Integer> result = new ArrayList<>();
        collectInOrder(root, result);
        return result;
    }

    private static void collectInOrder(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        collectInOrder(node.left, result);
        result.add(node.key);
        collectInOrder(node.right, result);
    }
}

编译并运行:

bash
javac BstInsertDemo.java
java BstInsertDemo

预期输出

text
中序遍历: [1, 3, 4, 6, 7, 8, 10, 13, 14]
树高: 4
查找 7: true

中序遍历结果严格递增,说明每个节点都满足“左子树键更小、右子树键更大”的约束。这里把单节点树的高度定义为 1,因此示例树高度为 4。

常见错误与练习

常见错误包括:比较后忘记更新 current,导致死循环;在发现空链接前就覆盖已有子节点,导致整棵子树丢失;没有定义重复键策略,使集合语义和计数语义混在一起。调试时可以同时检查中序遍历是否有序,以及插入前后的节点数量是否符合预期。

练习 1:把重复键策略改为在节点中维护 count,连续插入三个 6 后,要求树结构不增加节点,但键 6 的计数为 3。

练习 2:分别按升序和随机顺序插入 1 到 1000,输出两棵树的高度,并比较查找最后一个键时访问的节点数量。

本课总结

  • 插入位置由连续比较唯一确定,算法只沿一条根到叶的路径前进。
  • 插入时间为 O(h)O(h),树高决定实际性能,退化树的最坏成本为 O(n)O(n)。
  • 中序遍历有序是验证二叉搜索树结构是否正确的直接方法。

下一课预告

下一课将学习“二叉搜索树删除”,重点处理叶节点、只有一个子节点和拥有两个子节点三种情况,并理解后继节点替换为什么能够保持搜索树性质。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉搜索树插入

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通