数据结构和算法(二叉搜索树)

た入场券 2024-03-31 08:50 73阅读 0赞

#### 概述 ####

二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。

> 二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：
> 
> 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
> 
> 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

#### 在二叉搜索树中实现搜索操作 - 介绍 ####

二叉搜索树主要支持三个操作：搜索、插入和删除。 在本章中，我们将讨论如何在二叉搜索树中搜索特定的值。

> 根据BST的特性，对于每个节点：
> 
> 如果目标值等于节点的值，则返回节点；
> 
> 如果目标值小于节点的值，则继续在左子树中搜索；
> 
> 如果目标值大于节点的值，则继续在右子树中搜索。

#### 在二叉搜索树中实现插入操作 - 介绍 ####

二叉搜索树中的另一个常见操作是插入一个新节点。有许多不同的方法去插入新节点，这篇文章中，我们只讨论一种使整体操作变化最小的经典方法。 它的主要思想是为目标节点找出合适的叶节点位置，然后将该节点作为叶节点插入。 因此，搜索将成为插入的起始。

与搜索操作类似，对于每个节点，我们将：

>  *  根据节点值与目标节点值的关系，搜索左子树或右子树；
>  *  重复步骤 1 直到到达外部节点；
>  *  根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。

举例:(来源力扣)

[二叉搜索树中的插入操作][Link 1]

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

输入：root = \[40,20,60,10,30,50,70\], val = 25

输出：\[40,20,60,10,30,50,70,null,null,25\]

插入一个数,需要考虑的是判断跟根节点的大小来判断插入哪一个子树,如果下面没有子树,则直接进行插入就可以了,如果有子树,就需要继续比较大小,知道到达叶子节点.

class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if(root==null){
                return new TreeNode(val);
            }
            if(root.val>val){
                root.left=insertIntoBST(root.left,val);
            }else{
                root.right=insertIntoBST(root.right,val);
            }
            return root;
        }
    }

class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null) {
                return new TreeNode(val);
            }
            TreeNode pos = root;
            while (pos != null) {
                if (val < pos.val) {
                    if (pos.left == null) {
                        pos.left = new TreeNode(val);
                        break;
                    } else {
                        pos = pos.left;
                    }
                } else {
                    if (pos.right == null) {
                        pos.right = new TreeNode(val);
                        break;
                    } else {
                        pos = pos.right;
                    }
                }
            }
            return root;
        }
    }

#### 在二叉搜索树中实现删除操作 - 介绍 ####

删除要比我们前面提到过的两种操作复杂许多。有许多不同的删除节点的方法，这篇文章中，我们只讨论一种使整体操作变化最小的方法。我们的方案是用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数，我们需考虑以下三种情况：

>  *  1. 如果目标节点没有子节点，我们可以直接移除该目标节点。
>  *  2. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
>  *  3. 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。

举例:(来源力扣)

[删除二叉搜索树中的节点][Link 2]

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；

如果找到了，删除它。

输入：root = \[5,3,6,2,4,null,7\], key = 3

输出：\[5,4,6,2,null,null,7\]

解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 \[5,4,6,2,null,null,7\], 如下图所示。

另一个正确答案是 \[5,2,6,null,4,null,7\]。

class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            if (key < root.val) {
                // 待删除节点在左子树中
                root.left = deleteNode(root.left, key);
                return root;
            } else if (key > root.val) {
                // 待删除节点在右子树中
                root.right = deleteNode(root.right, key);
                return root;
            } else {
                // key == root.val，root 为待删除节点
                if (root.left == null) {
                    // 返回右子树作为新的根
                    return root.right;
                } else if (root.right == null) {
                    // 返回左子树作为新的根
                    return root.left;
                } else {
                    // 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
                    TreeNode successor = min(root.right);
                    successor.right = deleteMin(root.right);
                    successor.left = root.left;
                    return successor;
                }
            }
        }
    
        private TreeNode min(TreeNode node) {
            if (node.left == null) {
                return node;
            }
            return min(node.left);
        }
    
        private TreeNode deleteMin(TreeNode node) {
            if (node.left == null) {
                return node.right;
            }
            node.left = deleteMin(node.left);
            return node;
        }
    }

class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            if (root.val > key) {
                root.left = deleteNode(root.left, key);
                return root;
            }
            if (root.val < key) {
                root.right = deleteNode(root.right, key);
                return root;
            }
            if (root.val == key) {
                if (root.left == null && root.right == null) {
                    return null;
                }
                if (root.right == null) {
                    return root.left;
                }
                if (root.left == null) {
                    return root.right;
                }
                TreeNode successor = root.right;
                while (successor.left != null) {
                    successor = successor.left;
                }
                root.right = deleteNode(root.right, successor.val);
                successor.right = root.right;
                successor.left = root.left;
                return successor;
            }
            return root;
        }
    }

[Link 1]: https://leetcode.cn/problems/insert-into-a-binary-search-tree/
[Link 2]: https://leetcode.cn/problems/delete-node-in-a-bst/