本文主要是介绍【数据结构】二叉搜索树的功能实现详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 二叉搜索树
- 查找
- 插入
- 删除
- 找到要删除的节点
- 删除节点
- 1. 要删除节点的左孩子为空
- 2. 要删除节点的右孩子为空
- 3. 要删除的节点的左右孩子都不为空
- 完整代码
二叉搜索树
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
其中序遍历是一颗有序的树
查找
二叉搜索树的查找效率非常高
- 因为二叉搜索树的左边都比我小,右边都比我大
- 要找比我小的树,就只需要在左树中找,直接最多可以去掉一半的数据
- 每次到达一个根节点都可以一次性排除掉最多一半的数据
时间复杂度:
- 最好情况下: O ( l o g N ) O(logN) O(logN)
- 最坏情况下: O ( N ) O(N) O(N),单分支,将整棵树遍历完
因为这颗二叉搜索树是由一个一个节点构成的,所以先定义出节点
- 左孩子
- 右孩子
- 节点的值
并定义出头结点
public class BinarySearchTree { static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public TreeNode root = null;
}
每次去看一下 cur
的 val
和我们要找的 key
的大小关系
- 如果
cur.val < key
,那么就往右边走 - 如果
cur.val > key
,那么就往左边走 - 如果
cur.val = key
,那么就找到了
public TreeNode search(int key) { TreeNode cur = root; while(cur != null) { if(cur.val < key) { cur = cur.right; } else if (cur.val > key) { cur = cur.left; }else return cur; } return null;
}
插入
所有的插入都是插入到了叶子节点
-
原来的树为空,则直接插入
-
当树不为空时
若要找到需要插入到的叶子结点的位置,就需要定位到最后父亲节点的叶子结点为null
的时候。但当cur
走到叶子结点的时候,就找不到此叶子结点的父亲节点了,所以需要多一个parent
节点,用来记录当前的父亲节点,好方便随时可以定位到目标叶子结点的父亲节点,后续通过父亲节点进行赋值操作
public void insert(int key) { TreeNode node = new TreeNode(key); TreeNode cur = root; TreeNode parent = null; while (cur != null) { if (cur.val < key) { parent = cur; cur = cur.right; } else if (cur.val > key) { parent = cur; cur = cur.left; } else { return; } } //此循环走完,parent 指向的节点就是需要插入的节点位置的父亲节点 if (parent.val > key) { parent.left = node; } else (parent.val < key) { parent.right = node; }
}
- 值相同的时候,不能进行重复插入
while
循环结束,cur
指向要插入的叶子结点,parent
指向需要插入的节点的父亲节点- 之后对父亲节点和
key
进行比较,选择插入哪一边
删除
删除包含很多种情况
- 需要删除的节点的左孩子为空
- 需要删除的节点的右孩子为空
- 需要删除的节点的左右孩子都不为空
找到要删除的节点
首先需要找到需要删除的节点
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) { parent = cur; cur = cur.left; }else { //此时就是找到了要删除的节点 removeNode(parent,cur); return; } }
}
- 当执行到
else
的时候,就是找到要删除的节点了 - 随后完善删除操作==>
removeNode
删除节点
1. 要删除节点的左孩子为空
cur
是root
,则root = cur.right
cur
不是root
,cur
是parent.left
,则parent.left = cur.right
cur
不是root
,cur
是parent.right
,则parent.right = cur.right
// 1.当要删除的节点 cur 的左孩子为空
if (cur.left == null) { if (cur == root) { // 1.1 要删除的 cur 为根节点 root = cur.right; } else if (cur == parent.left) { // 1.2 要删除的 cur 是 parent 的左节点 parent.left = cur.right; } else { // 1.3 要删除的 cur 是 parent 的右节点 parent.right = cur.right; }
}
2. 要删除节点的右孩子为空
cur
是root
,则root = cur.left
cur
不是root
,cur
是parent.left
,则parent.left = cur.left
cur
不是root
,cur
是parent.right
,则parent.right = cur.left
// 2. 要删除的节点 cur 的右孩子为空
else if (cur.right == null) { if (cur == root) { // 2.1 要删除的 cur 是根节点 root = cur.left; } else if (cur == parent.left) { // 2.2 要删除的 cur 是 parent 的左节点 parent.left = cur.left; } else { // 2.3 要删除的 cur 是 parent 的右节点 parent.right = cur.left; }
}
3. 要删除的节点的左右孩子都不为空
需要使用 替换法 进行删除
-
在它的右子树中寻找一个最小的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题
- 因为要删除的节点
cur
左边都比它小,右边都比它大,所以就在cur
的右边找到一个最小的节点,然后让目标节点覆盖掉 cur - 目标节点不会出现左右孩子都存在的情况。要么两边都为空,要么还存在一个右节点。(既然此节点是最小的,就不可能还有左子树,因为左子树肯定比此节点小)
- 因为要删除的节点
-
在它的左子树中寻找一个最大的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题
- 此时这个最大值一定是在左树的最右边,意味着它肯定没有右子树
所以找到最小值的特征是:
- 此节点左子树为空,且一定在
cur
右树的最左边 - 此节点右子树为空,且一定在
cur
左树的最右边
寻找右子树的最小值
// 3.1 右数的最小值
TreeNode t = cur.right;
TreeNode tp = cur;
while (t.left != null) { tp = t; t = tp.left;
}
cur.val = t.val;
if(t == tp.right) {
//t 和 tp 在起始步就找到了最小值tp.right = t.right;
}else{
//t 和 tp 在继续移动的过程中找到最小值tp.left = t.right;
}
t
是用来定位最小值的,当t.left == null
的时候,t
就是最小值tp
是用来定位t
的父节点的,方便后续对节点进行删除(因为节点的删除都要依靠删除节点的父节点进行“改变连接对象”)- 在没找到最小节点之前,
tp
和t
一起进行移动- 最开始
tp
在要删除的节点cur
的位置,t
在cur
的右节点(起始步) tp
走到t
的位置t
再走向tp
的左节点(一轮移动结束)t.left != null
,tp
走到t
的位置t
再走向tp
的左节点(一轮移动结束)- …
- 最开始
- 如果在起始步就满足
t.left == null
了,则直接进行
完整代码
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) { parent = cur; cur = cur.left; } else { //此时就是找到了要删除的节点 removeNode(parent, cur); return; } }
} private void removeNode(TreeNode parent, TreeNode cur) { // 1.当要删除的节点 cur 的左孩子为空 if (cur.left == null) { if (cur == root) { // 1.1 要删除的 cur 为根节点 root = cur.right; } else if (cur == parent.left) { // 1.2 要删除的 cur 是 parent 的左节点 parent.left = cur.right; } else { // 1.3 要删除的 cur 是 parent 的右节点 parent.right = cur.right; } // 2. 要删除的节点 cur 的右孩子为空 } else if (cur.right == null) { if (cur == root) { // 2.1 要删除的 cur 是根节点 root = cur.left; } else if (cur == parent.left) { // 2.2 要删除的 cur 是 parent 的左节点 parent.left = cur.left; } else { // 2.3 要删除的 cur 是 parent 的右节点 parent.right = cur.left; } // 3. 要删除的节点的左右孩子都不为空 } else { // 3.1 右数的最小值 TreeNode t = cur.right; TreeNode tp = cur; while (t.left != null) { tp = t; t = tp.left; } cur.val = t.val; if(t == tp.right) { //t 和 tp 在起始步就找到了最小值 tp.right = t.right; }else{ //t 和 tp 在继续移动的过程中找到最小值 tp.left = t.right; } }
}
这篇关于【数据结构】二叉搜索树的功能实现详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!