# 二分搜索树
二叉查找树(BST)：根节点大于等于左子树所有节点，小于等于右子树所有节点。二叉查找树中序遍历有序。
二分查找的时间复杂度是 O(log(n))，最坏情况下的时间复杂度是 O(n)(相当于顺序查找)
# 实现
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
this.size = 0;
}
getSize() {
return this.size;
}
isEmpty() {
return this.size === 0;
}
addNode(v) {
this.root = this._addChild(this.root, v);
}
// 添加节点时，需要比较添加的节点值和当前
// 节点值的大小
_addChild(node, v) {
if (!node) {
this.size++;
return new Node(v);
}
if (node.value > v) {
node.left = this._addChild(node.left, v);
} else if (node.value < v) {
node.right = this._addChild(node.right, v);
}
return node;
}
}
以上是最基本的二分搜索树实现，接下来实现树的遍历。
接下来讲解的是二分搜索树中最难实现的部分：删除节点。因为对于删除节点来说，会存在以下几种情况
- 需要删除的节点没有子树
- 需要删除的节点只有一条子树
- 需要删除的节点有左右两条树
对于前两种情况很好解决，但是第三种情况就有难度了，所以先来实现相对简单的操作：删除最小节点，对于删除最小节点来说，是不存在第三种情况的，删除最大节点操作是和删除最小节点相反的，所以这里也就不再赘述。
deleteMin() {
this.root = this._deleteMin(this.root)
console.log(this.root)
}
_deleteMin(node) {
// 一直递归左子树
// 如果左子树为空，就判断节点是否拥有右子树
// 有右子树的话就把需要删除的节点替换为右子树
if ((node != null) & !node.left) return node.right
node.left = this._deleteMin(node.left)
// 最后需要重新维护下节点的 `size`
node.size = this._getSize(node.left) + this._getSize(node.right) + 1
return node
}
最后讲解的就是如何删除任意节点了。对于这个操作，T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。
当遇到这种情况时，需要取出当前节点的后继节点(也就是当前节点右子树的最小节点)来替换需要删除的节点。然后将需要删除节点的左子树赋值给后继结点，右子树删除后继结点后赋值给他。
你如果对于这个解决办法有疑问的话，可以这样考虑。因为二分搜索树的特性，父节点一定比所有左子节点大，比所有右子节点小。那么当需要删除父节点时，势必需要拿出一个比父节点大的节点来替换父节点。这个节点肯定不存在于左子树，必然存在于右子树。然后又需要保持父节点都是比右子节点小的，那么就可以取出右子树中最小的那个节点来替换父节点。
delete(v) {
this.root = this._delete(this.root, v)
}
_delete(node, v) {
if (!node) return null
// 寻找的节点比当前节点小，去左子树找
if (node.value < v) {
node.right = this._delete(node.right, v)
} else if (node.value > v) {
// 寻找的节点比当前节点大，去右子树找
node.left = this._delete(node.left, v)
} else {
// 进入这个条件说明已经找到节点
// 先判断节点是否拥有拥有左右子树中的一个
// 是的话，将子树返回出去，这里和 `_deleteMin` 的操作一样
if (!node.left) return node.right
if (!node.right) return node.left
// 进入这里，代表节点拥有左右子树
// 先取出当前节点的后继结点，也就是取当前节点右子树的最小值
let min = this._getMin(node.right)
// 取出最小值后，删除最小值
// 然后把删除节点后的子树赋值给最小值节点
min.right = this._deleteMin(node.right)
// 左子树不动
min.left = node.left
node = min
}
// 维护 size
node.size = this._getSize(node.left) + this._getSize(node.right) + 1
return node
}
# 中序遍历的前驱后继节点
实现这个算法的前提是节点有一个 parent 的指针指向父节点，根节点指向 null 。
如图所示，该树的中序遍历结果是 4, 2, 5, 1, 6, 3, 7
# 前驱节点
对于节点 2 来说，他的前驱节点就是 4 ，按照中序遍历原则，可以得出以下结论
- 如果选取的节点的左节点不为空，就找该左节点最右的节点。对于节点
1来说，他有左节点2，那么节点2的最右节点就是5 - 如果左节点为空，且目标节点是父节点的右节点，那么前驱节点为父节点。对于节点
5来说，没有左节点，且是节点2的右节点，所以节点2是前驱节点 - 如果左节点为空，且目标节点是父节点的左节点，向上寻找到第一个是父节点的右节点的节点。对于节点
6来说，没有左节点，且是节点3的左节点，所以向上寻找到节点1，发现节点3是节点1的右节点，所以节点1是节点6的前驱节点
以下是算法实现
function predecessor(node) {
if (!node) return;
// 结论 1
if (node.left) {
return getRight(node.left);
} else {
let parent = node.parent;
// 结论 2 3 的判断
while (parent && parent.right === node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
function getRight(node) {
if (!node) return;
node = node.right;
while (node) node = node.right;
return node;
}
# 后继节点
对于节点 2 来说，他的后继节点就是 5 ，按照中序遍历原则，可以得出以下结论
- 如果有右节点，就找到该右节点的最左节点。对于节点
1来说，他有右节点3，那么节点3的最左节点就是6 - 如果没有右节点，就向上遍历直到找到一个节点是父节点的左节点。对于节点
5来说，没有右节点，就向上寻找到节点2，该节点是父节点1的左节点，所以节点1是后继节点
以下是算法实现
function successor(node) {
if (!node) return;
// 结论 1
if (node.right) {
return getLeft(node.right);
} else {
// 结论 2
let parent = node.parent;
// 判断 parent 为空
while (parent && parent.left === node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
function getLeft(node) {
if (!node) return;
node = node.left;
while (node) node = node.left;
return node;
}
# AVL 树
# 概念
二分搜索树实际在业务中是受到限制的，因为并不是严格的 O(logN)，在极端情况下会退化成链表，比如加入一组升序的数字就会造成这种情况。
AVL 树改进了二分搜索树，在 AVL 树中任意节点的左右子树的高度差都不大于 1，这样保证了时间复杂度是严格的 O(logN)。基于此，对 AVL 树增加或删除节点时可能需要旋转树来达到高度的平衡。
# 实现
因为 AVL 树是改进了二分搜索树，所以部分代码是于二分搜索树重复的，对于重复内容不作再次解析。
对于 AVL 树来说，添加节点会有四种情况
对于左左情况来说，新增加的节点位于节点 2 的左侧，这时树已经不平衡，需要旋转。因为搜索树的特性，节点比左节点大，比右节点小，所以旋转以后也要实现这个特性。
旋转之前：new < 2 < C < 3 < B < 5 < A，右旋之后节点 3 为根节点，这时候需要将节点 3 的右节点加到节点 5 的左边，最后还需要更新节点的高度。
对于右右情况来说，相反于左左情况，所以不再赘述。
对于左右情况来说，新增加的节点位于节点 4 的右侧。对于这种情况，需要通过两次旋转来达到目的。
首先对节点的左节点左旋，这时树满足左左的情况，再对节点进行一次右旋就可以达到目的。
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVL {
constructor() {
this.root = null;
}
addNode(v) {
this.root = this._addChild(this.root, v);
}
_addChild(node, v) {
if (!node) {
return new Node(v);
}
if (node.value > v) {
node.left = this._addChild(node.left, v);
} else if (node.value < v) {
node.right = this._addChild(node.right, v);
} else {
node.value = v;
}
node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
let factor = this._getBalanceFactor(node);
// 当需要右旋时，根节点的左树一定比右树高度高
if (factor > 1 && this._getBalanceFactor(node.left) >= 0) {
return this._rightRotate(node);
}
// 当需要左旋时，根节点的左树一定比右树高度矮
if (factor < -1 && this._getBalanceFactor(node.right) <= 0) {
return this._leftRotate(node);
}
// 左右情况
// 节点的左树比右树高，且节点的左树的右树比节点的左树的左树高
if (factor > 1 && this._getBalanceFactor(node.left) < 0) {
node.left = this._leftRotate(node.left);
return this._rightRotate(node);
}
// 右左情况
// 节点的左树比右树矮，且节点的右树的右树比节点的右树的左树矮
if (factor < -1 && this._getBalanceFactor(node.right) > 0) {
node.right = this._rightRotate(node.right);
return this._leftRotate(node);
}
return node;
}
_getHeight(node) {
if (!node) return 0;
return node.height;
}
_getBalanceFactor(node) {
return this._getHeight(node.left) - this._getHeight(node.right);
}
// 节点右旋
// 5 2
// / \ / \
// 2 6 ==> 1 5
// / \ / / \
// 1 3 new 3 6
// /
// new
_rightRotate(node) {
// 旋转后新根节点
let newRoot = node.left;
// 需要移动的节点
let moveNode = newRoot.right;
// 节点 2 的右节点改为节点 5
newRoot.right = node;
// 节点 5 左节点改为节点 3
node.left = moveNode;
// 更新树的高度
node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
newRoot.height = 1 + Math.max(this._getHeight(newRoot.left), this._getHeight(newRoot.right));
return newRoot;
}
// 节点左旋
// 4 6
// / \ / \
// 2 6 ==> 4 7
// / \ / \ \
// 5 7 2 5 new
// \
// new
_leftRotate(node) {
// 旋转后新根节点
let newRoot = node.right;
// 需要移动的节点
let moveNode = newRoot.left;
// 节点 6 的左节点改为节点 4
newRoot.left = node;
// 节点 4 右节点改为节点 5
node.right = moveNode;
// 更新树的高度
node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
newRoot.height = 1 + Math.max(this._getHeight(newRoot.left), this._getHeight(newRoot.right));
return newRoot;
}
}
# BST
# 1. 修剪二叉查找树
669. Trim a Binary Search Tree (Easy) (opens new window)
Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 Output: 3 / 2 / 1
题目描述：只保留值在 L ~ R 之间的节点
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
# 2. 寻找二叉查找树的第 k 个元素
230. Kth Smallest Element in a BST (Medium) (opens new window)
# 3. 把二叉查找树每个节点的值都加上比它大的节点的值
Convert BST to Greater Tree (Easy) (opens new window)
Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13
先遍历右子树。
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
traver(root);
return root;
}
private void traver(TreeNode node) {
if (node == null) return;
traver(node.right);
sum += node.val;
node.val = sum;
traver(node.left);
}
# 4. 二叉查找树的最近公共祖先
235. Lowest Common Ancestor of a Binary Search Tree (Easy) (opens new window)
# 5. 二叉树的最近公共祖先
236. Lowest Common Ancestor of a Binary Tree (Medium) (opens new window)
# 6. 从有序数组中构造二叉查找树
108. Convert Sorted Array to Binary Search Tree (Easy) (opens new window)
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length - 1);
}
private TreeNode toBST(int[] nums, int sIdx, int eIdx){
if (sIdx > eIdx) return null;
int mIdx = (sIdx + eIdx) / 2;
TreeNode root = new TreeNode(nums[mIdx]);
root.left = toBST(nums, sIdx, mIdx - 1);
root.right = toBST(nums, mIdx + 1, eIdx);
return root;
}
/*
* @lc app=leetcode id=108 lang=javascript
*
* [108] Convert Sorted Array to Binary Search Tree
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
// 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树
// 然后运用“树的递归性质”递归完成操作即可。
if (nums.length === 0) return null;
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
// 扩展： 这道题启示我们如果是一个非排序的数组，我们可以先进行排序然后再按上述思路进行。
};
# 7. 根据有序链表构造平衡的二叉查找树
109. Convert Sorted List to Binary Search Tree (Medium) (opens new window)
Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the
following height balanced BST: 0 / \ -3 9 / / -10 5
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
if (head.next == null) return new TreeNode(head.val);
ListNode preMid = preMid(head);
ListNode mid = preMid.next;
preMid.next = null; // 断开链表
TreeNode t = new TreeNode(mid.val);
t.left = sortedListToBST(head);
t.right = sortedListToBST(mid.next);
return t;
}
private ListNode preMid(ListNode head) {
ListNode slow = head, fast = head.next;
ListNode pre = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
return pre;
}
# 8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值
653. Two Sum IV - Input is a BST (Easy) (opens new window)
Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True
使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。
应该注意到，这一题不能用分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中。
public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
int i = 0, j = nums.size() - 1;
while (i < j) {
int sum = nums.get(i) + nums.get(j);
if (sum == k) return true;
if (sum < k) i++;
else j--;
}
return false;
}
private void inOrder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inOrder(root.left, nums);
nums.add(root.val);
inOrder(root.right, nums);
}
# 9. 在二叉查找树中查找两个节点之差的最小绝对值
530. Minimum Absolute Difference in BST (Easy) (opens new window)
Input: 1 \ 3 / 2 Output: 1
利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值。
private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return minDiff;
}
private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
preNode = node;
inOrder(node.right);
}
# 10. 寻找二叉查找树中出现次数最多的值
501. Find Mode in Binary Search Tree (Easy) (opens new window)
1 \ 2 / 2 return [2].
答案可能不止一个，也就是有多个值出现的次数一样多。
private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;
public int[] findMode(TreeNode root) {
List<Integer> maxCntNums = new ArrayList<>();
inOrder(root, maxCntNums);
int[] ret = new int[maxCntNums.size()];
int idx = 0;
for (int num : maxCntNums) {
ret[idx++] = num;
}
return ret;
}
private void inOrder(TreeNode node, List<Integer> nums) {
if (node == null) return;
inOrder(node.left, nums);
if (preNode != null) {
if (preNode.val == node.val) curCnt++;
else curCnt = 1;
}
if (curCnt > maxCnt) {
maxCnt = curCnt;
nums.clear();
nums.add(node.val);
} else if (curCnt == maxCnt) {
nums.add(node.val);
}
preNode = node;
inOrder(node.right, nums);
}