数据结构和算法(二叉搜索树)
概述
二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质:每个节点中的值必须大于(或等于)其左侧子树中的任何值,但小于(或等于)其右侧子树中的任何值。
二叉搜索树(BST)是二叉树的一种特殊表示形式,它满足如下特性:
每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。
每个节点中的值必须小于(或等于)存储在其右子树中的任何值。
在二叉搜索树中实现搜索操作 - 介绍
二叉搜索树主要支持三个操作:搜索、插入和删除。 在本章中,我们将讨论如何在二叉搜索树中搜索特定的值。
根据BST的特性,对于每个节点:
如果目标值等于节点的值,则返回节点;
如果目标值小于节点的值,则继续在左子树中搜索;
如果目标值大于节点的值,则继续在右子树中搜索。
在二叉搜索树中实现插入操作 - 介绍
二叉搜索树中的另一个常见操作是插入一个新节点。有许多不同的方法去插入新节点,这篇文章中,我们只讨论一种使整体操作变化最小的经典方法。 它的主要思想是为目标节点找出合适的叶节点位置,然后将该节点作为叶节点插入。 因此,搜索将成为插入的起始。
与搜索操作类似,对于每个节点,我们将:
- 根据节点值与目标节点值的关系,搜索左子树或右子树;
- 重复步骤 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. 如果目标节点有两个子节点,我们需要用其中序后继节点或者前驱节点来替换,再删除该目标节点。
举例:(来源力扣)
给定一个二叉搜索树的根节点 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;
}
}
- 点赞
- 收藏
- 关注作者
评论(0)