搜索树——二叉搜索树

遗忘： 1. 二叉搜索树的中序遍历是从大到小的排列。

一、概念 它是一颗二叉树，且有如下的特点： ♣ 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。 ♣若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。 ♣它的左右子树也分别为二叉搜索树。 二、常用操作——查找、删除

public class BinarySearchTree { public static class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; } } private Node root = null; //1.查找 public Node search(int val){ Node cur = root; while (cur != null){ if(val < cur.data){ cur = cur.left; }else if(val > cur.data){ cur = cur.right; }else{ return cur; } } return null; } //2.插入 public boolean Insert(int val){ Node node = new Node(val); if (root == null){ root = node; return true; } Node cur = root; Node parent = null; while (cur != null){ if (val < cur.data){ parent = cur; cur = cur.left; }else if(val > cur.data){ parent = cur; cur = cur.right; }else{ return false; } } if (parent.data < val){ parent.right = node; return true; } if (parent.data > val){ parent.left = node; return true; } return false; }

三、常用——删除（♣） 删除某个节点后，需要考虑其余节点仍要保持二叉搜索树的性质。在删除的操作中，要先查找到要删除的节点，再进行删除。

设待删除结点为 cur，待删除结点的双亲结点为 parent，删除节点时需考虑如下状况：

cur.left == null

cur 是 root，则 root = cur.right

cur 不是 root，cur 是 parent.left，则 parent.left = cur.right

cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

cur.right == null

cur 是 root，则 root = cur.left

cur 不是 root，cur 是 parent.left，则 parent.left = cur.left

cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

cur.left != null && cur.right != null 核心：找替罪羊，删除替罪羊

需要使用替换法进行删除。要么在左边找到最大的数字（右树为空了），要么在右边找到最小的数字（左树为空了），直接替换掉要删除的数字，因为：左边这个最大的数字替换了要删除的数后，仍然可以保持左边小右边大的特性。 如果要是找的的右边，那么右边的那个最小数字(taget)，左树为空，所以仍要考虑1.中的后两种情况（target 是 targetParent.left和target 是 targetParent.right）。 反之亦然。

代码以cur的右树找最小为例：

private void removeNode(Node parent,Node cur){ if (cur.left == null){ if (cur == this.root){ root = cur.right; }else if(cur==parent.left){ parent.left = cur.right; }else{ parent.right = cur.right; } }else if (cur.right==null){ if (cur == this.root){ root = cur.left; }else if(cur==parent.left){ parent.left = cur.left; }else { parent.right = cur.left; } //左右树都不为Null }else { Node targetParent = cur; Node target = cur.right; while (target.left != null){ targetParent = target; target = target.left; } //并未删除只是，值的替换 cur.data = target.data; //因为在右边找最小，所以右边最小的左树肯定是空。 //所以在删除时也要考虑两种情况 if (target == targetParent.left){ targetParent.left = target.right; }else{ targetParent.right = target.right; } } }