JAVA-数据结构- 二叉搜索树

1.搜索树

 前面我们已经使用C语言学习完了二叉树，懂得了一些二叉树的基本性质已经实现方法 https://mp.csdn.net/mp_blog/creation/editor/139572374，本文我们来一起进行二叉树的衍生-二叉搜索树

1.1 概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

简单来说，就是给二叉树定义为左右节点，左子树比根节点小，右子树比根节点大

 

1.2简单实现二叉搜索树的增加和删除

1.2.1创建二叉搜索树

 1.首先在搜索树内定义一个静态类来表示初始二叉树 ，定义出右指针，左指针，根节点，其他的交给二叉树的增加即可

 static class TreeNode{//在类中使用一个整体类来表示二叉树，要用静态类int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root;//定义根节点

2.判断输入值是否存在搜索树中

将输入的值和根节点比较，大于就将根节点向右移，小于就将根节点的值向左移，直到找到为止，找不到就返回false.

 public boolean search(int val){//创建二叉搜索树TreeNode cur = root;while(cur !=null){if(cur.val >val){cur = cur.left;}else if(cur.val<val){cur = cur.right;}else {return true;}}return false;}

1.2.2向二叉搜索树内添加元素

首先进行判空，将要赋值的数放在二叉树类里

1.判断要添加的值要放在哪，和判断是否存在一个道理，但是需要找到根节点的上一个指针，方便插入。

比方说我们要在这么个搜索二叉树内插入4

1.   4比5小，所以往左走，

2.   4比3大，所以往右走，发现cur为空，则停止

3.  将parent.right 赋值为4

 public void insert(int val){//二叉搜索树的添加TreeNode noot = new TreeNode(val);if(root == null){root = noot;//若为空，添加进来的元素则为根节点return;}TreeNode parent = null;//负责记录cur的上一个指针TreeNode cur = root;while(cur!=null){//若cur为零则说明parent的左指针或者右指针已经为插入位置if(val>cur.val){parent = cur;cur = cur.right;}else if(val<cur.val){parent = cur;cur = cur.left;}else{return;//如果找到就没必要添加了}}if(val>parent.val){parent.right=noot;//此时cur是叶子节点，所以需要有parent这个变量}else {parent.left = noot;}}

 1.2.3删除搜索树内的元素（难点）

思路：首先得先找到删除节点的位置  然后我们将删除分为三种情况：

1.删除的元素的左子树 == null

1.1  cur == root

当需要删除的元素在根节点时，直接将根节点右子树改为根节点即可

root = cur.right;

1.2  cur == parent.right

 parent.right = cur.right

由图可得， 

1.3cur == parent.left

parent.left = cur.right 

2.删除的元素的右子树 == null(和上面一样)

1.1  cur == root

1.2  cur == parent.right

1.3cur == parent.left

3.删除的元素左子树 == null && 右子树 == null（难点）

这时我们可以采用替换法，找到搜索树中同样适合放在删除位置的元素进行交换

这时 我们可以把左子树的最大值找到，也可以将右子树的最小值找到

 此时我们在删除的时候可能会面对以下情况

我们发现cur == 10的情况可以和9,15进行交换，此时我们任选一个即可

接下来我就统一使用找右子树最小值来写，找右子树的最小值，一定是根节点的左子树，所以我们需要找target.left == null的位置，此时target为cur右子树的最小值

其中，target负责找到最小值的位置，targetParent负责给target擦屁股，连接target的右子树

首先，将target定义为cur.right,targetParent = cur

然后遍历搜索树找到替换节点 

 然后将target位置的值给到cur

 

targetParent.left指向target.right

 记得考虑特殊情况

target一开始就没有left

 

所以找到替换位置后需要判断target和targetParent的位置关系

当 target在targetParent右边时需要特殊处理

删除总代码实现

 public void remove(int key) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val < key) {parent = cur;cur = cur.right;}else if(cur.val > key) {parent = cur;cur = cur.left;}else {removeNode(cur,parent);//找到需要删除的位置return;}}}public void removeNode(TreeNode cur,TreeNode parent){if(cur.left == null){if(cur == root){//当根节点为删除点时root = cur.right;}else if(cur == parent.left){//当cur是parent的左节点parent.left = cur.right;}else{//当cur是parent的右节点parent.right = cur.right;}}else if(cur.right == null){if(cur == root) {//当根节点为删除点时root = cur.left;}else if(parent.left == cur){//当cur是parent的右节点parent.left = cur.left;}else {//当cur是parent的左节点parent.right = cur.left;}}else{TreeNode target = cur.right,targetparent = cur;//targetParent是为了方便替换后，直接连接下一个节点while(target.left!=null){targetparent = target;target = target.left;}cur.val = target.val;//将替换值赋值给需要删除位置的值if(targetparent.right == target) {//对一开始就没有left的target进行特殊处理targetparent.right = target.right;}else {targetparent.left = target.right;}}

1.3性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

最好情况：最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2 **n

最坏情况：单分支二叉树其平均比较次数为：n/2