二叉搜索树的增删改查

太过爱你忘了你带给我的痛 2023-02-20 06:36 4阅读 0赞

### 目录 ###

*   *   *  1. 什么是二叉搜索树？
         *  2. 查找结点
         *  3. 插入结点
         *  4. 删除结点

### 1. 什么是二叉搜索树？ ###

二叉搜索树（Binary Search Tree）简称 BST，是一种特殊形式的二叉树。

二叉搜索树的的结构有两种可能：

*  一棵空树
 *  一棵由根节点、左右子树组成的树，同时，左右子树满足二叉搜索树的要求，且左子树的值小于等于根节点的值，右子树的值大于等于根节点的值。

对于二叉搜索树，需要掌握基本的操作：

*  查找某一特定值
 *  删除指定结点
 *  插入新结点

### 2. 查找结点 ###

当要查找目标值的节点时，我们可以根据二叉树的结点数据值的有序性（**左孩子 <= 根结点 <= 右孩子** ），根据以下思路进行查找：

*  遍历二叉树，如果当前遍历的节点为空，则以为着没有目标结点，直接返回
 *  若当前遍历的结点的值正好和目标值相等，则查找成功，返回
 *  若当前遍历的结点的值大于目标值，则应该在该结点的左子树进行查找，设置下一步遍历范围为`root.left`，继续递归遍历
 *  若当前遍历的结点的值小于目标值，则应该在该结点的右子树进行查找，设置下一步遍历范围为`root.right`，继续递归遍历

简单实现：

// 返回以目标值结点为根结点的二叉树
    function search(root, val) { 
        if(!root) { 
            return 
        }
        if(root.val === val) { 
            return root
        } else if(root.val > val) { 
            return search(root.left, val)
        } else { 
            return search(root.right, val)
        }
    }

### 3. 插入结点 ###

插入节点的操作和搜索结点类似，从根节点开始查找，把需要插入的值与当前遍历到的值作比较，若大于当前结点的值，就从其右子树继续遍历，若小于当前结点的值，就从其左子树继续遍历，直到直到合适的空位。

简单实现：

function insert(root, val) { 
        if(!root){ 
            return  new TreeNode(val)
        }
        if(val < root.val){ 
            root.left = insertIntoBST(root.left,val)
        }else{ 
            root.right = insertIntoBST(root.right,val)
        }
        return root
    };

### 4. 删除结点 ###

删除结点时，我们要考虑以下情况：

*  若二叉树为空树，直接返回
 *  若需要删除的目标节点没有左右孩子，那么直接删掉即可
 *  若需要删除的目标节点只存在左子树，那么就去左子树中小于目标结点的最大值，用这个节点覆盖掉目标结点
 *  若需要删除的目标节点只存在右子树，那么就去左子树中大于目标结点的最小值，用这个节点覆盖掉目标结点
 *  若需要删除的目标节点既有左子树，又有右子树，那么可以取左子树的最大值结点，也可以取右子树的最小值结点去覆盖目标结点。

简单实现：

function delete(root, n) { 
        // 如果没找到目标结点，直接返回
        if(!root) { 
            return 
        }
    
        if(root.val === n) { 
    
            if(!root.left && !root.right) { 
                root = null
            } else if(root.left) { 
                // 寻找左子树里值最大的结点
                const maxLeft = findMax(root.left)
                // 用 maxLeft 覆盖掉需要删除的当前结点 
                root.val = maxLeft.val
                // 递归
                delete(root.left, maxLeft.val)
            } else { 
                // 寻找右子树里值最小的结点
                const minRight = findMin(root.right)
                // 用 minRight 覆盖掉需要删除的当前结点 
                root.val = minRight.val
                // 递归
                delete(root.right, minRight.val)
            }
        } else if(root.val > n) { 
            delete(root.left, n)
        } else  { 
            delete(root.right, n)
        }
    }
    
    // 寻找左子树最大值
    function findMax(root) { 
        while(root.right) { 
            root = root.right
        }
    }
    
    // 寻找右子树的最小值
    function findMin(root) { 
        while(root.left) { 
            root = root.left
        }
    }