算法——BST-阿里云开发者社区

算法——BST

2024-07-02 28

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法——BST

算法简介

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

BST具有以下特性：

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

算法原理

BST（Binary Search Tree，二叉搜索树）是一种常用的二叉树结构，具有以下特点：

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

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

插入操作：

从根节点开始，比较要插入的值与当前节点的值。
如果待插入的值小于当前节点的值，则将其置于当前节点的左子树。如果左子树为空，则直接插入。
如果待插入的值大于当前节点的值，则将其置于当前节点的右子树。如果右子树为空，则直接插入。
如果待插入的值等于当前节点的值，则可以根据实际需求选择是忽略还是进行其他操作（如计数）。

查找操作：

从根节点开始，比较要查找的值与当前节点的值。
如果当前节点为空或等于要查找的值，则返回当前节点。
如果要查找的值小于当前节点的值，则在左子树上进行递归查找。
如果要查找的值大于当前节点的值，则在右子树上进行递归查找。

删除操作：

首先，要找到要删除的目标节点。通过查找操作定位到目标节点。
如果目标节点没有子节点，可以直接删除。
如果目标节点只有一个子节点，将该子节点替代目标节点。
如果目标节点有两个子节点，可以选择以下两种方式进行删除：

找到目标节点的左子树中的最大值（或右子树中的最小值），用它来替代目标节点，然后再删除这个最大（小）节点。
或者找到目标节点的右子树中的最小值（或左子树中的最大值），用它来替代目标节点，然后再删除这个最小（大）节点。

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

算法优缺点

BST（Binary Search Tree，二叉搜索树）作为一种常用的数据结构，具有如下优点和缺点：

优点：

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

缺点：

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

总结来说，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();
    }
}

算法——BST

算法简介

算法原理

算法优缺点

使用场景

代码实现

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

热门文章

最新文章

相关课程

相关电子书

相关实验场景