首页 / 知识
搜索树与哈希表详解
2023-04-11 16:19:00
一、搜索树
1.1 概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
它的左右子树也分别为二叉搜索树。
如：
1.2 查找
若根节点不为空：
如果根节点==查找key 返回当前节点；
如果根节点 >查找key在其左子树查找；
如果根节点<查找key在其右子树查找；否则就是没有找到，返回null；
class Node{
public int val;
public Node left;
public Node right;
public Node（int val）{
this.val = val;
}
}
//二叉搜索树
public class BinarySearchTree {
public Node root = null;
//查找
public Node search（int key）{
Node cur = root;
while （cur != null）{
if（cur.val == key）{
return cur;
}else if（cur.val < key）{
cur = cur.right;
}else{
cur = cur.left;
}
}
return null;
}
1.3 插入
用cur和parent来找到val需要存储的位置。
parent.val 和val比较大小，确定是在左边还是在右边进行插入。
public boolean insert（int val） {
if（root == null） {
root = new Node（val）;
return true;
}
Node cur = root;
Node parent = null;
while （cur != null） {
if（cur.val < val） {
parent = cur;
cur = cur.right;
}else if（cur.val == val） {
return false;//不能有相同的数据
}else {
parent = cur;
cur = cur.left;
}
}
Node node = new Node（val）;
if（parent.val < val） {
parent.right = node;
}else {
parent.left = node;
}
return true;
}
1.4 删除
设待删除结点为 cur, 待删除结点的双亲结点为 parent；
cur.left == null
cur 是 root，则 root = cur.right
cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
cur.right == null
cur 是 root，则 root = cur.left
cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
cur.left != null && cur.right != null
需要使用替换法进行删除：
在cur的左树当中找最大值或者在cur的右树中找最小值
用它的值填补到被删除节点中，再来处理该结点的删除问题。
/**
* Created With IntelliJ IDEA
* Description:
* Users: yyyyy
* Date: 2022-02-19
* Time: 16:43
*
*/
class Node{
public int val;
public Node left;
public Node right;
public Node（int val）{
this.val = val;
}
}
//二叉搜索树
public class BinarySearchTree {
public Node root = null;
//查找
public Node search（int key）{
Node cur = root;
while （cur != null）{
if（cur.val == key）{
return cur;
}else if（cur.val < key）{
cur = cur.right;
}else{
cur = cur.left;
}
}
return null;
}
//插入
public boolean insert（int val） {
if（root == null） {
root = new Node（val）;
return true;
}
Node cur = root;
Node parent = null;
while （cur != null） {
if（cur.val < val） {
parent = cur;
cur = cur.right;
}else if（cur.val == val） {
return false;//不能有相同的数据
}else {
parent = cur;
cur = cur.left;
}
}
Node node = new Node（val）;
if（parent.val < val） {
parent.right = node;
}else {
parent.left = node;
}
return true;
}
public void remove（int key）{
Node cur = root;
Node parent = null;
while （cur != null）{
if （cur.val == key）{
removeNode（cur,parent）;
break;
}else if（cur.val < key）{
parent = cur;
cur = cur.right;
}else{
parent = cur;
cur = cur.left;
}
}
}
//cur代表要删除的节点
public void removeNode（Node cur,Node parent）{
if （cur.left == null）{
if（cur == root）{
root = cur.right;
}else if（cur == parent.left）{
parent.left = cur.right;
}else{
parent.right = cur.right;
}
}else if（cur.right == null）{
if（cur == root）{
root = cur.left;
}else if（cur == parent.left）{
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else{//cur的左和右都不为空的情况
//找到cur的右子树的最小值然后进行替换
Node targetParent = cur;
Node target = cur.right;
while （target.left != null）{
targetParent = target;
target = target.left;
}
cur.val = target.val;
if （target == targetParent.left）{
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
public void inOrder（Node root）{
if（root == null）return;
inOrder（root.left）;
System.out.print（root.val + " "）;
inOrder（root.right）;
}
public static void main（String[] args） {
int[] arr = {2,45,19,12,3,8};
BinarySearchTree binarySearchTree = new BinarySearchTree（）;
for （int i = 0; i < arr.length; i++） {
binarySearchTree.insert（arr[i]）;
}
binarySearchTree.inOrder（binarySearchTree.root）;
System.out.println（）;
System.out.println（"插入重复的数"）;
System.out.println（binarySearchTree.insert（2））;
System.out.println（"删除数据"）;
binarySearchTree.remove（2）;
binarySearchTree.inOrder（binarySearchTree.root）;
}
}
|
最新内容
相关内容
python如何读取列表中元素的位置?
python如何读取列表中元素的位置?，位置，数据，异常，培训，字符串，元素，索引，方法，示例，结果，python读取列表中元素位置的方法：1、使用index()方
python如何调用另一个文件夹中的内
python如何调用另一个文件夹中的内容?，系统，培训，文件，模块，内容，路径，函数，所在，前缀，语句，python中调用另外一个文件夹中的内容：1、同一文件
python里小数如何表述?
python里小数如何表述?，银行，培训，小数，位数，问题，精度，表示，以上，存在，更多，1、Python中的小数存在精度问题：>>>0.1+0.1+0.1-0.35.5511151231
python中怎么对一个数进行因式分解
python中怎么对一个数进行因式分解?，代码，培训，因式分解，因数，个数，最小，整数，数组，假定，分解，1、Python因式分解代码：importtime#对一个数进
python中函数怎么表示?
python中函数怎么表示?，名称，标准，培训，代码，函数，圆括号，字符串，表达式，选择性，自变量，python中函数定义规则：·函数代码块以def关键词开头，后
Python怎么取出列表中的相邻元素?
Python怎么取出列表中的相邻元素?，代码，异常，培训，元素，指针，序列，对象，表示，语句，函数，1、python的迭代器。iter()能把一个序列生成为一个和python怎么在数组添加一行?
python怎么在数组添加一行?，培训，下标，维度，数组，列表，函数，形状，元素，代表，原型，python中在数组添加一行的方法：python中可以使用stack()函数
python函数里面形参和实参一样吗?
python函数里面形参和实参一样吗?，培训，函数，参数，里面，变量，实际，形式，全称，示例，后面，python函数里面形参和实参不一样。形参全称是形式参
python判断xml是否存在某一节点?
python判断xml是否存在某一节点?，数据，培训，节点，方法，结果，表达式，长度，以上，更多，内容，python中判断xml是否存在某一节点的方法：使用selectN
python怎么筛选列表中大于0的数据?
python怎么筛选列表中大于0的数据?，数据，培训，函数，结果，以上，方法，更多，内容，列表，python筛选列表中大于0的数据的方法：1、使用匿名函数lamb
python列表有哪些常用方法?
python列表有哪些常用方法?，位置，方法，培训，列表，语法，元素，示例，对象，以上，参数，列表是最常用的Python数据类型，它可以作为一个方括号内的逗
python是一种编程语言吗？
python是一种编程语言吗？，放宽，适当，平台，培训，语言，指令，计算机，机器，程序，解释性，python是一种编程语言，Python是一种跨平台的计算机程序设计