一文搞懂——搜索树

小灰灰 2024-04-01 16:48 83阅读 0赞

**目录**

1.搜索树的定义

2.插入操作

3.查找操作

4.删除操作

5.性能分析

6.完整代码

--------------------

二叉搜索树又称为二叉排序树，它具有以下性质

> 1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
> 
> 2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
> 
> 3.它的左右子树也为二叉搜索树

以下就是一个二叉搜索树，每个节点的左节点小于父亲节的，右节点大于父亲节点。

![0741d2a1f38e4477a5e5fd406b950c32.png][]

## 1.搜索树的定义 ##

class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int val){
            this.val = val;
        }
    }

## 2.插入操作 ##

首先判断根节点是否为空，为空直接添加，不为空的话就利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”这个特点进行判断，并进行插入。

public boolean insert(int v){
            if(root == null){
                root = new Node(v);
                return true;
            }
            Node parent = null;
            Node cur = root;
            while(cur != null){
                if(cur.val > v){
                    parent = cur;
                    cur = cur.left;
                }else if (cur.val == v){
                    return false;//不能有相同的数据
                }else {
                    parent = cur;
                    cur = cur.right;
                }
            }
            Node node = new Node(v);
            if(parent.val > v){
                parent.left = node;
            }else if(parent.val < v){
                parent.right = node;
            }
            return true;
        }

## 3.查找操作 ##

对于某个元素的查找，利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”，进行判断，直至找到目标节点。

public Node Serach(int v){
            Node cur = root;
            while(cur != null) {
                if (cur.val > v) {
                    cur = cur.left;
                } else if (cur.val == v) {
                    return cur;
                } else {
                    cur = cur.right;
                }
            }
            return null;
        }

## 4.删除操作 ##

删除操作情况及其复杂。

**设待删除结点为 cur,**  **待删除结点的双亲结点为**  **parent**

1. **cur.left == null**

1. cur 是 root ，则  root = cur.right

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

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

2. **cur.right == null**

1. cur 是 root ，则  root = cur.left

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

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

3. **cur.left != null && cur.right != null**

需要使用**替换法** 进行删除，即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点中，再来处理该结点的删除问题。

public void remove(int v){
                Node cur = root;
                Node parent = null;
                while(cur != null){
                    if(cur.val == v){
                        removeNode(cur,parent);
                        break;
                    }else if(cur.val > v){
                        parent = cur;
                        cur = cur.left;
                    }else {
                        parent = cur;
                        cur = cur.right;
                    }
    
                }
            }
            public void removeNode(Node cur,Node parent){
                if(cur.left == null){
                    if(cur == 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 == root){
                        root = cur.left;
                    }else if(cur == parent.left){
                        parent.left = cur.left;
                    }else {
                        parent.right = cur.left;
                    }
                }else {
                    Node targetParent = cur;
                    Node target = cur.right;
                    while(target.left != null){
                        targetParent = target;
                        target = target.left;
    
                    }
                    cur.val = target.val;
                    if(target == targetParent.left){
                        targetParent.left = target.right;
                    }else {
                        targetParent.right = target.right;
                    }
    
                }
            }

## 5.性能分析 ##

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

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

**最优情况：二叉搜索树为完全二叉树，其平均比较次数为 log(2)(N);**

**最差情况：二叉搜索树为单支树，其平均比较次数为 N/2。**

## **6.完整代码** ##

//节点定义
    class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int val){
            this.val = val;
        }
    }
    public class BinarySearchTree {
        public Node root = null;
    
        //搜索操作
        public Node Serach(int v){
            Node cur = root;
            while(cur != null) {
                if (cur.val > v) {
                    cur = cur.left;
                } else if (cur.val == v) {
                    return cur;
                } else {
                    cur = cur.right;
                }
            }
            return null;
        }
    
        //插入操作
        public boolean insert(int v){
            if(root == null){
                root = new Node(v);
                return true;
            }
            Node parent = null;
            Node cur = root;
            while(cur != null){
                if(cur.val > v){
                    parent = cur;
                    cur = cur.left;
                }else if (cur.val == v){
                    return false;//不能有相同的数据
                }else {
                    parent = cur;
                    cur = cur.right;
                }
            }
            Node node = new Node(v);
            if(parent.val > v){
                parent.left = node;
            }else if(parent.val < v){
                parent.right = node;
            }
            return true;
        }
    
            //删除操作
            public void remove(int v){
                Node cur = root;
                Node parent = null;
                while(cur != null){
                    if(cur.val == v){
                        removeNode(cur,parent);
                        break;
                    }else if(cur.val > v){
                        parent = cur;
                        cur = cur.left;
                    }else {
                        parent = cur;
                        cur = cur.right;
                    }
    
                }
            }
    
            //删除操作的具体实现
            public void removeNode(Node cur,Node parent){
                if(cur.left == null){
                    if(cur == 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 == root){
                        root = cur.left;
                    }else if(cur == parent.left){
                        parent.left = cur.left;
                    }else {
                        parent.right = cur.left;
                    }
                }else {
                    Node targetParent = cur;
                    Node target = cur.right;
                    while(target.left != null){
                        targetParent = target;
                        target = target.left;
    
                    }
                    cur.val = target.val;
                    if(target == targetParent.left){
                        targetParent.left = target.right;
                    }else {
                        targetParent.right = target.right;
                    }
    
                }
            }
    
    //中序遍历
        public void inOrder(Node root){
            if(root == null) return;
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
    }

测试用例：

public static void main(String[] args) {
            int[] array = {10,8,19,3,9,4,7};
            BinarySearchTree binarySearchTree = new BinarySearchTree();
            for (int i = 0;i < array.length;i++){
                binarySearchTree.insert(array[i]);
            }
            binarySearchTree.inOrder(binarySearchTree.root);
    
            System.out.println();
            Node node = binarySearchTree.Serach(8);
            System.out.println(node.val);
    
            binarySearchTree.insert(15);
            binarySearchTree.inOrder(binarySearchTree.root);
    
            System.out.println();
            binarySearchTree.remove(9);
            binarySearchTree.inOrder(binarySearchTree.root);
    
        }

运行结果：

![74d3413e640b4dc78ba06a6112bb2c03.png][]

[0741d2a1f38e4477a5e5fd406b950c32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ad9eb290ee2e43d7a10a89d8ffa76ddf.png
[74d3413e640b4dc78ba06a6112bb2c03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d55176a00a2b41908b72f3fd72102987.png