# 二分搜索树

二叉查找树(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. 如果选取的节点的左节点不为空,就找该左节点最右的节点。对于节点 1 来说,他有左节点 2 ,那么节点 2 的最右节点就是 5
  2. 如果左节点为空,且目标节点是父节点的右节点,那么前驱节点为父节点。对于节点 5 来说,没有左节点,且是节点 2 的右节点,所以节点 2 是前驱节点
  3. 如果左节点为空,且目标节点是父节点的左节点,向上寻找到第一个是父节点的右节点的节点。对于节点 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. 如果有右节点,就找到该右节点的最左节点。对于节点 1 来说,他有右节点 3 ,那么节点 3 的最左节点就是 6
  2. 如果没有右节点,就向上遍历直到找到一个节点是父节点的左节点。对于节点 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);
}