攀枝花做网站,wordpress 分类目录 插件,山西省城乡住房和建设厅网站首页,网页传奇3如何搜索构建一颗二叉搜索树插入删除 如何搜索 在二叉搜索树里搜索值#xff1b;搜索非常类似于二分查找
//查找key是否存在public TreeNode search(int key) {TreeNode cur root;while(cur ! null) {if(cur.key key) {return cur;}else if(cur.key key){cur cur.lef… 如何搜索构建一颗二叉搜索树插入删除 如何搜索 在二叉搜索树里搜索值搜索非常类似于二分查找
//查找key是否存在public TreeNode search(int key) {TreeNode cur root;while(cur ! null) {if(cur.key key) {return cur;}else if(cur.key key){cur cur.left;}else {cur cur.right;}}return null;}
最好的情况是这颗搜索树是一个完全二叉树时间复杂度Olog n最坏情况是单边的树时间复杂度O(N)
构建一颗二叉搜索树
假设给你一串没有重复的数字你如何构建出一棵搜索树?
插入
第一次插入的节点是根节点其次每个节点都是在叶子节点的位置插入;cur从根节点开始走cur为空的时候就是我们插入的时候定义一个parent记录cur父亲的位置因为我们cur只是找到空的节点虽然我们是一步一步比较下来但是走下来我们得记录cur是从哪个节点走下来的知道它的父亲才能插入 public boolean insert(int key) {if(root null) {//没有节点的时候得注意直接插入根节点就行root new TreeNode(key);}TreeNode prev null;TreeNode cur root;while(cur ! null) { //找位置if(cur.val key) {//值相同时不给插入return false;}else if(cur.val key) {prev cur;cur cur.left;}else { prev cur;cur cur.right;}}//上述找到cur为空但是不知道是左边还是右边走下来空了所以我们需要和父亲比较一下if(prev.val key) {prev.left new TreeNode(key);}else {prev.right new TreeNode(key);}return true;}删除
假设删除结点为 cur, 待删除结点的双亲结点为 parent 删除分三种情况 大前提1cur.leftnull 左边没有树 1删除根节点cur是root删除方案rootcur.right。
2删除上一个根节点的左孩子 cur是parent.left删除方案parent.leftcur.right 3cur 是 parent.right 删除方案parent.right cur.right 实现 找位置先
大前提2cur.rightnull 右边没有树 1删除根节点删除方案rootcur.left 2:cur 是 parent.left删除方案parent.left cur.left 3cur是patent.right解决方案parent.rightcur.left
大前提3左右都不为空例如删除12 第三种并不是真正意义上的删除两种方式找到左边的最大值或者右边的最小值。也就是左边的最右或者右边的最左。9或者13.然后一步一步找到这个位置把我的12改成13或者9然后再让这个9等于它自己的右边或者13等于13的左边。这样这个节点就变为空了. 如果右边的左为空只有右。就直接把25给12然后25指向16删除这个重复的25
整体代码 public void removeNode(TreeNode preant,TreeNode cur){if(cur.leftnull){if(curroot){rootcur.right;}else if(curpreant.left){preant.leftcur.right;}else {preant.rightcur.right;}} else if(cur.rightnull){if(curroot){rootcur.left;}else if(curpreant.left){preant.leftcur.left;}else {preant.rightcur.left;}}else {//两边都不为空TreeNode targetcur.right;TreeNode targetParentcur;while (target.left!null){targetParenttarget;targettarget.left;}cur.valtarget.val;if(targettargetParent.left) {targetParent.left target.right;}else {targetParent.righttarget.right;}}}
