关于javascript:二叉树三-二叉查找树

什么是二叉查找树

二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）

他领有以下性质:

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

图中的二叉树就是一颗二叉查找树

const nodes = {
    value: 6,
    left: {
        value: 3,
        left: {
            value: 1,
            left: {value: 0},
            right: {value: 2}
        },
        right: {value: 5}
    },
    right: {
        value: 8,
        left: {value: 7},
        right: {value: 9}
    }
} 

查找节点

在二叉查找树 b 中查找 x 的过程为：

1. 若 b 是空树，则搜寻失败，否则：
2. 若 x 等于 b 的根节点的数据域之值，则查找胜利；否则：
3. 若 x 小于 b 的根节点的数据域之值，则搜寻左子树；否则：
4. 查找右子树。

const SearchBST = (tree, value) => {if (!tree) {return false}
    if (value === tree.value) {return tree}
    if (value < tree.value) {return SearchBST(tree.left, value)
    }
    return SearchBST(tree.right, value)
}

插入节点

向一个二叉查找树 b 中插入一个节点 s 的算法，过程为：

1. 若 b 是空树，则将 s 所指节点作为根节点插入，否则：
2. 若 s ->data 等于 b 的根节点的数据域之值，则返回，否则：
3. 若 s ->data 小于 b 的根节点的数据域之值，则把 s 所指节点插入到左子树中，否则：
4. 把 s 所指节点插入到右子树中。（新插入节点总是叶子节点）

const InsertBST = (tree, value, parent, key) => {if (!tree) {parent[key] = {value}
        return true
    }
    if (tree.value === value) {return false}
    if (tree.value > value) {return InsertBST(tree.left, value, tree, 'left')
    }
    return InsertBST(tree.right, value, tree, 'right')
}

相比拟其余算法, JS 的实现感觉有些有余

删除节点

二叉搜寻树的节点删除包含两个过程，查找和删除。

在二叉查找树删去一个结点，分三种状况探讨：

• 待删除节点度为零；
• 待删除节点度为一；
• 待删除节点度为二。

节点度能够看成分支数

const DeleteBST = (root, value) => {if (!root) {return false}
    if (root.value === value) {return DELETE(root)
    }
    if (root.value > value) {return DeleteBST(root.left, value, root, 'left')
    }
    return DeleteBST(root.right, value, root, 'left')
}

const DELETE = (root, parent, key) => {
    // 在这里实现三种状况
    // 状况 1 没有左右子节点 可间接删除
    if (!root.left && !root.right) {parent[key] = null
        return true
    }

    // 状况 2 只有一个子节点 从新连贯即可
    if (!root.right) {
        const q = root.left
        root.value = q.value
        root.left = q.left
        root.right = q.right
        return true
    }
    if (!root.left) {
        const p = root.right
        root.value = p.value
        root.left = p.left
        root.right = p.right
        return true
    }

    // 状况 3
    // 删除节点后，为了维持二叉搜寻树的构造个性，须要从其左子树中选出一个最大值的节点，“上移”到删除的节点地位上
    let temp = root
    let l = root.left
    while (l.right) {
        temp = l
        l = l.right
    }
    root.value = l.value
    if (root != temp) {temp.right = l.left} else {temp.left = l.left}
    return true
}

复杂度

尽管二叉查找树的最坏效率是 O(n)，但它反对动静查问，且有很多改进版的二叉查找树能够使树高为 O(log n)，从而将最坏效率降至 O(log n)，如 AVL 树、红黑树等。

结语

二叉查找树它既有链表的疾速插入与删除操作的特点，又有数组疾速查找的劣势, 利用非常宽泛，例如在文件系统和数据库系统个别会采纳这种数据结构进行高效率的排序与检索操作

仓库地址: https://github.com/Grewer/notes

参考:

• https://zh.wikipedia.org/wiki…
• https://www.jianshu.com/p/ff4…

相干系列

• 二叉树 (一): 遍历
• 二叉树 (二): 补充
• 二叉树 (三): 二叉查找树