二叉搜索树
3/1/2022 BST
# 二叉搜索树BST
# 定义特性
二叉搜索树（BST）是一种特殊的二叉树，它满足如下特性：
- 左子树的节点 均小于 根节点的值，右子树的节点 均大于 根节点的值
- BST的中序遍历结果是递增的有序数列
BST具有以下优点：
- BST查找、删除、增加的时间复杂度由于二分的存在，时间复杂度均为O(h)，在高度平衡的BST下时间复杂度均为O(lgn)，对于需要查找和删除或插入同时进行的操作，用BST更为合适
# 基本操作
BST的基本操作有三种：查找、插入、删除，其中较为复杂的为删除操作。
- 查找，根据BST的特性，可二分快速确定去左右子树查找
- 插入，方式有很多，一般用是整体操作变化最小的经典方式，即根据BST的特性，在合适的节点上插入新节点。
- 删除，删除的情况较为复杂，需要根据删除的节点分为三种情况：
- 为叶子节点时，直接删除
- 如果右子树存在，则寻找右子树中最小的节点（即删除节点的后继节点）替代该节点，然后再递归删除该节点
- 如果左子树存在，则寻找左子树中最大的节点（即删除节点的前驱节点）替代该节点，然后再递归删除该节点
# 代码示例
这里列出三种基本操作的JS代码供参考，这里优先使用递归法，因为递归法更容易理解，但是从代码性能上，迭代法性能会更优。
详细的迭代、递归解法，参考：
- 700.二叉搜索树中的搜索
- 701.二叉搜索树中的插入操作
- 450.删除二叉搜索树中的节点
# 查找
var searchBST = function (root, val) {
while (root) {
if (root.val == val) return root;
root = val < root.val ? root.left : root.right;
}
return null;Ï
};
# 插入
var insertIntoBST = function (root, val) {
if (!root) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
} else {
return null;
}
return root;
};
# 删除
var deleteNode = function (root, key) {
if (!root) return null;
// 寻找node在中序遍历的前驱节点，即左子树中最大的值
const predecessor = (node) => {
node = node.left;
while (node && node.right) {
node = node.right;
}
return node.val;
};
// 寻找node在中序遍历的后继节点，即右子树中最小的值
const successor = (node) => {
node = node.right;
while (node && node.left) {
node = node.left;
}
return node.val;
};
if (key < root.val) {
// 左子树中寻找需要删除的节点
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
// 右子树中寻找需要删除的节点
root.right = deleteNode(root.right, key);
} else {
if (!root.left && !root.right) {
// 叶子节点直接删除
// 分为两种情况，只有根节点 和 普通的叶子节点，但处理都是一样。如果是根节点返回null，如果是叶子节点，则由于递归，父节点会置位null
root = null;
} else if (root.right) {
// 如果右子树存在，则寻找右子树中最小的节点替代该节点，然后再递归删除该节点
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
} else {
// 如果右子树不存在，则寻找左子树中最大的节点替代该节点，然后再递归删除该节点
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
};
# 案例分析
这里重点讨论下220.存在重复元素-iii，这一题通过BST解法，能够综合的运用BST，且加深对BST这种数据结构的认识。
需要注意以下两点：
1. 220这一题的最优解法为桶排序，但是这里为了练习BST，重点从BST的角度去梳理。
1. 220这一题BST解法优先使用平衡二叉树，即使用红黑或者AVL树，优先使用红黑，这样能保证树操作的时间复杂度在O(lgn)，但是这里为了练习BST，所以不做延伸，仅用简单的BST来实现。
# 附录
# 树结构中的常见用语
- 节点的深度 - 从树的根节点到该节点的边数
- 节点的高度 - 该节点和叶子之间最长路径上的边数
- 树的高度 - 其根节点的高度
即，深度为从上往下，高度为从下往上。
# 平衡二叉搜索树
平衡二叉搜索树，是高度平衡的二叉搜索树，指每个节点的两个子树高度相差不会超过1。
当插入和删除时，平衡二叉搜索树，会自动调整高度，自动保持高度最小。
常用的平衡二叉搜索树：