最近这阵工作,我越来越感受到基础知识能力的重要性。
之前都是在赶进度、做业务逻辑,逃避自己基础薄弱的事实。
最近下定决心,加强之前薄弱的基础。先从自己之前一直似是而非的搜索树的内容开始吧。
在生活中我们经常会使用到搜索的功能。在我们数据量不大的情况下,可以使用每次遍历
全部数据,查询我们的目标数据。当数据量增加时,我们遍历的方式就有些力不从心了;也可以将数据的数据排序,使用比较高效的二分查找
方式,但是在插入或删除数据时,数组
表现就会很慢。所以我们可以结合二分查找
查询的高效 + 链表
添加删除的高效性来实现高效搜索(符号表)的情况
下面我将列举一些树的内容定义(后续所有的代码使用Java语言实现)
NULL
或者其他真实存在的节点度
;树的度是指所有的子节点中最大的度(将度为2的树称为二叉树、度为3的树称为三叉树等)。如图1~3示 如图-1的B、C、D节点
图-1的A节点是B、C、D节点的父节点
图-3的A节点是B、C、D的父节点,同时也是H节点的子节点
图-1的B、C、D
//二叉搜索树的节点定义
查找
//查询算法
根据查找二叉树的特性,极值存在于叶节点或者只包含一个子节点的父节点中
//查询极小值,一直向左查询,如果没有左节点,则认为当前节点最小 例子:A节点
public TreeNode<T> findMin(TreeNode<T> node){
if (Objects.isNull(node.getLeft())) {
return node;
}
return findMin(node.getLeft());
}
//查询极大值,一直向右查询,如果没有右节点,则认为当前节点最大 例子:Z节点
public TreeNode<T> findMax(TreeNode<T> node){
if (Objects.isNull(node.getRight())) {
return node;
}
return findMax(node.getRight());
}
图-7展示了插入Z的作为F右子节点的情况(插入到左子节点的情况类似,不再赘叙)
图-8展示了被插入节点存在的情况。
public void add(T element) {
if (element == null) {
throw new RuntimeException("数据不能为NULL");
}
TreeNode<T> node = new TreeNode<>();
node.data = element;
if (Objects.isNull(root)) {
root = node;
return;
}
addImpl(root, node);
}
private void addImpl(TreeNode<T> root, TreeNode<T> node) {
T val = root.data;
T element = node.data;
int sub = element.compareTo(val);
//包含要插入的值,不处理
if (sub == 0) {
return;
}
//插入的值大于根节点的值,将新节点作为根节点的右子节点
if (sub > 0) {
TreeNode<T> right = root.getRight();
if (Objects.isNull(right)) {
root.setRight(node);
return;
}
addImpl(right, node);
} else { //插入的值小于根节点的值,将新节点作为根节点的左子节点
TreeNode<T> left = root.getLeft();
if (Objects.isNull(left)) {
root.setLeft(node);
return;
}
addImpl(root.getLeft(), node);
}
}
由于删除节点比较复杂,我们先看下删除极大值(极小值)的情况,为节点删除做好准备工作
由于二叉搜索树的特点二(左子边节点的Key小于父节点、右子节点的Key大于父节点)那么最小值节点要么是叶子节点或者包含右子节点的情况
//移除最小的节点,将返回的值作为根节点
private TreeNode<T> deleteMin(TreeNode<T> node) {
if (Objects.isNull(node.getLeft())) { //没有左子节点,返回右子节点
return node.getRight();
}
TreeNode<T> min = deleteMin(node.getLeft()); //递归左子树
node.setLeft(min);
return node;
}
和删除最小值的情况相似。只不过递归的是右子树
//移除node节点的最大值,使用返回值替换原节点
我们将删除节点的情况归纳如下
//删除element的节点,返回根结点的引用
public TreeNode<T> delete(T element, TreeNode<T> node){
if (Objects.isNull(node)) {
return null;
}
T val = node.data;
int res = val.compareTo(element);
if (res < 0) { //被删除节点在node的右子树
TreeNode<T> rNode = delete(element, node.getRight());
node.setRight(rNode);
} else if (res > 0) { //被删除节点在node的左子树
TreeNode<T> lNode = delete(element, node.getLeft());
node.setLeft(lNode);
} else { //node为被删除节点
//包含一个子节点,使用子节点替换父节点
if (Objects.isNull(node.getLeft())) {
return node.getRight();
}
if (Objects.isNull(node.getRight())) {
return node.getLeft();
}
//左右节点均存在,使用后继节点代替,移除后继节点
TreeNode<T> tmp = node;
node = findMin(node.getRight());
TreeNode<T> rNode = deleteMin(tmp.getRight());
node.setRight(rNode);
node.setLeft(tmp.getLeft());
}
return node;
}
至此,我们已经完成了二叉搜索树的增加、查询、删除的方法。我们发现二叉搜索树的实现并不困难,并且在大多数场景下也能正常运行。二叉搜索树在极端情况的性能也是不可忍受的。
后面我们将讲述一种在任何场景初始化,运行时间都将是对数级的(下一篇预告平衡查找树)
本文是在工作之余整理出来的,难免出现逻辑纰漏、排版错误,还请各位客官理解,同时欢迎各位留言和我交流分享!
本文分享自 javascript艺术 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!