jsp做网站用什么封装字符串,wordpress图片网站,做网站要费用多少,wordpress知识库模板文章目录 1 什么是二叉搜索树1.1 二叉搜索树的特征1.2 前驱后继 2 二叉搜索树的Java实现2.1 定义二叉搜索树节点类BSTNode泛型key改进 2.2 实现查找方法get(int key)递归实现非递归实现 ★非递归实现 泛型key版本 2.3 实现查找最小方法min()递归实现非递归实现 ★ 2.4 实现查找… 文章目录 1 什么是二叉搜索树1.1 二叉搜索树的特征1.2 前驱后继 2 二叉搜索树的Java实现2.1 定义二叉搜索树节点类BSTNode泛型key改进 2.2 实现查找方法get(int key)递归实现非递归实现 ★非递归实现 泛型key版本 2.3 实现查找最小方法min()递归实现非递归实现 ★ 2.4 实现查找最大方法max()递归实现非递归实现 ★ 2.5 实现新增方法put(int key, Object value)递归实现非递归实现 ★ 2.6 实现查找关键字的前任值predecessor(int key)2.7 查找关键字的后任值successor(int key)2.8 根据关键字删除remove(int key)非递归实现 ★递归实现 3 二叉搜索树——范围查询3.1 找所有小于索引的值less(int key)3.2 找所有大于索引的值greater(int key)3.3 找范围值between(int key1, int key2)3.3 小结 前言本文章为瑞_系列专栏之《数据结构与算法》的二叉搜索树篇。由于博主是从B站黑马程序员的《数据结构与算法》学习到的相关知识所以本系列专栏主要针对该课程进行笔记总结和拓展文中的部分原理及图解也是来源于黑马提供的资料。本文仅供大家交流、学习及研究使用禁止用于商业用途违者必究 1 什么是二叉搜索树 二叉搜索树最早是由Bernoulli兄弟在18世纪中提出的但是真正推广和应用该数据结构的是1960年代的D.L. Gries。他的著作《The Science of Programming》中详细介绍了二叉搜索树的实现和应用。 在计算机科学的发展中二叉搜索树成为了一种非常基础的数据结构被广泛应用在各种领域包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究二叉搜索树也不断被优化和扩展例如AVL树、红黑树等。
1.1 二叉搜索树的特征 二叉搜索树也称二叉排序树是符合下面特征的二叉树
树节点增加 key 属性用来比较谁大谁小key 不可以重复对于任意一个树节点它的 key 比左子树的 key 都大同时也比右子树的 key 都小例如下图所示 轻易看出要查找 7 从根开始自然就可应用二分查找算法只需三次比较
与 4 比较之大向右找与 6 比较之大继续向右找与 7 比相等即找到 查找的时间复杂度与树高相关插入、删除也是如此。
如果这棵树长得还不赖左右平衡如上图那么时间复杂度均是 O ( log N ) O(\log{N}) O(logN)当然这棵树如果长得丑左右高度相差过大如下图那么这时是最糟的情况链表时间复杂度是 O ( N ) O(N) O(N) 注 二叉搜索树 - 英文 binary search tree简称 BST二叉排序树 - 英文 binary ordered tree 或 binary sorted tree 二叉树的相关知识可以参考博客《瑞_数据结构与算法_二叉树》 二分查找的相关知识可以参考博客瑞_数据结构与算法_二分查找 1.2 前驱后继
前驱值前任值找到一个离该节点最近且比该节点存储值小的值后继值后任值找到一个离该节点最近且比该节点存储值大的值 2 二叉搜索树的Java实现 以简单实现为主主要是学习其思想和Java中的Map集合实现的思维类似通过key查找value 内部节点类BSTNode中含有属性
索引存储值左孩子右孩子属性
BSTTree二叉搜索树类含有方法
查找关键字对应的值get(int key)查找最小关键字对应值min()查找最大关键字对应值max()存储关键字和对应值put(int key, Object value)查找关键字的前任值predecessor(int key)查找关键字的后任值successor(int key)根据关键字删除remove(int key)
2.1 定义二叉搜索树节点类BSTNode BSTNode即二叉搜索树节点类内部类含有索引、存储值、左孩子、右孩子属性由于是简单实现索引定义基本数据类型若希望任意类型作为 key则后续可以将其设计为 Comparable 接口
/*** Binary Search Tree 二叉搜索树** author LiaoYuXing-Ray* version 1.0* createDate 2024/1/24 19:27**/
public class BSTTree {/*** 根节点*/BSTNode root;static class BSTNode {// 索引比较值int key;// 该节点的存储值Object value;// 左孩子BSTNode left;// 右孩子BSTNode right;public BSTNode(int key) {this.key key;}public BSTNode(int key, Object value) {this.key key;this.value value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key key;this.value value;this.left left;this.right right;}}}泛型key改进 使用泛型上限语法让泛型的Key继承Comparable接口使其能够进行大小比较。改进后代码如下含get方法
/*** 二叉搜索树, 泛型 key 版本*/
public class BSTTreeK extends ComparableK, V {static class BSTNodeK, V {K key;V value;BSTNodeK, V left;BSTNodeK, V right;public BSTNode(K key) {this.key key;}public BSTNode(K key, V value) {this.key key;this.value value;}public BSTNode(K key, V value, BSTNodeK, V left, BSTNodeK, V right) {this.key key;this.value value;this.left left;this.right right;}}BSTNodeK, V root;public V get(K key) {if (key null) {return null;}BSTNodeK, V node root;while (node ! null) {int result key.compareTo(node.key);if (result 0) {node node.left;} else if (result 0) {node node.right;} else {return node.value;}}return null;}
} 瑞此处泛型没有定义为T而定义K是因为K、V迎合map集合中的keyvalue容易理解 2.2 实现查找方法get(int key) get(int key)方法通过关键字查找对应的值
递归实现 get(int key)方法是通过key索引关键字查找对应的值可以使用递归查找 /*** h3查找关键字对应的值/h3** param key 关键字* return 关键字对应的值*/public Object get(int key) {return doGet(root, key);}/*** 私有 - 封装BSTNode参数外部只需要调用get(int key)方法即可不用关心具体细节** param node 根节点* param key 索引关键字 * return java.lang.Object 关键字对应的值* author LiaoYuXing-Ray 2024/1/24 19:53**/private Object doGet(BSTNode node, int key) {if (node null) {return null; // 没找到}if (key node.key) {return doGet(node.left, key); // 向左找} else if (node.key key) {return doGet(node.right, key); // 向右找} else {return node.value; // 找到了}}瑞该递归实现是尾递归 尾递归是一种特殊形式的递归它的特点是在函数的最后一步调用自身并且不需要保留外层函数的调用记录。 注意区别伪递归伪递归通常指的是使用迭代实现的递归算法它们在逻辑上模拟了递归的过程但实际上并不通过函数调用自身来实现。 尾递归的特点 在函数的最后一步调用自身不保留外层函数的调用记录。可以仅使用常量级的栈空间与迭代过程类似。有着与循环同样优秀的计算性能。 伪递归的特点使用迭代来模拟递归的逻辑。不涉及实际的函数自我调用。通常用于那些不支持尾递归优化的编程语言中以减少内存消耗。 方法测试代码如下
/*** Binary Search Tree 二叉搜索树** author LiaoYuXing-Ray* version 1.0* createDate 2024/1/24 19:27**/
public class BSTTree {/*** 根节点*/BSTNode root;static class BSTNode {// 索引比较值int key;// 该节点的存储值Object value;// 左孩子BSTNode left;// 右孩子BSTNode right;public BSTNode(int key) {this.key key;}public BSTNode(int key, Object value) {this.key key;this.value value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key key;this.value value;this.left left;this.right right;}}/*** h3查找关键字对应的值/h3* 递归实现** param key 关键字* return 关键字对应的值*/public Object get(int key) {return doGet(root, key);}/*** 私有 - 封装BSTNode参数外部只需要调用get(int key)方法即可不用关心具体细节** param node 根节点* param key 索引关键字* return java.lang.Object 关键字对应的值* author LiaoYuXing-Ray 2024/1/24 19:53**/private Object doGet(BSTNode node, int key) {if (node null) {return null; // 没找到}if (key node.key) {return doGet(node.left, key); // 向左找} else if (node.key key) {return doGet(node.right, key); // 向右找} else {return node.value; // 找到了}}public static void main(String[] args) {/*4/ \2 6/ \ / \1 3 5 7*/BSTNode n1 new BSTNode(1, Ray1);BSTNode n3 new BSTNode(3, Ray3);BSTNode n2 new BSTNode(2, Ray2, n1, n3);BSTNode n5 new BSTNode(5, Ray5);BSTNode n7 new BSTNode(7, Ray7);BSTNode n6 new BSTNode(6, Ray6, n5, n7);BSTNode root new BSTNode(4, Ray4, n2, n6);BSTTree tree new BSTTree();tree.root root;for (int i 0; i 8; i) {System.out.println(tree.get(i));}}}运行结果如下找不到索引为0和8的元素存储值而1-7都能找到符合预期 nullRay1Ray2Ray3Ray4Ray5Ray6Ray7null非递归实现 ★ 由于之前使用的是尾递归实现而尾递归转换成迭代法是非常容易的性能上也能有所提升所以一般情况下如果使用尾递归都会转化为迭代法。 /*** h3查找关键字对应的值/h3* 非递归实现** param key 关键字* return 关键字对应的值*/public Object get(int key) {BSTNode node root;while (node ! null) {if (key node.key) {// 向左找node node.left;} else if (node.key key) {// 向右找node node.right;} else {// 找到return node.value;}}// 没找到return null;}瑞测试用例可以使用同一个同样能通过且性能更佳。 非递归实现 泛型key版本 如果希望让除 int 外更多的类型能够作为 key一种方式是 key 必须实现 Comparable 接口。 由于compareTo方法返回-1表示key node.key0表示key node.key1表示key node.key所以改进后代码如下 public V get(K key) {BSTNodeK, V node root;while (node ! null) {/*-1 key p.key0 key p.key1 key p.key*/int result key.compareTo(node.key);if (result 0) {node node.left;} else if (result 0) {node node.right;} else {return node.value;}}return null;}还有一种做法不要求 key 实现 Comparable 接口而是在构造 Tree 时把比较规则作为 Comparator 传入将来比较 key 大小时都调用此 Comparator 进行比较这种做法可以参考 Java 中的 java.util.TreeMap 方法测试代码如下
/*** 二叉搜索树, 泛型 key 版本*/
public class BSTTreeK extends ComparableK, V {static class BSTNodeK, V {K key;V value;BSTNodeK, V left;BSTNodeK, V right;public BSTNode(K key) {this.key key;}public BSTNode(K key, V value) {this.key key;this.value value;}public BSTNode(K key, V value, BSTNodeK, V left, BSTNodeK, V right) {this.key key;this.value value;this.left left;this.right right;}}BSTNodeK, V root;public V get(K key) {if (key null) {return null;}BSTNodeK, V node root;while (node ! null) {/*-1 key node.key0 key node.key1 key node.key*/int result key.compareTo(node.key);if (result 0) {node node.left;} else if (result 0) {node node.right;} else {return node.value;}}return null;}public static void main(String[] args) {BSTNodeString,String n1 new BSTNode(a, RayA);BSTNodeString,String n3 new BSTNode(c, RayC);BSTNodeString,String n2 new BSTNode(b, RayB, n1, n3);BSTNodeString,String n5 new BSTNode(e,RayE);BSTNodeString,String n7 new BSTNode(g,RayG);BSTNodeString,String n6 new BSTNode(f, RayF, n5, n7);BSTNodeString,String root new BSTNode(d, RayD, n2, n6);BSTTreeString,String tree new BSTTree();tree.root root;System.out.println(tree.get(a));System.out.println(tree.get(b));System.out.println(tree.get(c));System.out.println(tree.get(d));System.out.println(tree.get(e));System.out.println(tree.get(f));System.out.println(tree.get(g));System.out.println(tree.get(h));}
} 运行结果如下符合预期 RayARayBRayCRayDRayERayFRayGnull由于使用泛型代码阅读对新手会比较困难本文主要是学习思想所以后续方法采用int类型作为key 2.3 实现查找最小方法min() min()方法查找最小关键字key的对应存储值
递归实现 根据二叉搜索树的特征树中最左的节点即为最小索引关键字即向左走到头即可所以只要左孩子为null即找到最小关键字使用递归实现的代码就非常简单如下 /*** h3查找最小关键字对应值/h3* 递归实现** return 关键字对应的值*/public Object min() {return doMin(root);}public Object doMin(BSTNode node) {if (node null) {return null;}// 左边已走到头if (node.left null) {return node.value;}return doMin(node.left);}非递归实现 ★ 由于之前使用的是尾递归实现所以下面转化为迭代法代码如下 /*** h3查找最小关键字对应值/h3* 非递归实现** return 关键字对应的值*/public Object min() {return min(root);}private Object min(BSTNode node) {if (node null) {return null;}BSTNode p node;// 左边未走到头while (p.left ! null) {p p.left;}return p.value;}方法测试代码如下 public static void main(String[] args) {/*4/ \2 6/ \ / \1 3 5 7*/BSTNode n1 new BSTNode(1, Ray1);BSTNode n3 new BSTNode(3, Ray3);BSTNode n2 new BSTNode(2, Ray2, n1, n3);BSTNode n5 new BSTNode(5, Ray5);BSTNode n7 new BSTNode(7, Ray7);BSTNode n6 new BSTNode(6, Ray6, n5, n7);BSTNode root new BSTNode(4, Ray4, n2, n6);BSTTree tree new BSTTree();tree.root root;System.out.println(tree.min()); }运行结果如下查找到最小最左节点索引key为1的存储值Ray1符合预期 Ray12.4 实现查找最大方法max() max()方法查找最大关键字key的对应存储值
递归实现 与min()方法实现的思想类似树中最右的节点即为最大索引关键字即向右走到头即可所以只要右孩子为null即找到最大关键字使用递归实现的代码如下 /*** h3查找最大关键字对应值/h3* 递归实现** return 关键字对应的值*/public Object max() {return doMax(root);}public Object doMax(BSTNode node) {if (node null) {return null;}// 右边已走到头if (node.right null) {return node.value;}return doMax(node.right);}非递归实现 ★ 由于之前使用的是尾递归实现所以下面转化为迭代法代码如下 /*** h3查找最大关键字对应值/h3** return 关键字对应的值*/public Object max() {return max(root);}private Object max(BSTNode node) {if (node null) {return null;}BSTNode p node;while (p.right ! null) {p p.right;}return p.value;} 方法测试代码如下 public static void main(String[] args) {BSTNode n1 new BSTNode(1, Ray1);BSTNode n3 new BSTNode(3, Ray3);BSTNode n2 new BSTNode(2, Ray2, n1, n3);BSTNode n5 new BSTNode(5, Ray5);BSTNode n7 new BSTNode(7, Ray7);BSTNode n6 new BSTNode(6, Ray6, n5, n7);BSTNode root new BSTNode(4, Ray4, n2, n6);BSTTree tree new BSTTree();tree.root root;System.out.println(tree.max());}运行结果如下查找到最大最右节点索引key为7的存储值Ray7符合预期 Ray72.5 实现新增方法put(int key, Object value) 新增put(int key, Object value)方法存储关键字和对应值和Java中的Map的put方法类似分为两种情况 1️⃣ key在整个树中已经存在新增操作变为更新操作将旧的值替换为新的值 2️⃣ key在整个树中未存在执行新增操作将key value添加到树中
递归实现 递归实现思路如下
若找到 key走 else 更新找到节点的值若没找到 key走第一个 if创建并返回新节点 返回的新节点作为上次递归时 node 的左孩子或右孩子缺点是会有很多不必要的赋值操作 /*** h3存储关键字和对应值/h3* 递归实现** param key 关键字* param value 值*/public void put(int key, Object value) {root doPut(root, key, value);}private BSTNode doPut(BSTNode node, int key, Object value) {if (node null) {return new BSTNode(key, value);}if (key node.key) {node.left doPut(node.left, key, value);} else if (node.key key) {node.right doPut(node.right, key, value);} else {node.value value;}return node;}非递归实现 ★ 查找逻辑和get方法的逻辑基本一样区别是如果查找到值则更新node.value value;没查找到则新增。在新增时为了防止频繁的更新操作添加parent父节点判断新增节点是父节点的左孩子还是右孩子然后再新增代码如下 /*** h3存储关键字和对应值/h3* 非递归实现** param key 关键字* param value 值*/public void put(int key, Object value) {BSTNode node root;BSTNode parent null; // 父节点while (node ! null) {parent node;if (key node.key) {node node.left;} else if (node.key key) {node node.right;} else {// 1. key 存在则更新node.value value;return;}}// 2. key 不存在则新增判断新节点是父节点的左孩子还是右孩子// parent 为空代表树为空的情况那新增节点就是根节点if (parent null) {root new BSTNode(key, value);}// 新增节点为左孩子else if (key parent.key) {parent.left new BSTNode(key, value);}// 新增节点为右孩子else {parent.right new BSTNode(key, value);}}测试代码 public static void main(String[] args) {/*4/ \2 6/ \ / \1 3 5 7*/BSTNode n1 new BSTNode(1, Ray1);BSTNode n3 new BSTNode(3, Ray3);BSTNode n2 new BSTNode(2, Ray2, n1, n3);BSTNode n5 new BSTNode(5, Ray5);BSTNode n7 new BSTNode(7, Ray7);BSTNode n6 new BSTNode(6, Ray6, n5, n7);BSTNode root new BSTNode(4, Ray4, n2, n6);BSTTree createTree new BSTTree();createTree.root root;BSTTree tree new BSTTree();tree.put(4, new Object());tree.put(2, new Object());tree.put(6, new Object());tree.put(1, new Object());tree.put(3, new Object());tree.put(5, new Object());tree.put(7, new Object());System.out.println(createTree tree);tree.put(1, Ray486);System.out.println(tree.get(1).equals(Ray486));}两树的key一致但输出false说明不是同样的树索引1的存储值被成功替换均符合预期测试结果如下 falsetrue2.6 实现查找关键字的前任值predecessor(int key) 回顾跳转前驱后继 一个节点的前驱前任节点是指比它小的节点中最大的那个 一个节点的后继后任节点是指比它大的节点中最小的那个 例如上图中
1 没有前驱后继是 22 前驱是 1后继是 33 前驱是 2后继是 4 想要找到二叉搜索树的某节点的前驱后继节点简单但不高效的办法是中序遍历即可获得排序结果此时很容易找到前驱后继。因为使用中序遍历后二叉搜索树的值就是升序的有了升序排序前驱后继节点就很好找。但是由于中序遍历的性能不高所以不推荐使用。 要效率更高需要研究一下规律找前驱分成以下 2 种情况 1️⃣节点 有 左子树此时前驱节点就是左子树的最大值图中属于这种情况的有
2 的前驱是14 的前驱是 36 的前驱是 57 的前驱是 6 2️⃣节点 没有 左子树若离它最近的祖先自从左而来此祖先即为前驱如
3 的祖先 2 自左而来前驱 25 的祖先 4 自左而来前驱 48 的祖先 7 自左而来前驱 71 没有这样的祖先前驱 null 瑞祖先不止是父节点也可以是父节点的父节点父节点的的父节点的父节点… 对于情况2只需要添加一个指针记录最近一个自左而来的祖先即可实现代码如下 /*** h3查找关键字的前任值/h3** param key 关键字* return 前任值*/public Object predecessor(int key) {BSTNode p root;// 自左而来的祖先BSTNode ancestorFromLeft null;while (p ! null) {if (key p.key) {p p.left;} else if (p.key key) {// 记录自左而来的祖先ancestorFromLeft p;p p.right;} else {break;}}// 没找到节点if (p null) {return null;}// 找到节点 情况1节点有左子树此时前任就是左子树的最大值if (p.left ! null) {return max(p.left);}// 找到节点 情况2节点没有左子树若离它最近的、自左而来的祖先就是前任return ancestorFromLeft ! null ?ancestorFromLeft.value : null;}2.7 查找关键字的后任值successor(int key) 回顾跳转前驱后继 一个节点的前驱前任节点是指比它小的节点中最大的那个 一个节点的后继后任节点是指比它大的节点中最小的那个 与前驱类似找后继也分成 2 种情况 1️⃣节点有右子树此时后继节点即为右子树的最小值如
2 的后继 33 的后继 45 的后继 67 的后继 8 2️⃣节点没有右子树若离它最近的祖先自右而来此祖先即为后继如
1 的祖先 2 自右而来后继 24 的祖先 5 自右而来后继 56 的祖先 7 自右而来后继 78 没有这样的祖先后继 null 代码实现和前任类似如下 /*** h3查找关键字的后任值/h3** param key 关键字* return 后任值*/public Object successor(int key) {BSTNode p root;// 自右而来的祖先BSTNode ancestorFromRight null;while (p ! null) {if (key p.key) {// 记录自右而来的祖先ancestorFromRight p;p p.left;} else if (p.key key) {p p.right;} else {break;}}// 没找到节点if (p null) {return null;}// 找到节点 情况1节点有右子树此时后任就是右子树的最小值if (p.right ! null) {return min(p.right);}// 找到节点 情况2节点没有右子树若离它最近的、自右而来的祖先就是后任return ancestorFromRight ! null ?ancestorFromRight.value : null;}2.8 根据关键字删除remove(int key) 删除remove(int key)方法需要考虑的情况较多。要删除某节点称为 D必须先找到被删除节点的父节点这里称为 Parent具体情况如下
删除节点没有左孩子将右孩子托孤给 Parent删除节点没有右孩子将左孩子托孤给 Parent删除节点左右孩子都没有已经被涵盖在情况1、情况2 当中把 null 托孤给 Parent删除节点左右孩子都有可以将它的后继节点称为 S托孤给 Parent设 S 的父亲为 SP又分两种情况 SP 就是被删除节点此时 D 与 S 紧邻只需将 S 托孤给 ParentSP 不是被删除节点此时 D 与 S 不相邻此时需要将 S 的后代托孤给 SP再将 S 托孤给 Parent 删除本身很简单只要通过索引查找到该节点删除即可但是由于需要料理后事所以想要做好删除操作需要处理好“托孤”操作。
非递归实现 ★ 情况3走情况1或者情况2的逻辑都是可以的所以不用管主要是情况4的第二种子情况删除和后继不相邻需要处理好该情况下要删除节点的后任的托孤利用后继节点不会有左孩子如果有左孩子那就不会是最小值所以后继不可能有左孩子再将后继节点托孤给被删除节点的父节点代码如下
/*** h3根据关键字删除/h3* 非递归实现** param key 关键字* return 被删除关键字对应值*/
public Object remove(int key) {BSTNode p root;// 记录待删除节点的父亲BSTNode parent null;while (p ! null) {if (key p.key) {parent p;p p.left;} else if (p.key key) {parent p;p p.right;} else {break;}}if (p null) {return null;}// 删除操作if (p.left null) {shift(parent, p, p.right); // 情况1} else if (p.right null) {shift(parent, p, p.left); // 情况2} else {// 情况4// 4.1 被删除节点找后继BSTNode s p.right;BSTNode sParent p; // 后继父亲while (s.left ! null) {sParent s;s s.left;}// 4.2 删除和后继不相邻, 处理后继的后事if (sParent ! p) { shift(sParent, s, s.right); // 不可能有左孩子否则就不是后继节点s.right p.right;}// 4.3 后继取代被删除节点shift(parent, p, s);s.left p.left;}return p.value;
}/*** 托孤方法** param parent 被删除节点的父亲* param deleted 被删除节点* param child 被顶上去的节点*/
// 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {if (parent null) {// 根节点特殊情况root child;} else if (deleted parent.left) {parent.left child;} else {parent.right child;}
}测试代码 public static void main(String[] args) {/*4/ \2 7/ \ /1 3 6/5*/BSTNode n1 new BSTNode(1, 1);BSTNode n3 new BSTNode(3, 3);BSTNode n2 new BSTNode(2, 2, n1, n3);BSTNode n5 new BSTNode(5, 5);BSTNode n6 new BSTNode(6, 6, n5, null);BSTNode n7 new BSTNode(7, 7, n6, null);BSTNode root1 new BSTNode(4, 4, n2, n7);BSTTree tree1 new BSTTree();tree1.root root1;Object delete tree1.remove(7);System.out.println(delete \t 7); // 7 7// 删除后/*4/ \2 6/ \ /1 3 5*/BSTNode x1 new BSTNode(1, 1);BSTNode x3 new BSTNode(3, 3);BSTNode x2 new BSTNode(2, 2, x1, x3);BSTNode x5 new BSTNode(5, 5);BSTNode x6 new BSTNode(6, 6, x5, null);BSTNode root2 new BSTNode(4, 4, x2, x6);BSTTree tree2 new BSTTree();tree2.root root2;System.out.println(isSameTree(tree1.root,tree2.root)); // true}// 判断是否为同一树key对应的value都相等static boolean isSameTree(BSTNode tree1, BSTNode tree2) {if (tree1 null tree2 null) {return true;}if (tree1 null || tree2 null) {return false;}if (tree1.key ! tree2.key) {return false;}return isSameTree(tree1.left, tree2.left) isSameTree(tree1.right, tree2.right);}测试结果如下删除的元素符合预期且删除后的树与预期结果的结构一致 7 7true递归实现 由于递归实现效率低且较难理解主要是为了结合非递归实现提供思路可以结合注释思考不过多讲解代码如下 /*** h3根据关键字删除/h3* 递归实现** param key 关键字* return 被删除关键字对应值*/public Object remove(int key) {ArrayListObject result new ArrayList(); // 保存被删除节点的值root doRemove(root, key, result);return result.isEmpty() ? null : result.get(0);}/*** 私有 递归删除具体实现细节** param node 起点* param key 删除索引* param result 保存被删除节点的值* return node 删剩下的孩子(找到) 或 null(没找到)* author LiaoYuXing-Ray 2024/1/25 19:59**/private BSTNode doRemove(BSTNode node, int key, ArrayListObject result) {if (node null) {return null;}if (key node.key) {node.left doRemove(node.left, key, result);return node;}if (node.key key) {node.right doRemove(node.right, key, result);return node;}result.add(node.value);if (node.left null) { // 情况1 - 只有右孩子return node.right;}if (node.right null) { // 情况2 - 只有左孩子return node.left;}BSTNode s node.right; // 情况3 - 有两个孩子while (s.left ! null) {s s.left;}s.right doRemove(node.right, s.key, new ArrayList());s.left node.left;return s;}说明
ArrayListObject result 用来保存被删除节点的值第二、第三个 if 对应没找到的情况继续递归查找和删除注意后续的 doRemove返回值代表删剩下的因此需要更新最后一个 return 对应删除节点只有一个孩子的情况返回那个不为空的孩子待删节点自己因没有返回而被删除第四个 if 对应删除节点有两个孩子的情况此时需要找到后继节点并在待删除节点的右子树中删掉后继节点最后用后继节点替代掉待删除节点返回别忘了改变后继节点的左右指针
3 二叉搜索树——范围查询 4/ \2 6/ \ / \1 3 5 73.1 找所有小于索引的值less(int key) less(int key)方法找 key 的所有 value 使用中序遍历 // 找 key 的所有 valuepublic ListObject less(int key) {ArrayListObject result new ArrayList();BSTNode p root;LinkedListBSTNode stack new LinkedList();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;} else {BSTNode pop stack.pop();// 处理值if (pop.key key) {result.add(pop.value);} else {break;}p pop.right;}}return result;}
3.2 找所有大于索引的值greater(int key) greater(int key)方法找 key 的所有 value 使用常规的中序遍历从左向右的中序遍历
public ListObject greater(int key) {ArrayListObject result new ArrayList();BSTNode p root;LinkedListBSTNode stack new LinkedList();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;} else {BSTNode pop stack.pop();if (pop.key key) {result.add(pop.value);}p pop.right;}}return result;
}中序遍历效率不高可以用 RNL 遍历中序遍历的逆操作 注 Pre-order, NLRIn-order, LNRPost-order, LRNReverse pre-order, NRL反向前序遍历值右左Reverse in-order, RNL反向中序遍历右值左Reverse post-order, RLN反向后续序遍历右左值 RNL 遍历代码如下
// 找 key 的所有 value
public ListObject greater(int key) {ArrayListObject result new ArrayList();BSTNode p root;LinkedListBSTNode stack new LinkedList();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.right;} else {BSTNode pop stack.pop();if (pop.key key) {result.add(pop.value);} else {break;}p pop.left;}}return result;
}3.3 找范围值between(int key1, int key2) between(int key1, int key2)方法找 key1 且 key2 的所有值 // 找 key1 且 key2 的所有值public ListObject between(int key1, int key2) {ArrayListObject result new ArrayList();BSTNode p root;LinkedListBSTNode stack new LinkedList();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;} else {BSTNode pop stack.pop();// 处理值if (pop.key key1 pop.key key2) {result.add(pop.value);} else if (pop.key key2) {break;}p pop.right;}}return result;}测试 public static void main(String[] args) {/*4/ \2 6/ \ / \1 3 5 7*/BSTNode n1 new BSTNode(1, 1);BSTNode n3 new BSTNode(3, 3);BSTNode n2 new BSTNode(2, 2, n1, n3);BSTNode n5 new BSTNode(5, 5);BSTNode n7 new BSTNode(7, 7);BSTNode n6 new BSTNode(6, 6, n5, n7);BSTNode root new BSTNode(4, 4, n2, n6);BSTTree tree new BSTTree();tree.root root;System.out.println(tree.less(6));System.out.println(tree.greater(6));System.out.println(tree.between(3,5));}输出如下符合预期 [1, 2, 3, 4, 5][7][3, 4, 5]3.3 小结
优点
如果每个节点的左子树和右子树的大小差距不超过一可以保证搜索操作的时间复杂度是 O(log n)效率高。插入、删除结点等操作也比较容易实现效率也比较高。对于有序数据的查询和处理二叉查找树非常适用可以使用中序遍历得到有序序列。
缺点
如果输入的数据是有序或者近似有序的就会出现极度不平衡的情况可能导致搜索效率下降时间复杂度退化成O(n)。对于频繁地插入、删除操作需要维护平衡二叉查找树例如红黑树、AVL 树等否则搜索效率也会下降。对于存在大量重复数据的情况需要做相应的处理否则会导致树的深度增加搜索效率下降。对于结点过多的情况由于树的空间开销较大可能导致内存消耗过大不适合对内存要求高的场景。 本文是博主的粗浅理解可能存在一些错误或不完善之处如有遗漏或错误欢迎各位补充谢谢 如果觉得这篇文章对您有所帮助的话请动动小手点波关注你的点赞收藏⭐️转发评论都是对博主最好的支持~
