算法——BST

简介: 算法——BST

算法简介

BST是二叉搜索树(Binary Search Tree)的缩写,它是一种特殊的二叉树结构,其中每个节点的左子树中的所有节点都小于该节点的值,而右子树中的所有节点都大于该节点的值。这使得在BST中可以高效地进行搜索、插入和删除操作。

BST具有以下特性:

  • 左子树中的所有节点都小于根节点。
  • 右子树中的所有节点都大于根节点。
  • 左右子树也是二叉搜索树。

算法原理

BST(Binary Search Tree,二叉搜索树)是一种常用的二叉树结构,具有以下特点:

  1. 对于每个节点n,其左子树上的所有节点值都小于n的值,右子树上的所有节点值都大于n的值。
  2. 左右子树也都是BST。

BST的算法原理主要包括插入、查找和删除操作:

  1. 插入操作
  • 从根节点开始,比较要插入的值与当前节点的值。
  • 如果待插入的值小于当前节点的值,则将其置于当前节点的左子树。如果左子树为空,则直接插入。
  • 如果待插入的值大于当前节点的值,则将其置于当前节点的右子树。如果右子树为空,则直接插入。
  • 如果待插入的值等于当前节点的值,则可以根据实际需求选择是忽略还是进行其他操作(如计数)。
  1. 查找操作
  • 从根节点开始,比较要查找的值与当前节点的值。
  • 如果当前节点为空或等于要查找的值,则返回当前节点。
  • 如果要查找的值小于当前节点的值,则在左子树上进行递归查找。
  • 如果要查找的值大于当前节点的值,则在右子树上进行递归查找。
  1. 删除操作
  • 首先,要找到要删除的目标节点。通过查找操作定位到目标节点。
  • 如果目标节点没有子节点,可以直接删除。
  • 如果目标节点只有一个子节点,将该子节点替代目标节点。
  • 如果目标节点有两个子节点,可以选择以下两种方式进行删除:
  • 找到目标节点的左子树中的最大值(或右子树中的最小值),用它来替代目标节点,然后再删除这个最大(小)节点。
  • 或者找到目标节点的右子树中的最小值(或左子树中的最大值),用它来替代目标节点,然后再删除这个最小(大)节点。

BST的基本原则是通过比较节点值来确定子树的方向,从而进行高效的查找和插入操作。通过树结构的特性,BST在查找、区间搜索等应用场景中具有广泛的应用。

算法优缺点

BST(Binary Search Tree,二叉搜索树)作为一种常用的数据结构,具有如下优点和缺点:

优点:

  1. 快速的查找:BST的查找操作的平均时间复杂度为O(log N), N表示树中节点的数量。对于平衡的BST,查找操作的最坏情况时间复杂度也是O(log N)。
  2. 高效的插入和删除:BST在插入和删除操作上表现较好,时间复杂度也为O(log N),并且不需要移动其他元素。
  3. 有序性:BST的构造使得其中的节点按照一定的顺序排列,方便进行区间搜索和范围查找。
  4. 灵活性:BST可以根据需求进行动态调整,具有较强的灵活性。

缺点:

  1. 不平衡性:如果BST不平衡,即左右子树的高度差很大,可能会导致查找和插入操作的时间复杂度明显增加,退化成链表。
  2. 弱失衡性:由于插入和删除操作可能导致BST失衡,因此需要进行平衡操作以保持树的高度平衡,这会引入额外的复杂性。
  3. 对重复值的处理:普通的BST无法处理重复值,但可以通过扩展节点的方式解决。
  4. 非固定性:删除节点时,可能需要调整树的结构,导致树的形状发生变化,不适合要求固定结构的场景。

总结来说,BST在查找、插入和删除等操作上具有较好的性能,能够满足许多应用场景的需求。然而,BST的失衡和对重复值的处理等问题可能需要额外的处理和算法来解决。

使用场景

代码实现

以下是C#语言中实现BST的示例代码:

