BST Operations

思路

BST这个数据结构本质上就是一个支持动态增删查改的sorted array，所以我们在sorted array上常用的算法在BST上也同样适用，which is binary search。基本上每道BST的问题都会或多或少用到binary search的思想，如果要想traverse down the tree。

除此之外，BST常见的操作还可以分成七大ordered operation，也就是跟排序／找顺序有关。以及五大增删查改操作。

题型

7大ordered operation

• find Min:核心思路就是一路向左走。
• find Max:核心思路就是一路向右走。
• find Ceiling (inorder succesor)。核心思路就是keep 一个prev pointer，只有在往某一个方向拐弯的时候才会更新prev pointer
• find Floor (inorder predecesor)。核心思路就是keep 一个prev pointer，只有在往某一个方向拐弯的时候才会更新prev pointer
• select。核心是和左子树的size做比较，从而得出应该往哪个方向走。
• rank 。核心也是计算出来左子树的size，用以compute最终的rank
• find range。核心是一个带边界check的inorder traversal，如果超过upper bound或者低于lower bound我们就不去遍历了。

5大增删查改

• insert: 核心是keep 一个prev pointer用以最后做插入用
• delete min：核心是一路向左，但是也要keep 一个prev pointer，用以把min的右子树嫁接到prev的左子树。
• delete max：核心是一路向右，但是也要keep 一个prev pointer，用以把max的左子树嫁接到prev的右子树。
• search：就是binary search!
• delete:非常复杂，但是基本思路是分情况讨论。看被删除节点的子树个数，分别是0，1，2个。然后针对不同情况分别处理。

  题目

binary search

• Leetcode 235. Lowest Common Ancestor of a Binary Search Tree
• Leetcode 270. Closest Binary Search Tree Value
• Find distance between two nodes in binary tree (Uber店面)这道题其实是LCA的马甲，我们先求出LCA，然后distance = dis(LCA, a) + dis(LCA, b)

Rank

• Leetcode 406. Queue Reconstruction by Height (这道题有greedy的思想在里面，那就是针对当前BST,如果有多个height符合rank，我们取height最小的那个。可以通过反正法来说明，如果不取他，那么后一个比他高的加进来就会使得这个height的rank变得invalid)
• Leetcode 315. Count of Smaller Numbers After Self

Select

• Leetcode 230. Kth Smallest Element in a BST (Snapchat店面）

Ceiling

• Leetcode 285. Inorder Successor in BST
• Leetcode 272. Closest Binary Search Tree Value II

Floor

• Leetcode 272. Closest Binary Search Tree Value II