Binary Search Tree

基础的二分搜索树

定义

操作定义

interface BST<K : Comparable<K>, V> : KVOperation<K, V> {

    /**
     * Retrieves the root node of the binary search tree (BST).
     *
     * @return the root node of the BST, or null if the tree is empty
     */
    fun getRoot(): BSTNode<K, V>?

    /**
     * Determines whether the binary search tree (BST) contains the specified key.
     *
     * @param key the key to search for in the binary search tree
     * @return true if the key exists in the tree, false otherwise
     */
    override fun contains(key: K): Boolean {
        return getNode(key) != null
    }

    /**
     * Retrieves the value associated with the specified key in the binary search tree (BST).
     */
    override fun get(key: K): V? {
        return getNode(key)?.getValue()
    }

    /**
     * Retrieves the node associated with the specified key in the binary search tree (BST).
     *
     * @param key the key to search for in the binary search tree
     * @return the node corresponding to the given key, or null if the key is not found
     */
    fun getNode(key: K): BSTNode<K, V>? {
        return getNode(getRoot(), key)
    }

    /**
     * Determines whether the binary search tree (BST) satisfies the properties of a valid BST.
     *
     * @return true if the tree is a valid binary search tree, false otherwise
     */
    fun isBst(): Boolean {
        return isBST(node = getRoot())
    }

    /**
     * Retrieves the minimum node in the binary search tree (BST).
     *
     * @return the node containing the smallest key in the tree, or null if the tree is empty
     */
    fun getMin(): BSTNode<K, V>? {
        return getMin(getRoot())
    }

    /**
     * Retrieves the maximum node in the binary search tree (BST).
     *
     * @return the node containing the largest key in the tree, or null if the tree is empty
     */
    fun getMax(): BSTNode<K, V>? {
        return getMax(getRoot())
    }

    fun preorder(action: (BSTNode<K, V>) -> Unit) {
        getRoot()?.preorder(action)
    }

    fun inorder(action: (BSTNode<K, V>) -> Unit) {
        getRoot()?.inorder(action)
    }

    fun postorder(action: (BSTNode<K, V>) -> Unit) {
        getRoot()?.postorder(action)
    }

    fun bfs(action: (BSTNode<K, V>) -> Unit) {
        getRoot()?.bfs(action)
    }

    fun <K : Comparable<K>, V> BSTNode<K, V>.preorder(action: (BSTNode<K, V>) -> Unit) {
        action.apply { this }

        getLeft()?.preorder(action)
        getRight()?.preorder(action)
    }

    fun <K : Comparable<K>, V> BSTNode<K, V>.inorder(action: (BSTNode<K, V>) -> Unit) {
        getLeft()?.inorder(action)
        action.apply { this }
        getRight()?.inorder(action)
    }

    fun <K : Comparable<K>, V> BSTNode<K, V>.postorder(action: (BSTNode<K, V>) -> Unit) {
        getLeft()?.postorder(action)
        getRight()?.postorder(action)
        action.apply { this }
    }

    fun <K : Comparable<K>, V> BSTNode<K, V>.bfs(action: (BSTNode<K, V>) -> Unit) {
        val queue = ArrayDeque<BSTNode<K, V>>()
        queue.add(this)

        while (queue.isNotEmpty()) {
            val current = queue.removeFirst()
            action(current)

            current.getLeft()?.let { queue.addLast(it) }
            current.getRight()?.let { queue.addLast(it) }
        }
    }

}

节点定义

interface BSTNode<K : Comparable<K>, V> {

    /**
     * 节点高度，定义为节点到根节点的高度
     */
    fun getHeight(): Int

    fun setHeight(height: Int): BSTNode<K, V>

    fun getKey(): K

    fun setKey(key: K): BSTNode<K, V>

    fun getValue(): V

    fun setValue(value: V): BSTNode<K, V>

    fun getLeft(): BSTNode<K, V>?

    fun setLeft(left: BSTNode<K, V>?): BSTNode<K, V>

    fun getRight(): BSTNode<K, V>?

