介绍

二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透过建构一棵二叉查找树变成一个有序序列，建构树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望O(log n)，最坏O(n)（数列有序，树退化成线性表)。

（以上内容摘自wikipedia）

简而言之，就是左边的节点一定比根节点小，右边的节点一定比根节点大，如下图：

相关操作

插入

插入过程比较简单，一路递归下去，当新节点小于该节点，往左边插入，否则往右边插入

func insertNode(node *TreeNode, newNode *TreeNode) {
    //当新节点小于该节点，左边插入，否则右边插入
    if newNode.Value < node.Value {
        if node.Left != nil {
            insertNode(node.Left, newNode)
        } else {
            node.Left = newNode
        }
    } else {
        if node.Right != nil {
            insertNode(node.Right, newNode)
        } else {
            node.Right = newNode
        }
    }
}

查找

查找过程也比较简单，与节点进行比对，小的往左走大的往右走知道找到该节点或找不到该节点

func findNode(v int, node *TreeNode) *TreeNode {
    for {
        if node == nil {
            return node
        }
        if node.Value == v {
            return node
        } else {
            if node.Value > v {
                node = node.Left
            } else {
                node = node.Right
            }
        }
    }
}

最值

这个就更简单了，最小值往左边遍历，最大值往右边遍历，到头就是了

// Max 最大值
func (b *BinarySearchTree) Max() int {
    node := b.Root
    for {
        if node.Right != nil {
            node = node.Right
        } else {
            return node.Value
        }
    }
}

// Min 最小值
func (b *BinarySearchTree) Min() int {
    node := b.Root
    for {
        if node.Left != nil {
            node = node.Left
        } else {
            return node.Value
        }
    }
}

删除

BST里面最复杂的应该就是删除操作了，通过观察BST，我们能够发现，需要删除的节点存在四种情况：

  1. 没有子节点
  2. 只有左节点
  3. 只有右节点
  4. 左右节点都有

对此，我们需要分别处理

对于情况1，只需要删除该节点即可：

对于情况2，删除该节点，并将该节点提升至左节点

对于情况3，删除该节点，并将该节点提升至右节点

情况4需要做特殊说明：

如上所示，假如我们需要删除3号节点，满足情况4，需要先将该节点删除

删除后可存在两种操作，均可以使该树满足BST条件：

  • 找到左子树的最大节点，并将该节点提升到节点3的位置
  • 找到右子树的最小节点，并将该节点提升到节点3的位置

以上操作后，根据BST的性质，必然不会破坏该树的结构，不信的可以自行证明

//删除节点
func deleteNode(node *TreeNode, v int) *TreeNode {
    if node == nil {
        return node
    }
    if node.Value > v {
        node.Left = deleteNode(node.Left, v)
        return node
    }
    if node.Value < v {
        node.Right = deleteNode(node.Right, v)
        return node
    }
    //情况1：没有子节点
    if node.Left == nil && node.Right == nil {
        node = nil
        return node
    }
    //情况2：右子节点为空，即只有左子节点，提升左子节点
    if node.Right == nil {
        node = node.Left
        return node
    }
    //情况3：左子节点为空，即只有右子节点，提升右子节点
    if node.Left == nil {
        node = node.Right
        return node
    }
    //情况4：左右节点都部位空，将该节点与左子树最大或者右子树最小节点进行替换，替换后删除节点
    if node.Right != nil && node.Left != nil {
        maxVal := findMaxInLeft(node.Left)
        node.Value = maxVal
        node.Left = deleteNode(node.Left, maxVal)
        return node
    }
    return node
}

//查找左节点最大值
func findMaxInLeft(leftNode *TreeNode) int {
    for {
        if leftNode.Right != nil {
            leftNode = leftNode.Right
        } else {
            return leftNode.Value
        }
    }
}

Golang实现

bst.go

package bst

import "fmt"

type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

type BinarySearchTree struct {
    Root *TreeNode
}

// Insert 插入
func (b *BinarySearchTree) Insert(v int) {
    if b.Root == nil {
        b.Root = &TreeNode{Value: v}
        return
    }
    insertNode(b.Root, &TreeNode{Value: v})
}

// Remove 删除
func (b *BinarySearchTree) Remove(v int) {
    deleteNode(b.Root, v)
}

// Search 查找
func (b *BinarySearchTree) Search(v int) bool {
    node := findNode(v, b.Root)
    if node == nil {
        return false
    } else {
        return true
    }
}

// Max 最大值
func (b *BinarySearchTree) Max() int {
    node := b.Root
    for {
        if node.Right != nil {
            node = node.Right
        } else {
            return node.Value
        }
    }
}

// Min 最小值
func (b *BinarySearchTree) Min() int {
    node := b.Root
    for {
        if node.Left != nil {
            node = node.Left
        } else {
            return node.Value
        }
    }
}

// PreOrderTraverse 前序遍历
func (b *BinarySearchTree) PreOrderTraverse() {
    preorder(b.Root)
    fmt.Println()
}

