当前位置： 首页 > article >正文

深入理解二叉搜索树（BST）

article 2024/11/26 5:55:08

二叉搜索树简介

二叉搜索树（BST） 是一种具有特殊排序性质的二叉树，能够高效地执行数据检索、插入和删除操作。BST 的主要特性是，对于每个节点，其左子树中所有节点的值都小于或等于该节点的值，而右子树中所有节点的值都大于该节点的值。这一特性使得 BST 成为一种非常重要的数据结构，适用于搜索和排序任务，因为它提供了一种逻辑清晰且直接的方式来存储和检索有序数据。

二叉搜索树的定义与性质

二叉搜索树要么是一棵空树，要么是具有以下性质的二叉树：

  • 如果左子树不为空，则左子树中的所有节点值都 小于或等于 根节点的值。

  • 如果右子树不为空，则右子树中的所有节点值都 大于 根节点的值。

  • 左右子树本身也必须是二叉搜索树。

这种排序特性使得搜索操作非常高效，因为每次决定向左还是向右走都将可能的位置数量减半，这类似于二分查找算法。

二叉搜索树的性能分析

BST 的性能直接受到树结构的影响。理想情况下，我们希望树是平衡的，以最小化高度，从而确保良好的性能。

  • 最佳情况（平衡树）：在最佳情况下，BST 是完全二叉树或接近完全二叉树，高度为 ，其中 是节点的数量。

  • 最差情况（退化树）：在最差情况下，树会退化为链表，树的高度为 。这通常发生在节点按顺序插入的情况下。

因此，插入、删除和搜索等操作的时间复杂度在 最佳情况下 为 ，而在 最差情况下 为 。

为了解决最差情况下可能出现的低效问题，引入了平衡二叉搜索树，如 AVL 树和红黑树。它们在插入和删除操作时会自动调整自身，以确保其高度保持在对数级别。

二叉搜索树与二分查找的局限性

BST 提供了与二分查找相似的搜索效率（），但有一些附加的灵活性：

  • 二分查找 需要将数据存储在连续的结构（如数组）中，并且保持有序，这使得 插入 和 删除 的代价很高（）。

  • BST 可以将数据存储在动态扩展的结构中，无需连续内存，允许高效的插入和删除。

BST 的核心操作

1. 二叉搜索树中的插入操作

在 BST 中插入元素需要遵循树的排序性质：

  • 如果树为空，新节点就成为根节点。

  • 如果新值小于当前节点的值，则进入左子树。

  • 如果新值大于当前节点的值，则进入右子树。

  • 重复这一过程，直到找到合适的叶子位置。

以下是 C++ 中实现 BST 插入操作的示例代码：

#include <iostream>

// 定义二叉搜索树节点模板
template<class K>
struct BSTNode {
    K _key; // 节点的键值
    BSTNode<K>* _left; // 指向左子节点的指针
    BSTNode<K>* _right; // 指向右子节点的指针

    // 构造函数，初始化节点的键值和左右子节点为空
    BSTNode(const K& key)
        : _key(key), _left(nullptr), _right(nullptr) {}
};

// 定义二叉搜索树模板类
template<class K>
class BSTree {
    typedef BSTNode<K> Node;
public:
    // 插入新节点
    bool Insert(const K& key) {
        // 如果树为空，新节点成为根节点
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }

        Node* parent = nullptr; // 用于记录当前节点的父节点
        Node* cur = _root; // 从根节点开始遍历树
        while (cur) {
            if (cur->_key < key) { // 如果插入的值大于当前节点，移动到右子树
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) { // 如果插入的值小于当前节点，移动到左子树
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 不允许插入重复的键
            }
        }

        // 找到空位置插入新节点
        cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }

        return true;
    }

private:
    Node* _root = nullptr; // 根节点指针，初始化为空
};

在上面的代码中，我们定义了一个二叉搜索树的节点结构 BSTNode，以及一个二叉搜索树类 BSTree。Insert 方法实现了插入操作，从根节点开始遍历树，直到找到适合插入的位置。

