二叉搜索树-构造解释

概念
- 树节点的左边，所有节点的值都比它小
- 树节点的右边，所有节点的值都比它大
树的节点类型-Node类
- 含有三个属性: key、left、right

插入

如果key偏小，就考虑插入左边
- 如果有左边，就递归插入左子树，否则新建赋予
如果key偏大，就考虑插入右边
- 如果有右边，就递归插入右子树，否则新建赋予
如果相等，代表已存在，返回

function insertNode(root, key) {
    if (key < root.key) {
        if (root.left) {
            insertNode(root.left, key);
        } else {
            root.left = new Node(key);
        }
    } else if (key > root.key) {
        if (root.right) {
            insertNode(root.right, key);
        } else {
            root.right = new Node(key);
        }
    } else {
        return;
    }
}

查找

如果key相等，代表找到了，返回true
如果key偏小，就考虑找左边
- 如果有左边，就递归找左子树，否则返回false
如果key偏大，就考虑找右边
- 如果有右边，就递归找右子树，否则返回false

function searchNode(root, key) {
    if (key === root.key) {
        return true;
    } else if (key < root.key) {
        if (root.left) {
            return searchNode(root.left, key);
        } else {
            return false;
        }
    } else {
        if (root.right) {
            return searchNode(root.right, key);
        } else {
            return false;
        }
    }
}

最值节点

最小的一般出现在左边
- 如果有左边，就递归找左子树，否则返回当前节点

function getMin(root) {
    if (root.left) {
        return getMin(root.left);
    } else {
        return root;
    }
}

最大的一般出现在右边
- 如果有右边，就递归找右子树，否则返回当前节点

function getMax(root) {
    if (root.right) {
        return getMax(root.right);
    } else {
        return root;
    }
}

删除

如果当前节点为空，代表没东西可删，返回null
如果key偏小，就考虑在左边删，让递归函数返回新的根赋予
如果key偏大，就考虑在右边删，让递归函数返回新的根赋予
如果相等
- 当左右都为空时，最简单，直接把当前节点置null
- 只有一边空时，直接把另一边节点提升为当前节点
- 都不空，就要从后代中找一个替罪羊补上
  - 这里选择从右子树中取最小的，直接赋予值
  - 同时记得对右子树递归，删掉这个替罪羊，让递归函数返回新的根赋予

function removeNode(root, key) {
    if (root === null) return null;
    if (key < root.key) {
        root.left = removeNode(root.left, key);
    } else if (key > root.key) {
        root.right = removeNode(root.right, key);
    } else {
        if (!root.left && !root.right) {
            root = null;
        } else if (!root.left) {
            root = root.right;
        } else if (!root.right) {
            root = root.left;
        } else {
            const minNode = getMin(root.right);
            root.key = minNode.key;
            root.right = removeNode(root.right, minNode.key);
        }

        return root;
    }
}

Keyboard shortcuts

二叉搜索树-构造解释