// InOrderTraverse 中序遍历
func (b *BinarySearchTree) InOrderTraverse() {
    inorder(b.Root)
    fmt.Println()
}

// PostOrderTraverse 后序遍历
func (b *BinarySearchTree) PostOrderTraverse() {
    postorder(b.Root)
    fmt.Println()
}

//插入节点
func insertNode(node *TreeNode, newNode *TreeNode) {
    //当新节点小于该节点，左边插入，否则右边插入
    if newNode.Value < node.Value {
        if node.Left != nil {
            insertNode(node.Left, newNode)
        } else {
            node.Left = newNode
        }
    } else {
        if node.Right != nil {
            insertNode(node.Right, newNode)
        } else {
            node.Right = newNode
        }
    }
}

//删除节点
func deleteNode(node *TreeNode, v int) *TreeNode {
    if node == nil {
        return node
    }
    if node.Value > v {
        node.Left = deleteNode(node.Left, v)
        return node
    }
    if node.Value < v {
        node.Right = deleteNode(node.Right, v)
        return node
    }
    //情况1：没有子节点
    if node.Left == nil && node.Right == nil {
        node = nil
        return node
    }
    //情况2：右子节点为空，即只有左子节点，提升左子节点
    if node.Right == nil {
        node = node.Left
        return node
    }
    //情况3：左子节点为空，即只有右子节点，提升右子节点
    if node.Left == nil {
        node = node.Right
        return node
    }
    //情况4：左右节点都部位空，将该节点与左子树最大或者右子树最小节点进行替换，替换后删除节点
    if node.Right != nil && node.Left != nil {
        maxVal := findMaxInLeft(node.Left)
        node.Value = maxVal
        node.Left = deleteNode(node.Left, maxVal)
        return node
    }
    return node
}

//查找左节点最大值
func findMaxInLeft(leftNode *TreeNode) int {
    for {
        if leftNode.Right != nil {
            leftNode = leftNode.Right
        } else {
            return leftNode.Value
        }
    }
}

//查找节点
func findNode(v int, node *TreeNode) *TreeNode {
    for {
        if node == nil {
            return node
        }
        if node.Value == v {
            return node
        } else {
            if node.Value > v {
                node = node.Left
            } else {
                node = node.Right
            }
        }
    }
}

//前序遍历
func preorder(node *TreeNode) {
    if node == nil {
        return
    }
    fmt.Print(node.Value)
    fmt.Print(" ")
    preorder(node.Left)
    preorder(node.Right)
}

//中序遍历
func inorder(node *TreeNode) {
    if node == nil {
        return
    }
    inorder(node.Left)
    fmt.Print(node.Value)
    fmt.Print(" ")
    inorder(node.Right)
}

//后序遍历
func postorder(node *TreeNode) {
    if node == nil {
        return
    }
    postorder(node.Left)
    postorder(node.Right)
    fmt.Print(node.Value)
    fmt.Print(" ")
}

bst_test.go （测试代码）

package bst

import (
    "fmt"
    "testing"
)

func Test_BinarySearchTree(t *testing.T) {
    bst := new(BinarySearchTree)
    bst.Insert(8)
    bst.Insert(3)
    bst.Insert(10)
    bst.Insert(1)
    bst.Insert(6)
    bst.Insert(14)
    bst.Insert(4)
    bst.Insert(7)
    bst.Insert(13)
    fmt.Println("search 7:", bst.Search(7))
    fmt.Println("search 11", bst.Search(11))
    fmt.Println("PreOrder Traverse:")
    bst.PreOrderTraverse()
    fmt.Println("InOrder Traverse:")
    bst.InOrderTraverse()
    fmt.Println("PostOrder Traverse:")
    bst.PostOrderTraverse()
    fmt.Println("before remove:")
    bst.InOrderTraverse()
    bst.Remove(3)
    fmt.Println("before remove 3:")
    bst.InOrderTraverse()
}

Leetcode 450. 删除二叉搜索树中的节点

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

题解

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return root
    }
    if root.Val > key {
        root.Left = deleteNode(root.Left, key)
        return root
    }
    if root.Val < key {
        root.Right = deleteNode(root.Right, key)
        return root
    }
    if root.Left == nil && root.Right == nil {
        root = nil
        return root
    }
    if root.Left == nil {
        root = root.Right
        return root
    }
    if root.Right == nil {
        root = root.Left
        return root
    }
    if root.Right != nil && root.Left != nil {
        maxVal := findMaxInLeft(root.Left)
        root.Val = maxVal
        root.Left = deleteNode(root.Left, maxVal)
        return root
    }
    return root
}

func findMaxInLeft(leftNode *TreeNode) int {
    for {
        if leftNode.Right != nil {
            leftNode = leftNode.Right
        } else {
            return leftNode.Val
        }
    }
}

结果

执行用时：12 ms, 在所有 Go 提交中击败了85.25%的用户

内存消耗：6.9 MB, 在所有 Go 提交中击败了100.00%的用户

最后修改：2021 年 11 月 26 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