二叉排序树：数据存储的艺术

2023-11-13 18:24:40 浏览数 (1)

前言

  • hello，大家好，我是 Lorin，今天给大家带来数据结构系列，二叉树中的一种特殊类型-二叉搜索树BST，又称二叉排序树或二叉查找树，比如我们我们常见的 AVL 树、B树、B 树都是BST的变种。

二叉搜索树（Binary Search Tree，BST）

定义

  • 二叉搜索树，又称二叉排序树或二叉查找树，是一种常见的二叉树数据结构。它具有以下特点：
代码语言：txt复制
1、每个节点最多有两个子节点，分别为左子节点和右子节点。
2、左子节点的值小于或等于父节点的值。右子节点的值大于父节点的值。
3、对BST进行中序遍历，可以得到升序排列的节点值序列。

时间复杂度

  • 查找（Search）：O(log n) - 平均情况，最坏情况为O(n)，当BST退化成链表时。
  • 插入（Insertion）：O(log n) - 平均情况，最坏情况为O(n)。
  • 删除（Deletion）：O(log n) - 平均情况，最坏情况为O(n)。

空间复杂度

  • 空间复杂度为O(n)，其中n是BST的节点数量，主要是用于存储树结构本身。

树操作

插入

代码语言：txt复制
从根节点开始，比较待插入的值与当前节点的值。
若待插入的值小于当前节点的值，移至左子树；否则，移至右子树。
重复以上步骤，直到找到一个为空的位置，将待插入的值放入此位置。

查找

代码语言：txt复制
从根节点开始，比较待查找的值与当前节点的值。
若待查找的值等于当前节点的值，返回当前节点；若小于当前节点的值，移至左子树；否则，移至右子树。
重复以上步骤，直到找到目标值或者遇到空节点。

删除

代码语言：txt复制
先查找到待删除节点。
如果节点没有子节点，直接删除；如果有一个子节点，用子节点替代待删除节点；
如果有两个子节点，用右子树中的最小值节点（或左子树的最大值节点）替代待删除节点，然后删除最小值节点（或最大值节点）。

Java 版实现

代码语言：java复制
元素：54,25,36,47,36,88,11,86,60

import java.util.ArrayList;
import java.util.Arrays;

class TreeNode {
    Integer val;
    TreeNode left, right;

    public TreeNode(Integer val) {
        this.val = val;
    }
}

