jsp网站开发期末大作业网站设计app

jsp网站开发期末大作业,网站设计app,wordpress 调用时间,高端做网站公司哪家好二分搜索树#xff08;BST#xff09;是一种有序的二叉树#xff0c;也是数据结构中最常用的树形结构之一#xff0c;其核心特性是 “左小右大”#xff0c;这使得它的查找、插入、删除操作的平均时间复杂度可达 \(O(\log n)\)#xff08;最坏为 \(O(n)\)#xff0c;退化…二分搜索树BST是一种有序的二叉树也是数据结构中最常用的树形结构之一其核心特性是 “左小右大”这使得它的查找、插入、删除操作的平均时间复杂度可达 \(O(\log n)\)最坏为 \(O(n)\)退化为链表是高效的动态查找 / 排序数据结构。一、定义一棵二叉树满足以下条件则称为二分搜索树对于任意节点 node其左子树中的所有节点值都 小于 node.val其右子树中的所有节点值都 大于 node.val左、右子树本身也必须是二分搜索树递归定义。可选若需支持重复值可约定左子树 ≤ 当前节点 ≤ 右子树本文默认无重复值。二、BST特性1中序遍历结果有序对 BST 进行中序遍历左→根→右会得到一个升序排列的序列核心特性常用于验证 BST、排序、找前驱 / 后继节点2查找 / 插入 / 删除的高效性每次操作可排除一半子树类似二分查找3无唯一形态同一组数据可构造不同的 BST如插入顺序不同极端情况下会退化为单链表如按升序插入 1,2,3,4,5。三、BST性能特征四、应用场景1动态查找 / 排序支持高效的插入、删除、查找且中序遍历可直接得到有序序列2集合 / 映射实现如 Java TreeSet/TreeMap、C set/map底层为红黑树属于平衡 BST3范围查询如找 “大于 x 且小于 y 的所有节点”利用 BST 的有序性可快速定位边界4前驱 / 后继节点查找如在 BST 中找某个节点的前驱比它小的最大值、后继比它大的最小值用于排序、TopK 问题。五、案例分享题目1给定一棵二分搜索树和两个结点寻找这两个结点的最近公共祖先如下图所示的二分搜索树2和8的最近公共祖先为62和4的最近公共祖先为2。树形结构见下图。public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (null root) return null; // p and q are in the left side of the tree if (root.val q.val root.val p.val) return lowestCommonAncestor(root.left, p, q); // p and q are in the right side of the tree if (root.val q.val root.val p.val) return lowestCommonAncestor(root.right, p, q); // p and q are in the different sides of the treeq or p may be is the root node. return root; }题目2:给定一棵二叉树验证其是否为二分搜索树。思路1根据题目的要求结点的值大于其左孩子结点的值而小于其右孩子结点的值则中序遍历该二叉搜索树时会返回一个有序的列表。但是若是left.valroot.valright.val这种方式就不行了此种方式效率较低。import java.util.LinkedList; import java.util.List; public class LC98 { // 根据题意中序遍历二叉树看看是否升序排列 public boolean isValidBST(TreeNode root) { if (null root) return true; // 此时root肯定不为空 ListInteger nodeValueList new LinkedList(); inOrder(root, nodeValueList); for(int i 0;i nodeValueList.size() - 1;i) { if(nodeValueList.get(i1) nodeValueList.get(i)) return false; } return true; } private void inOrder(TreeNode root, ListInteger nodeValueList) { if(null root) return; inOrder(root.left, nodeValueList); nodeValueList.add(root.val); inOrder(root.right, nodeValueList); } public static void main(String[] args) { TreeNode root new TreeNode(2); root.left new TreeNode(1); root.right new TreeNode(3); System.out.println(result new LC98().isValidBST(root)); } }思路2直接使用二分搜索树的性质左root右public class LC98 { // 根据题意使用其性质直接判断 左root右 public boolean isValidBST(TreeNode root) { if (root null) return true; return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean valid(TreeNode root, long leftValue, long rightValue) { if (root null) return true; if (root.val leftValue || root.val rightValue) return false; return valid(root.left, leftValue, root.val) valid(root.right, root.val, rightValue); } public static void main(String[] args) { TreeNode root new TreeNode(10); root.left new TreeNode(5); root.right new TreeNode(15); root.right.left new TreeNode(6); root.right.right new TreeNode(20); System.out.println(result new LC98().isValidBST(root)); } }