    fun setRight(right: BSTNode<K, V>?): BSTNode<K, V>

    fun isLeaf(): Boolean {
        return this.getLeft() == null && this.getRight() == null
    }
}

实现

class BasicBST<K : Comparable<K>, V> : BST<K, V> {
    private var root: BSTNode<K, V>? = null
    private var count = 0

    override fun size(): Int = this.count

    override fun getRoot(): BSTNode<K, V>? = this.root

    /**
     * Adds a key-value pair to the binary search tree (BST). If the key already exists,
     * updates the value associated with the key.
     *
     * @param key the key to insert or update in the BST
     * @param value the value to associate with the specified key
     */
    override fun insert(key: K, value: V) {
        root = add(root, key, value)
    }

    private fun add(node: BSTNode<K, V>?, k: K, v: V): BSTNode<K, V> {
        if (node == null) {
            count++
            return BasicBSTNode(k, v)
        }

        when {
            k < node.getKey() -> node.setLeft(add(node.getLeft(), k, v))

            k > node.getKey() -> node.setRight(add(node.getRight(), k, v))

            else -> {
                node.setValue(v)
            }
        }
        return node.updateHeight()
    }

    override fun remove(k: K): V? {
        return getNode(k)?.let { node ->
            val rtV = node.getValue()
            root = remove(root, k)
            rtV
        }
    }

    private fun remove(node: BSTNode<K, V>?, k: K): BSTNode<K, V>? {
        if (node == null) {
            return null
        }
        when {
            k < node.getKey() -> {
                node.setLeft(remove(node.getLeft(), k))
            }

            k > node.getKey() -> {
                node.setRight(remove(node.getRight(), k))
            }

            else -> {
                // Node to be removed found
                if (node.getLeft() == null && node.getRight() == null) {
                    // 左右子节点都为空
                    this.count--
                    return null
                }
                // 剩余三种情况  左不空+右不空 左不空+右空  左空+右不空
                node.getLeft()?.let { leftChild ->
                    // 左不空+右不空 左不空+右空
                    getMax(leftChild)!!.let { leftMax ->
                        node.setKey(leftMax.getKey())
                            .setValue(leftMax.getValue())
                            .setLeft(remove(leftChild, leftMax.getKey()))
                    }
                } ?: run {
                    // 左空+右不空：选择右子树最小值作为替换节点
                    getMin(node.getRight())!!.let { rightMin ->
                        node.setKey(rightMin.getKey())
                            .setValue(rightMin.getValue())
                            .setRight(remove(node.getRight(), rightMin.getKey()))
                    }
                }
            }
        }
        return node.updateHeight()
    }

    override fun clear() {
        this.root = null
        this.count = 0
    }
}

internal class BasicBSTNode<K : Comparable<K>, V> : BSTNode<K, V> {
    private var height: Int
    private var key: K
    private var value: V
    private var left: BSTNode<K, V>?
    private var right: BSTNode<K, V>?

    internal constructor(key: K, value: V) {
        this.key = key
        this.value = value
        this.height = DEFAULT_HEIGHT
        this.left = null
        this.right = null
    }

    override fun getHeight(): Int = height

    override fun setHeight(height: Int): BSTNode<K, V> {
        this.height = height
        return this
    }

    override fun getKey(): K = this.key

    override fun setKey(key: K): BSTNode<K, V> = this.apply {
        this.key = key
    }

    override fun getValue(): V = this.value

    override fun setValue(value: V): BSTNode<K, V> = this.apply {
        this.value = value
    }

    override fun getLeft(): BSTNode<K, V>? = this.left

    override fun setLeft(left: BSTNode<K, V>?): BSTNode<K, V> = this.apply {
        this.left = left
    }

    override fun getRight(): BSTNode<K, V>? = this.right

    override fun setRight(right: BSTNode<K, V>?): BSTNode<K, V> = this.apply {
        this.right = right
    }

    override fun toString(): String {
        return "BSTNode(key=$key, value=$value)"
    }

}

问题

普通的二分搜索树在极端情况下会退化成链表