文章目录
- 二叉搜索树
- 1. 二叉搜索树的概念
- 2. 二叉树操作 - 查找
- 3. 二叉树操作 - 插入
- 4. 二叉树操作 - 删除
- 5. 性能分析
二叉搜索树 1. 二叉搜索树的概念 二叉搜索树又称二叉排序树，它或者是一棵空树**，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
文章图片
2. 二叉树操作 - 查找
文章图片
代码实现:
public Node search(int val){
while (root != null){
if(val > root.val){// val>root.val 在右子树查找
root = root.right;
}else if(val < root.val){// val3. 二叉树操作 - 插入 【数据结构|数据结构 Java数据结构 --- 二叉搜索树】
文章图片
代码实现:
public boolean insert(int val) {
// 当为空树的时候 直接插入val
if(root == null) {
root = new Node(val);
return true;
}
// 当不为空时的时候,进行判断
Node parent = null;
Node child = root;
while (child != null){
// val 较大 寻找右子树
if(child.val < val){
parent = child;
child = child.right;
}else {//val 较小 寻找左子树
parent = child;
child = child.left;
}
}
// 这里 parent的左子树或右子树就可以进行插入,此时进行判断.
if(parent.val < val){
parent.right = new Node(val);
}else {
parent.left = new Node(val);
}
return true;
}
4. 二叉树操作 - 删除
文章图片
文章图片
public void remove(int key) {
Node cur = root;
Node parent = null;
while (cur != null){
if(cur.val == key){
//找到要删除的节点 进行删除
removeNode(cur,parent);
}else if(cur.val < key){
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
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.right){
parent.right = cur.left;
}else {
parent.left = cur.left;
}
}else { // 情况三
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;
}
}
}
5. 性能分析 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树
文章图片
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
文章图片
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：
文章图片
推荐阅读
- 数据结构|数据结构 Java数据结构 --- 十大排序
- Java|Java SE --- 内部类
- 数据结构|数据结构 Java数据结构 ---- 堆(优先级队列)
- 数据结构|数据结构 Java数据结构 --- 二叉树
- java|java 基础数据结构_Java实现的基础数据结构
- 笔记|咖啡汪对敖丙老哥Java后端面试心得体会————阿里一面
- java|java 反射的概念
- 面试笔试|2022春招华为笔试题-（2）
- java|咸鱼疯传5W次，字节最新春招面试题泄露