2. 二叉搜索树中的查找操作

查找操作的实现与插入类似，根据键值的大小关系不断向左或向右移动，直到找到目标节点或到达叶子节点。

// 查找节点是否存在于二叉搜索树中
bool Find(const K& key) {
    Node* cur = _root; // 从根节点开始查找
    while (cur) {
        if (cur->_key < key) { // 如果查找值大于当前节点值，移动到右子树
            cur = cur->_right;
        } else if (cur->_key > key) { // 如果查找值小于当前节点值，移动到左子树
            cur = cur->_left;
        } else {
            return true; // 找到目标值
        }
    }
    return false; // 未找到目标值
}

在 Find 方法中，我们从根节点开始，根据键值大小关系不断移动，直到找到目标值或者树中不存在该值。

3. 二叉搜索树中的删除操作（重点）

删除操作较为复杂，因为需要处理多种情况：

  • 叶子节点：直接删除该节点。

  • 只有一个子节点的节点：让其父节点指向该子节点。

  • 有两个子节点的节点：使用替换法，用右子树中的最小节点或左子树中的最大节点替换要删除的节点。

以下是删除操作的代码示例：

// 删除节点
bool Erase(const K& key) {
    Node* parent = nullptr; // 用于记录父节点
    Node* cur = _root; // 从根节点开始查找要删除的节点
    while (cur) {
        if (cur->_key < key) { // 查找值大于当前节点值，移动到右子树
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) { // 查找值小于当前节点值，移动到左子树
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到了需要删除的节点
            if (cur->_left == nullptr) { // 只有右子节点或无子节点的情况
                if (parent == nullptr) {
                    _root = cur->_right; // 如果是根节点，则更新根节点
                } else {
                    if (parent->_left == cur) {
                        parent->_left = cur->_right;
                    } else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
                return true;
            } else if (cur->_right == nullptr) { // 只有左子节点的情况
                if (parent == nullptr) {
                    _root = cur->_left; // 如果是根节点，则更新根节点
                } else {
                    if (parent->_left == cur) {
                        parent->_left = cur->_left;
                    } else {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
                return true;
            } else { // 有两个子节点的情况
                Node* rightMinP = cur; // 记录右子树中最小节点的父节点
                Node* rightMin = cur->_right; // 找右子树中的最小节点
                while (rightMin->_left) {
                    rightMinP = rightMin;
                    rightMin = rightMin->_left;
                }
                cur->_key = rightMin->_key; // 用右子树中最小节点的值替换当前节点的值
                if (rightMinP->_left == rightMin) {
                    rightMinP->_left = rightMin->_right;
                } else {
                    rightMinP->_right = rightMin->_right;
                }
                delete rightMin; // 删除右子树中的最小节点
                return true;
            }
        }
    }
    return false; // 未找到要删除的节点
}

在 Erase 方法中，删除操作分为三种情况进行处理：叶子节点、只有一个子节点、以及有两个子节点的情况。在有两个子节点时，我们使用右子树中的最小节点来替换要删除的节点，以保持 BST 的性质。

二叉搜索树的使用场景

1. 仅使用 Key 作为搜索目标

在一些场景中，我们只需要查找某个值是否存在，此时只需要存储键（key）。例如：

  • 小区无人值守车库：物业将业主车牌号录入系统，车辆进场时扫描车牌，如果在系统中则自动抬杆放行。

  • 英文单词拼写检查：将所有正确的单词放入 BST 中，检查文档中的单词是否存在，不存在则标记为拼写错误。

2. 使用 Key-Value 结构

在有些情况下，每个键都有一个对应的值，树节点需要存储键值对。例如：

  • 中英翻译字典：树节点中存储英文单词和对应的中文翻译，查找时输入英文即可获取对应的中文。

  • 停车场计费系统：记录车辆的车牌和入场时间，离场时计算停车费用。

  • 统计单词出现次数：读取文章中的每个单词并存入 BST，如果单词已经存在则增加其出现次数。

以下是一个简单的 Key-Value 二叉搜索树的实现：

template<class K, class V>
struct BSTNode {
    K _key; // 节点的键
    V _value; // 节点的值
    BSTNode<K, V>* _left; // 左子节点指针
    BSTNode<K, V>* _right; // 右子节点指针

    // 构造函数，初始化键值对和左右子节点为空
    BSTNode(const K& key, const V& value)
        : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

// Key-Value 型二叉搜索树
template<class K, class V>
class BSTree {
    typedef BSTNode<K, V> Node;
public:
    // 插入新的键值对
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }

        Node* parent = nullptr; // 记录父节点
        Node* cur = _root; // 从根节点开始遍历树
        while (cur) {
            if (cur->_key < key) { // 插入值大于当前节点，移动到右子树
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) { // 插入值小于当前节点，移动到左子树
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 不允许插入重复的键
            }
        }

        // 找到空位置插入新节点
        cur = new Node(key, value);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }

        return true;
    }

    // 查找键值对
    Node* Find(const K& key) {
        Node* cur = _root; // 从根节点开始查找
        while (cur) {
            if (cur->_key < key) { // 查找值大于当前节点值，移动到右子树
                cur = cur->_right;
            } else if (cur->_key > key) { // 查找值小于当前节点值，移动到左子树
                cur = cur->_left;
            } else {
                return cur; // 找到目标节点
            }
        }
        return nullptr; // 未找到目标节点
    }

private:
    Node* _root = nullptr; // 根节点指针，初始化为空
};

在 BSTree 类中，我们实现了一个带有键值对的二叉搜索树。插入操作和查找操作均遵循 BST 的基本规则，从根节点开始遍历，找到合适的位置或节点。

结论

二叉搜索树是一种强大而灵活的数据结构，适用于需要快速查找、插入和删除的场景。通过平衡的结构，BST 可以实现近似于对数级别的高效操作。然而，在某些极端情况下，BST 可能会退化为链表，因此更高级的平衡树如 AVL 树和红黑树在实际应用中更为常用。通过理解 BST 的基本操作和性能特点，我们可以更好地选择合适的数据结构来满足不同的应用需求。


http://www.kler.cn/a/409542.html

相关文章：

  • 在英文科技论文中分号后面的单词首字母需不需要大写
  • Element UI 打包探索【2】
  • 鸿蒙开发Hvigor插件动态生成代码
  • 使用timm库加载模型与模型权重
  • Oracle 19c Rac + ADG搭建（源库：RAC，目标库FS）
  • 由于centos停更，yum、docker等不支持，采用阿里云仓库搭建K8S
  • 【组件】前端ElementUi 下拉Tree树形组件 带模糊搜索自动展开高亮功能
  • Move 合约部署踩坑笔记：如何解决 Sui 客户端发布错误Committing lock file
  • linux系统运维面试题（二）（Linux System Operations Interview Questions II）
  • 国产FPGA+DSP 双FMC 6U VPX处理板
  • 嵌入式硬件实战提升篇(二)PCB高速板设计 FPGA核心板带DDR3 PCB设计DDR全面解析
  • LeetCode Hot100 - 矩阵篇
  • Vue.js 前端路由详解：从基础概念到 Vue Router 实战
  • 植物明星大乱斗——功能拆解
  • ffmpeg.wasm 在浏览器运行ffmpeg操作视频
  • day27|leetCode 455. 分发饼干,376.摆动序列,53. 最大子数组和
  • 快速排序算法-C语言
  • GitLab 使用过程中常见问题及解决方案
  • 【人工智能】Transformers之Pipeline（二十五）：图片特征抽取（image-feature-extraction）
  • Vue.js 学习总结（14）—— Vue3 为什么推荐使用 ref 而不是 reactive
  • c ++零基础可视化——字符串
  • 用js实现点击抽奖
  • C# 读取多条数据记录导出到 Word标签模板之图片输出改造
  • 图解GitLab DevSecOps 流程
  • LabVIEW发动机热磨合试验台
  • 基于Angular+BootStrap+SpringBoot简单的购物网站