赞
踩
记忆是一张很小的渔网,只能网住很少的鱼,并且漏走所有的水。
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
从上述概念以及图中可以看出,二叉搜索树具有以下特性:
public static class TreeNode {
// 定义节点的三个属性
int val; // 节点的值
TreeNode left; // 子节点的引用,指向左子树
TreeNode right; // 子节点的引用,指向右子树
// 构造函数,用于创建一个具有指定值的节点
public TreeNode(int val) {
this.val = val;
}
}
既然将其称之为二叉搜索树,因此这棵树最主要的作用是进行查询,而且其查询原理特别简单,具体如下:
假如要查找一个值val,
举个例子:在以下二分搜索树中寻找 43 元素
//查找 public TreeNode search(int key) { // 初始化一个指针cur,指向根节点root TreeNode cur = root; // 开始一个while循环,只要cur不为null,就继续查找 while (cur != null) { // 如果cur节点的值小于key,说明key应该在cur的右子树中 if (cur.val < key) { // 将cur更新为其右子节点,继续在右子树中查找 cur = cur.right; // 如果cur节点的值大于key,说明key应该在cur的左子树中 } else if (cur.val > key) { // 将cur更新为其左子节点,继续在左子树中查找 cur = cur.left; // 如果cur节点的值等于key,说明找到了匹配的节点 } else { // 直接返回当前节点 return cur; } } //没找到,返回null return null; }
关于二叉搜索树的插入,我们首先要知道:
原因:
- 新插入的节点最终会位于叶子节点上。这是因为插入操作会从根节点开始,沿着树向下寻找合适的位置来放置新节点。新节点会与路径上的每个节点进行比较,直到找到一个空的位置(即叶子节点),然后将新节点插入到这个位置。
- 如果允许插入重复的元素,那么这些重复的元素既可以放在左子树也可以放在右子树,这会破坏二叉搜索树的性质,导致树的结构混乱,从而影响搜索、插入和删除等操作的效率。
二叉搜索树插入新节点的一般步骤:
举个例子:向如下二分搜索树中插入元素 61
// 插入操作,将给定值插入到二叉搜索树中 public void insert(int val) { // 创建一个新节点 TreeNode node = new TreeNode(val); // 如果根节点为空,则将新节点作为根节点 if (root == null) { root = node; return; } // 定义当前节点为根节点,父节点初始化为空 TreeNode cur = root; TreeNode parent = null; // 在二叉搜索树中查找插入位置 while (cur != null) { parent = cur; if (cur.val < val) { // 如果当前节点值小于插入值,则向右子树移动 cur = cur.right; } else if (cur.val > val) { // 如果当前节点值大于插入值,则向左子树移动 cur = cur.left; } else { //在二叉搜索树中相同的值不能重新插入 return; } } // 将新节点插入到找到的位置 if (parent.val < val) { // 如果父节点值小于插入值,则将新节点作为右子节点 parent.right = node; } else { // 如果父节点值大于插入值,则将新节点作为左子节点 parent.left = node; } }
对于二叉搜索树的删除,相对来说就比较麻烦了。因为要考虑以下三种情况:
1.要删除的是叶子结点
2.要删除的结点只有一个孩子结点
3.要删除的结点有左、右两棵子树
一. 删除只有左孩子的节点,如下图节点 58。
删除掉元素 58,让左子树直接代替 58 的位置,整个二分搜索树的性质不变。
二. 删除只有右孩子的节点,如下图节点 58。
删除掉元素 58,让右子树直接代替 58 的位置,整个二分搜索树的性质不变。
三.删除左右都有孩子的节点,如下图节点 58。
a.找到右子树中的最小值,为节点 59(替罪羊)
b.节点 59 代替待删除节点 58,并删除掉节点59
小小的总结一下:
根据该节点的子节点情况,分三种情况进行删除:
- 如果要删除的节点没有左子节点,则将该节点的右子节点替换该节点。
- 如果要删除的节点没有右子节点,则将该节点的左子节点替换该节点。
- 如果要删除的节点既有左子节点又有右子节点,则找到该节点右子树中最小的节点(替罪羊),将该节点的值替换为要删除的节点的值,然后删除该节点。
// 删除给定值的节点 public boolean remove(int key) { TreeNode cur = root; // 从根节点开始查找 TreeNode parent = null; // 记录当前节点的父节点 while (cur != null) { // 循环直到找到节点或者遍历完整棵树 if (cur.val > key) { // 如果当前节点值大于要删除的值 parent = cur; // 记录当前节点为父节点 cur = cur.left; // 向左子树移动 } else if (cur.val < key) { // 如果当前节点值小于要删除的值 parent = cur; // 记录当前节点为父节点 cur = cur.right; // 向右子树移动 } else { // 如果当前节点值等于要删除的值 // 找到了要删除的节点,开始删除 removeNode(cur, parent); return true; // 返回删除成功 } } return false; // 没有找到要删除的值,返回删除失败 } // 删除节点的具体操作 public void removeNode(TreeNode cur, TreeNode parent) { if(cur.left == null) { // 如果要删除的节点没有左子树 if(cur == root) { // 如果要删除的节点是根节点 root = cur.right; // 将根节点指向其右子节点 } else if (cur == parent.right) { // 如果要删除的节点是父节点的右子节点 parent.right = cur.right; // 将父节点的右子节点指向要删除节点的右子节点 } else { // 如果要删除的节点是父节点的左子节点 parent.left = 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 { // 如果要删除的节点既有左子树又有右子树 // 找到要删除节点的右子树中的最小节点,即右子树中的最左节点 TreeNode remove = cur.right; TreeNode prev = cur; while (remove.left != null) { // 循环找到最左节点 prev = remove; // 记录当前节点为前一个节点 remove = remove.left; // 向左移动 } cur.val = remove.val; // 将当前节点的值替换为最小节点的值 if(cur == prev) { // 如果要删除的节点的右子树只有一个节点 cur.right = remove.right; // 将当前节点的右子树指向最小节点的右子树 } else { // 如果要删除的节点的右子树有多个节点 prev.left = remove.right; // 将最小节点的父节点的左子树指向最小节点的右子树 } } }
插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:
l
o
g
2
(
N
)
log_2(N)
log2(N)
最差情况下,二叉搜索树退化为单支树,其平均比较次数为:
N
/
2
N/2
N/2
public class BinarySearchTree { public static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } public TreeNode root = null; //插入 public void insert(int val) { TreeNode node = new TreeNode(val); if (root == null) { root = node; return; } TreeNode cur = root; TreeNode parent = null; while (cur != null) { parent = cur; if (cur.val < val) { cur = cur.right; } else if (cur.val > val) { cur = cur.left; } else { //在二叉搜索树中相同的值不能重新插入 return; } } if (parent.val < val) { parent.right = node; } else { parent.left = node; } } //查找 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; } //删除key的值 public boolean remove(int key) { TreeNode cur = root; TreeNode parent = null; while (cur != null) { if (cur.val > key) { parent = cur; cur = cur.left; } else if (cur.val < key) { parent = cur; cur = cur.right; } else { //找到了,开始删除 removeNode(cur, parent); return true; } } return false; } public void removeNode(TreeNode cur, TreeNode parent) { if(cur.left == null) { if(cur == root) { root = cur.right; } else if (cur == parent.right) { parent.right = cur.right; } else { parent.left = 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 { //都不为空 TreeNode remove = cur.right; TreeNode prev = cur; while (remove.left != null) { prev = remove; remove = remove.left; } cur.val = remove.val; if(cur == prev) { cur.right = remove.right; } else { prev.left = remove.right; } } } }
请给自己些耐心,不要急于求成。
山外青山楼外楼,莫把百尺当尽头。
保持空杯心态加油努力吧!
都看到这里啦!真棒(*^▽^*)
可以给作者一个免费的赞赞吗,这将会鼓励我继续创作,谢谢大家
如有纰漏或错误,欢迎指正
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。