【数据结构 Java版】了解二叉搜索树
2021/11/17 9:09:44
本文主要是介绍【数据结构 Java版】了解二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 1. 概念
- 2. 操作
- 2.1 查找
- 2.2 插入
- 2.3 删除
- 3. 性能分析及优化
1. 概念
二叉搜索树(又称二叉排序树),它可以是一棵空树,也可以是一棵具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有的节点的值都小于根节点的值
- 若它的右子树不为空,则右子树上所有的节点的值都大于根节点的值
- 它的左子树和右子树也都为二叉搜索树
通过性质,我们也容易得出一个结论:
可以通过中序遍历来判断这棵二叉树是否为搜索二叉树,如果结果有序,则是搜索二叉树
示例图:
2. 操作
在进行下面搜索二叉树的几个操作实现之前,我们先写一个基本的搜索二叉树类,在这个类中来实现我们的操作
实现代码:
public class BinarySearchTree { // 将节点直接定义在二叉树类的内部 static class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int val){ this.val=val; } } // 查找 // 插入 // 删除 }
2.1 查找
思想:
- 若节点不为空:
- 如果根节点 key == 查找值 key,返回 true
- 如果根节点 key > 查找值 key,在其左子树继续查找
- 如果根节点 key < 查找值 key,在其右子树继续查找
- 否则返回 false
实现代码:
// 查找 public TreeNode search(TreeNode root,int key){ while(root!=null){ if(root.val==key){ return root; }else if(root.val>key){ root=root.left; }else{ root=root.right; } } return null; }
2.2 插入
思想:
- 若跟节点为空,则在根节点插入
- 若不为空,则找到数值应该插入的叶子节点,来进行判断插入
实现代码:
public void insertTree(int key){ if (root==null){ root=new TreeNode(key); } TreeNode cur=root; TreeNode parent=null; while(cur!=null){ if(cur.val<key){ parent=cur; cur=cur.right; }else{ parent=cur; cur=cur.left; } } TreeNode node=new TreeNode(key); if(parent.val<key){ parent.right=node; }else{ parent.left=node; } }
2.3 删除
思想:
- 先通过查找找到要删除的节点,再设置一个节点记为其父节点
- 找到删除的节点之后
- 若待删除的结点的左节点为空
- 如果待删除结点为根节点,让根节点为右子树即可
- 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的右子树即可
- 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的右子树即可
- 若待删除的结点的右结点为空
- 如果待删除结点为根节点,让根节点为左子树即可
- 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的左子树即可
- 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的左子树即可
- 若待删除的结点的左右节点都不为空,那么使用替换法,找到左子树的最大值或者右子树的最小值,来将待删除结点给替换,这样,我们只要再将将其替换的结点删除即可
实现代码:
public void remove(int key){ TreeNode cur=root; TreeNode parent=null; while(cur!=null){ if(cur.val<key){ parent=cur; cur=cur.right; }else if(cur.val==key){ removeNode(cur,parent); }else{ parent=cur; cur=cur.left; } } } public void removeNode(TreeNode cur,TreeNode parent){ if(cur.left==null){ if(cur==root){ root=cur.right; } else if(cur==parent.left){ parent.left=cur.right; } else if(cur==parent.right){ 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 if(cur==parent.right){ parent.right=cur.left; } }else{ TreeNode tp=cur; TreeNode target=cur.right; while (target.left!=null) { tp = target; target = target.left; } cur.val=target.val; if(tp.left==target){ tp.left=target.right; }else{ tp.right=target.right; } } }
3. 性能分析及优化
通过分析,我们发现删除和插入操作之前都必须先查找,故查找效率代表了二叉搜索树的这几个操作的性能
以下来分析下两种特殊的搜索二叉树的查找的时间复杂度
-
完全二叉树(时间复杂度为:
O(logN)
) -
单支二叉树(时间复杂度为:
O(N)
)
如果是一棵单支树的话,时间复杂度其实就达到了 O(N),为了优化的更快则出现了:AVL 树、红黑树
这篇关于【数据结构 Java版】了解二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南