Java二叉搜索树深度解析:一文尽揽核心要诀

前言:Java具备丰富的数据结构用于数据的处理与管理,其中TreeSet和TreeMap是以红黑树为基础实现的集合与映射接口。它们能够有序地存储数据,并且支持高效的搜索、插入以及删除操作。


本文讲解概览:

目录

1.对二叉搜索树的认知

(1)二叉搜索树的概念

在开始研习TreeSet与TreeMap之前,我们需先了解Java里的二叉搜索树。二叉搜索树是一种特殊的二叉树,每个节点都有一个值,且满足以下性质:

  • 对于每一个节点,其左子树中所有节点的值均小于该节点的值。

  • 对于每一个节点,其右子树中所有节点的值均大于该节点的值。

如图所示:

<p title=Java二叉搜索树深度解析:一文尽揽核心要诀

" />

从该图中能清晰看出二叉搜索树的上述两个特性。

(2)二叉搜索树的性质

在明确二叉搜索树的概念后,我们来学习其相关性质。对于一棵二叉搜索树而言,具有以下三个性质:

  • 有序性:二叉搜索树进行中序遍历的结果是一个递增的有序序列。

  • 动态性:二叉搜索树支持动态的插入和删除操作,适用于需要频繁更新的数据集合。

  • 查找效率:在理想情况下,二叉搜索树的查找、插入和删除操作的时间复杂度为 O(log n)。

——读者可能对其中部分性质不太理解,没关系,继续往下阅读,后续会逐步领会其含义。

2.关于二叉搜索树的常见操作

【1】插入操作

插入操作是向二叉搜索树中添加新值。插入过程从根节点开始,根据当前节点的值与新值的比较结果,决定将新值插入到左子树还是右子树。

以下是实现该操作的代码:

public void insertNode(int key) {
    // 如果根节点为空,直接将新节点作为根节点插入
    if (root == null) {
        root = new TreeNode(key);
        return;
    }

    // 初始化当前节点为根节点,父节点为null
    TreeNode cur = root;
    TreeNode parent = null;
    TreeNode node = new TreeNode(key);

    // 寻找合适的插入位置
    while (cur != null) {
        if (cur.val < key) { // 当前值小于插入值,往右子树移动
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) { // 当前值大于插入值,往左子树移动
            parent = cur;
            cur = cur.left;
        } else { // 当前值等于插入值,直接返回,不插入重复值
            return;
        }
    }

    // 根据父节点值与插入值的比较结果,将新节点插入到左子树或右子树
    if (parent.val > key) {
        parent.left = node;
    } else {
        parent.right = node;
    }
}

大家可跟着下面的解释来理解上述代码:

  1. 根节点为空的检查

    • root 为空,直接把新节点 TreeNode(key) 当作根节点插入,并返回。
    • 初始化当前节点和父节点

    • cur 用于遍历树,从 root 开始。

    • parent 用来记录 cur 的父节点。
    • 寻找合适的插入位置

    • cur 不为空时,比较 cur.valkey

    • cur.val 小于 key,移动到右子树。
    • cur.val 大于 key,移动到左子树。
    • cur.val 等于 key,直接返回,不插入重复值。
    • 插入新节点

    • 根据 parent.valkey 的比较结果,把新节点插入到 parent 的左子树或右子树。

——这样我们就掌握了插入操作啦!

【2】查找操作

查找操作是在二叉搜索树中查找特定值。查找过程从根节点开始,根据当前节点的值与目标值的比较结果,决定在左子树还是右子树继续查找。

以下是实现该操作的代码:

public TreeNode search(int key) {
    // 初始化当前节点为根节点
    TreeNode cur = root;

    // 遍历树,直到找到目标节点或遍历到空节点
    while (cur != null) {
        if (cur.val < key) { // 当前节点值小于目标值,移动到右子树
            cur = cur.right;
        } else if (cur.val > key) { // 当前节点值大于目标值,移动到左子树
            cur = cur.left;  // 这里应修正为cur = cur.left;
        } else { // 找到目标节点
            return cur;
        }
    }
    // 如果没有找到目标节点,返回 null
    return null;
}

大家可跟着下面的解释来理解上述代码:

  1. 初始化当前节点

    • cur 用于遍历树,从 root 开始。
    • 遍历树

    • cur 不为空时,比较 cur.valkey

    • cur.val 小于 key,移动到右子树 (cur = cur.right)。
    • cur.val 大于 key,移动到左子树 (cur = cur.left)。
    • cur.val 等于 key,返回当前节点。
    • 返回结果

    • 如果遍历完整个树都没找到目标节点,返回 null