using System;
public class Node
{
    public int data;
    public Node left;
    public Node right;
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
public class BST
{
    private Node root;
    public BST()
    {
        root = null;
    }
    public void Insert(int key)
    {
        root = InsertNode(root, key);
    }
    private Node InsertNode(Node root, int key)
    {
        if (root == null)
        {
            root = new Node(key);
            return root;
        }
        if (key < root.data)
        {
            root.left = InsertNode(root.left, key);
        }
        else if (key > root.data)
        {
            root.right = InsertNode(root.right, key);
        }
        return root;
    }
    public bool Search(int key)
    {
        return SearchNode(root, key) != null;
    }
    private Node SearchNode(Node root, int key)
    {
        if (root == null || root.data == key)
        {
            return root;
        }
        if (key < root.data)
        {
            return SearchNode(root.left, key);
        }
        return SearchNode(root.right, key);
    }
    public void Delete(int key)
    {
        root = DeleteNode(root, key);
    }
    private Node DeleteNode(Node root, int key)
    {
        if (root == null)
        {
            return root;
        }
        if (key < root.data)
        {
            root.left = DeleteNode(root.left, key);
        }
        else if (key > root.data)
        {
            root.right = DeleteNode(root.right, key);
        }
        else
        {
            if (root.left == null)
            {
                return root.right;
            }
            else if (root.right == null)
            {
                return root.left;
            }
            root.data = MinValue(root.right);
            root.right = DeleteNode(root.right, root.data);
        }
        return root;
    }
    private int MinValue(Node root)
    {
        int minVal = root.data;
        while (root.left != null)
        {
            minVal = root.left.data;
            root = root.left;
        }
        return minVal;
    }
    public void InorderTraversal()
    {
        Inorder(root);
    }
    private void Inorder(Node root)
    {
        if (root != null)
        {
            Inorder(root.left);
            Console.Write(root.data + " ");
            Inorder(root.right);
        }
    }
    public static void Main(string[] args)
    {
        BST tree = new BST();
        // 插入示例节点
        tree.Insert(50);
        tree.Insert(30);
        tree.Insert(20);
        tree.Insert(40);
        tree.Insert(70);
        tree.Insert(60);
        tree.Insert(80);
        // 中序遍历二叉搜索树
        Console.WriteLine("中序遍历结果:");
        tree.InorderTraversal();
        // 搜索某个节点
        int key = 40;
        Console.WriteLine($"\n搜索节点 {key}: {tree.Search(key)}");
        // 删除某个节点
        key = 30;
        tree.Delete(key);
        Console.WriteLine($"删除节点 {key}");
        // 中序遍历二叉搜索树
        Console.WriteLine("中序遍历结果:");
        tree.InorderTraversal();
    }
}

关注我,不迷路,共学习,同进步

关注我,不迷路,共学习,同进步

相关文章
|
30天前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
24 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
算法 Java
Java数据结构与算法分析(八)二叉查找树(BST)
二叉查找树又叫二叉排序树(Binary Sort Tree),或叫二叉搜索树,简称BST。BST是一种节点值之间有次序的二叉树。
97 0
|
存储 算法
【数据结构与算法分析】0基础带你学数据结构与算法分析08--二叉查找树 (BST)
假设树上每个结点都存储了一项数据,如果这些数据是杂乱无章的插入树中,那查找这些数据时并不容易,需要 O(N) 的时间复杂度来遍历每个结点搜索数据。
126 0
【数据结构与算法分析】0基础带你学数据结构与算法分析08--二叉查找树 (BST)
|
算法 Java
看动画学算法之:二叉搜索树BST
看动画学算法之:二叉搜索树BST
看动画学算法之:二叉搜索树BST
|
算法 C语言
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
|
算法 C语言
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
|
存储 算法 Java
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
|
算法 C语言
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
|
存储 算法 API
【算法】二叉查找树(BST)实现字典API
参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结构》                                  — — 严蔚敏   上一篇文章,我介绍了实现字典的两种方式,:有序数组和无序链表 字典的诞生:有序数组 PK 无序链表 这一篇文章介绍的是一种新的更加高效的实现字典的方式——二叉查找树。
1310 0
下一篇
无影云桌面