- Structure
- 插入
- 查询
- 删除
- Order Operation
- 统计所有大于查询key的节点数
- 统计所有小于查询key的节点数
- 统计落在查询区间的节点数
- 找到大于查询key的最小节点
- 找到小于查询key的最大节点
- 找到查询key的后继节点
- 找到查询key的前驱结点
- 找到第k个大的节点
BST的节点如下图所示，count是用来统计以node为根的树的size，包括node本身：
1. Insert
插入节点我们在Insert Node in BST中已经讨论过了，就不细讲了。
2. Get
跟插入的思路是一样的
代码如下：
3. Delete
我们在 Remove Node' in BST中已经讨论过了，不细说。
4. Larger Than and Lower Than
思路跟二分是一样的，以lowerthan为例，如果在当前节点curr，value < curr.val 那么我们去左子结点继续统计。如果value > curr.val那么左子树size和当前节点都满足条件，然后去右子结点继续寻找。如果value == curr.val直接返回左子树size。largerthan的代码是类似的。
lowerthan代码如下：
5. Range Query
我们在Search Range in BST已经讨论过，这里只需要返回数量，更简单一些。
6. Floor(小于查询key的最大节点) and Ceiling(大于查询key的最小节点)
思路也是二分, 以ceiling为例，如果在当前节点curr，value >curr.val 那么我们去右子结点继续寻找。如果value <curr.val那么curr可能是可能不熟，我们先去左子树找，找不到的话就返回curr，找到的话就返回找到的。如果value == curr.val直接返回curr。floor的代码是类似的。
ceiling代码如下：
7. Predecessor and Successor
和Floor 和 Ceiling的思路基本上一直，代码只有小小的区别。
successor代码如下:
8. Find Kth
思路也是二分。n = 左子树的size + 1，是curr节点在tree里面排序的位置，从小到大。如果n < k的话，去右子树找第k - n个。如果n > k的话，去左子树找第k个。如果n==k说明curr正是我们要找的。
代码如下:
完整代码如下:
我们在 Remove Node' in BST中已经讨论过了，不细说。
4. Larger Than and Lower Than
思路跟二分是一样的，以lowerthan为例，如果在当前节点curr，value < curr.val 那么我们去左子结点继续统计。如果value > curr.val那么左子树size和当前节点都满足条件，然后去右子结点继续寻找。如果value == curr.val直接返回左子树size。largerthan的代码是类似的。
lowerthan代码如下：
5. Range Query
我们在Search Range in BST已经讨论过，这里只需要返回数量，更简单一些。
6. Floor(小于查询key的最大节点) and Ceiling(大于查询key的最小节点)
思路也是二分, 以ceiling为例，如果在当前节点curr，value >curr.val 那么我们去右子结点继续寻找。如果value <curr.val那么curr可能是可能不熟，我们先去左子树找，找不到的话就返回curr，找到的话就返回找到的。如果value == curr.val直接返回curr。floor的代码是类似的。
ceiling代码如下：
7. Predecessor and Successor
和Floor 和 Ceiling的思路基本上一直，代码只有小小的区别。
successor代码如下:
8. Find Kth
思路也是二分。n = 左子树的size + 1，是curr节点在tree里面排序的位置，从小到大。如果n < k的话，去右子树找第k - n个。如果n > k的话，去左子树找第k个。如果n==k说明curr正是我们要找的。
代码如下:
完整代码如下:
No comments:
Post a Comment