public class Test2 {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(54, 25, 36, 47, 36, 88, 11, 86, 60
        ));
        // 构建BST
        TreeNode root = null;
        for (Integer val : arr) {
            if (root == null) {
                root = new TreeNode(val);
            }
            addNode(root, val);
        }

        // 54 25 11 36 47 88 86 60
        dlr(root);
        System.out.println();
        ldr(root);
        System.out.println();

        System.out.println(searchNode(root, 1));
        System.out.println(searchNode(root, 54));
        System.out.println(searchNode(root, 33));

        // del
        assert root != null;
        final int delVal = 54;
        delNode(root, delVal, null);

        dlr(root);
        System.out.println();
        ldr(root);
    }

    private static void del(TreeNode node, TreeNode preRoot) {
        // 判断节点是否存在子节点 若不存在直接删除该节点
        if (node.left == null && node.right == null) {
            // 判断 node 是 preRoot 的左节点还是右节点
            if (node.val > preRoot.val) {
                preRoot.right = null;
            } else {
                preRoot.left = null;
            }
        } else if (node.left == null) {
            preRoot.right = node.right;
        } else if (node.right == null) {
            preRoot.left = node.left;
        } else {
            // 使用左子树的最大节点代替待删除节点并删除最大节点
            TreeNode maxNode;
            if (node.left.right == null) {
                maxNode = node;
                preRoot.left = maxNode.left;
            } else {
                maxNode = getAndDelLeftTreeMax(node.left, node);
            }
            node.val = maxNode.val;
        }
    }

    /**
     * 获取最大左子树最大节点，并移除该节点
     *
     * @param node
     * @param preRoot
     * @return
     */
    private static TreeNode getAndDelLeftTreeMax(TreeNode node, TreeNode preRoot) {
        if (node.right == null) {
            preRoot.right = node.left;
            return node;
        }
        return getAndDelLeftTreeMax(node.right, node);
    }

    /**
     * if not found ,return -1
     * or return searchVal
     *
     * @param root
     * @param searchVal
     * @return
     */
    private static Integer searchNode(TreeNode root, int searchVal) {
        if (root == null) {
            return -1;
        }

        if (root.val == searchVal) {
            return root.val;
        } else if (searchVal > root.val) {
            return searchNode(root.right, searchVal);
        } else {
            return searchNode(root.left, searchVal);
        }
    }

    /**
     * 删除树中的节点值
     *
     * @param root
     * @param val
     * @param preNode
     * @return
     */
    private static boolean delNode(TreeNode root, int val, TreeNode preNode) {
        if (root == null) {
            return false;
        }

        if (root.val == val) {
            del(root, preNode);
            return true;
        } else if (val > root.val) {
            return delNode(root.right, val, root);
        } else {
            return delNode(root.left, val, root);
        }
    }

    /**
     * 添加节点
     *
     * @param node
     * @param val
     */
    private static void addNode(TreeNode node, Integer val) {
        if (node.val.equals(val)) {
            return;
        }

        if (node.val > val) {
            if (node.left != null) {
                addNode(node.left, val);
            } else {
                node.left = new TreeNode(val);
            }

        } else {
            if (node.right != null) {
                addNode(node.right, val);
            } else {
                node.right = new TreeNode(val);
            }
        }
    }

    /**
     * 先根遍历
     *
     * @param root
     */
    private static void dlr(TreeNode root) {
        // 二叉树的先根遍历
        if (root != null) {
            System.out.print(root.val   " ");
            dlr(root.left);
            dlr(root.right);
        }
    }

    /**
     * 中根遍历
     *
     * @param root
     */
    private static void ldr(TreeNode root) {
        // 二叉树的先根遍历
        if (root != null) {
            ldr(root.left);
            System.out.print(root.val   " ");
            ldr(root.right);
        }
    }
}

优缺点

优点

快速的查找操作
  • BST的查找操作平均时间复杂度为O(log n)，使得它在大多数情况下非常高效。这是因为每次比较都能将搜索范围减半。
有序性
  • BST中的数据以有序的方式存储，中序遍历BST可以输出有序的数据序列，这对某些应用非常有用，如范围查询。
支持插入和删除操作
  • BST可以轻松支持插入和删除操作，并且在平均情况下，它们的时间复杂度也是O(log n)。
内存效率
  • 相对于一些其他数据结构（如哈希表），BST通常具有更好的内存使用效率，因为它们只需要存储节点和指针，不需要提前分配大块的内存。

缺点

不平衡性
  • BST在最坏情况下可能会退化成一个链表，导致查找、插入和删除操作的时间复杂度变为O(n)。为了解决这个问题，需要使用平衡二叉搜索树（如AVL树、红黑树）来确保树的平衡性。
对数据分布敏感
  • BST的性能高度依赖于数据的分布。如果数据按照某种有序方式插入，树将会变得不平衡，从而影响性能。
删除操作复杂性
  • BST中的删除操作相对复杂，因为它需要考虑多种情况，包括节点没有子节点、有一个子节点或有两个子节点。这可能需要额外的代码来处理。

使用场景

  • 由于BST的不平衡性和对数据库分布敏感的原因，实际运用中并不会直接使用BST而是基于BST的变种平衡二叉搜索树（如AVL树、红黑树）或多叉树（如B树、B 树）等，运用于数据库索引、文件系统等场景。

个人简介

数据结构 2023腾讯·技术创作特训营第三期数据结构

0 人点赞