【3】删除操作

删除操作是从二叉搜索树中移除指定值。删除节点分为三种情况:叶子节点、仅有一个子节点的节点和有两个子节点的节点。

由于删除操作较为复杂,我们着重讲解。对于删除操作,可能出现以下几种情况:

——现在假设待删除结点为 cur,待删除结点的双亲结点为 parent:

1.cur.left == null

1. cur 是 root,则 root = cur.right
2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.right
3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.right

2.cur.right == null

1. cur 是 root,则 root = cur.left
2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.left

3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.left

3.cur.left != null && cur.right != null

这时需要用替换法来删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,然后再处理该结点的删除问题

在大致了解删除的三种大情况后,我们尝试编写代码:

public void remove(int key) {
    TreeNode parent = null; // 父节点初始化为 null
    TreeNode cur = root; // 当前节点初始化为根节点
    // 遍历树,查找要删除的节点
    while (cur != null) {
        if (cur.val < key) { // 当前值小于目标值,移动到右子树
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) { // 当前值大于目标值,移动到左子树
            parent = cur;
            cur = cur.left;
        } else { // 找到目标节点
            removeNode(parent, cur); // 调用辅助方法删除节点
            return; // 删除节点后退出方法
        }
    }
}

private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.right == null) { // 当前节点没有右子树
        if (cur == root) { // 当前节点是根节点
            root = root.left; // 根节点指向左子树
        } else if (parent.left == cur) { // 当前节点是父节点的左子节点
            parent.left = cur.left; // 父节点左子节点指向当前节点的左子树
        } else { // 当前节点是父节点的右子节点
            parent.right = cur.left; // 父节点右子节点指向当前节点的左子树
        }
    } else if (cur.left == null) { // 当前节点没有左子树
        if (cur == root) { // 当前节点是根节点
            root = root.right; // 根节点指向右子树
        } else if (parent.left == cur) { // 当前节点是父节点的左子节点
            parent.left = cur.right; // 父节点左子节点指向当前节点的右子树
        } else { // 当前节点是父节点的右子节点
            parent.right = cur.right; // 父节点右子节点指向当前节点的右子树
        }
    } else { // 当前节点有两个子节点
        TreeNode targetParent = cur; // 目标节点的父节点初始化为当前节点
        TreeNode target = cur.right; // 目标节点初始化为当前节点的右子节点
        // 寻找右子树中的最左节点
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        cur.val = target.val; // 用右子树中最左节点的值替换当前节点的值
        // 调整指针以删除目标节点
        if (targetParent.left == target) {
            targetParent.left = target.right;
        } else {
            targetParent.right = target.right;
        }
    }
}

——这里我们给每一条代码都添加了注释,大家可依据注释来理解上述代码!!!

如此我们便了解了二叉搜索树中常见的操作。

3.二叉树的应用场景

在学习了二叉树的概念及其基本使用后,我们来了解一些二叉树的应用场景,二叉树(Binary Tree)在日常生活中有广泛应用。以下是一些主要的实际应用场景:

1. 数据结构和算法

  • 二叉搜索树(BST) :用于实现高效的搜索、插入和删除操作,时间复杂度平均为 O(log n)。

  • 平衡树(如AVL树、红黑树) :这些是自平衡二叉搜索树,确保树的高度保持在 O(log n),从而提供高效的操作。

  • 堆(Heap) :二叉堆用于实现优先队列。最大堆用于实现高效的最大值查找,最小堆用于最小值查找。

2. 数据库和文件系统

  • B树和B+树 :这些是多路搜索树,常用于数据库索引和文件系统索引,以提高查询和检索的效率。

  • Trie树 :一种多叉树,用于实现前缀匹配,常用于字典存储和自动补全功能。

3. 图形和游戏开发

  • 四叉树和八叉树 :用于空间分割,以提高碰撞检测、渲染和其他空间查询操作的效率。

  • 场景图(Scene Graph) :在3D图形引擎中,场景图是一个树状结构,用于管理和渲染场景中的对象。

这样我们就大致知晓了二叉树在未来日常中的应用之处啦!!!


以上便是本篇文章的主要内容啦!!!

相关文章

暂无评论

暂无评论...