娄底建设网站制作搭建一个app需要什么

娄底建设网站制作,搭建一个app需要什么,移动应用网站开发阶段作业,企业官网开发公司二叉排序树删除操作详解 二叉排序树#xff08;Binary Search Tree#xff0c;BST#xff09;是一种重要的数据结构#xff0c;它满足以下性质#xff1a;对于树中的每个节点#xff0c;其左子树所有节点的值都小于该节点的值#xff0c;右子树所有节点的值都大于该节点…二叉排序树删除操作详解二叉排序树Binary Search TreeBST是一种重要的数据结构它满足以下性质对于树中的每个节点其左子树所有节点的值都小于该节点的值右子树所有节点的值都大于该节点的值。删除操作是BST中最复杂的操作之一需要根据被删除节点的子树情况分别处理。删除叶子节点叶子节点是指没有左右子树的节点。删除这类节点相对简单只需要将其父节点对应的指针置空即可。处理步骤包括找到要删除的节点 targetNode找到targetNode的父节点parentNode(判断是否存在)确定targetNode是parentNode的左子树还是右子树根据以上的情况进行删除左节点:parentNode.lChild null右节点:parentNode.rChild null这种操作不会影响树的其他部分因为叶子节点不包含任何子树信息。时间复杂度为O(h)h为树的高度。删除单子树节点当节点只有一个子树时需要将该节点的子树提升到被删除节点的位置。具体处理需要考虑找到要删除的节点 targetNode找到targetNode的父节点parentNode(判断是否存在)确定targetNode是parentNode的左子树还是右子树判断targetNode的子节点是targetNode的左子树还是右子树(1). targetNode是parentNode的左子树① targetNode有左子结点parentNode.lChild targetNode.lChild② targetNode有右子结点parentNode.lChild targetNode.rChild(2). targetNode是parentNode的右子树① targetNode有左子结点parentNode.rChild targetNode.lChild② targetNode有右子结点parentNode.rChild targetNode.rChild这种操作保持了BST的性质因为子树中的所有节点都满足与被删除节点父节点的大小关系。算法复杂度同样为O(h)。删除双子树节点这是最复杂的情况通常采用以下策略之一用右子树的最小值替代被删除节点用左子树的最大值替代被删除节点示例代码选择第一种策略具体实现包括找到右子树的最小节点即最左节点用该节点的值替换被删除节点的值递归删除该最小节点这种方法保证了BST的性质因为右子树的最小值大于左子树所有节点小于右子树其他节点。时间复杂度为O(h)。关键方法实现public TreeNode findTarget(TreeNode root,Integer target){ if (root null){ return null; } if (root.data target){ return root; }else if (target root.data){ if (root.lchild null){ return null; } return findTarget(root.lchild,target); }else if (target root.data){ if (root.rchild null){ return null; } return findTarget(root.rchild,target); } return null; }findTarget方法采用递归方式查找目标节点利用BST的性质缩小搜索范围。比较当前节点值与目标值决定搜索方向直到找到匹配节点或到达叶子节点。public TreeNode findParent(TreeNode root,Integer target){ if (root null){ return null; } if((root.lchild!null root.lchild.data target)||(root.rchild!null root.rchild.data target)){ return root; }else { if(root.lchild!null target root.data){ return findParent(root.lchild,target); }else if(root.rchild!null target root.data){ return findParent(root.rchild,target); }else { return null; } } }findParent方法递归查找目标节点的父节点通过检查左右子节点是否匹配目标值来确定父节点位置。public int findRightTreeMin(TreeNode node){ while (node.lchild ! null){ node node.lchild; } int min node.data; delete(root,min); return min; }findRightTreeMin方法通过迭代找到右子树的最左节点即最小值节点。这是处理双子树删除的关键辅助方法。public void delete(TreeNode root,Integer target){ if (root null){ return; } if (root.lchild null root.rchild null){ root null; return; } TreeNode targetNode findTarget(root,target); if (targetNode null){ return; } TreeNode parentNode findParent(root,target); if (targetNode.lchild null targetNode.rchild null){//叶子结点 if (parentNode.lchild ! null parentNode.lchild.data target){ parentNode.lchild null; }else if (parentNode.rchild ! null parentNode.rchild.data target){ parentNode.rchild null; } }else if (targetNode.lchild ! null targetNode.rchild ! null){//有左右子树 int min findRightTreeMin(targetNode.rchild); targetNode.data min; }else {//有一个子树 if (parentNode.lchild ! null parentNode.lchild.data target){ if (targetNode.lchild ! null){ parentNode.lchild targetNode.lchild; }else { parentNode.lchild targetNode.rchild; } }else if (parentNode.rchild ! null parentNode.rchild.data target){ if (targetNode.lchild ! null){ parentNode.rchild targetNode.lchild; }else { parentNode.rchild targetNode.rchild; } } } }delete方法是核心删除逻辑处理三种不同情况叶子节点直接删除单子树节点用子树替代双子树节点用右子树最小值替换后删除原最小值节点性能分析二叉排序树的删除操作性能与树的高度直接相关。在平衡情况下时间复杂度为O(log n)最坏情况下树退化为链表时间复杂度为O(n)。因此在实际应用中常使用平衡二叉搜索树如AVL树、红黑树来保证操作效率。删除操作的正确性依赖于BST的性质维护每次删除后仍需保持左子树根节点右子树的关系。示例代码通过三种情况的分别处理确保了这一性质的保持。