纯数据结构Java实现(4/11)(BST)
个人感觉，BST(二叉查找树)应该是众多常见树的爸爸，而不是弟弟，尽管相比较而言，它比较简单。
二叉树基础
理论定义，代码定义，满，完全等定义
不同于线性结构，树结构用于存储的话，通常操作效率更高。就拿现在说的二叉搜索树(排序树)来说，如果每次操作之后会让剩余的数据集减少一半，这不是太美妙了么？(当然不当的运用树结构存储，也会导致从 O(logN) 退化到 O(n))。
- 值得说明，O(logN) 其实并不准确，准确来说应该说 O(树的高度)
定义&性质&行话
树里面常见的二叉树: BST, AVL，特殊的AVL(比如2-3树，即红黑树)。
不常见的有(包括多叉树): 线段树，Trie。(但我们说的不常见，不见得真的不常见，可能内核或者框架里面有用到，而写应用的没有用到；所以常见或者不常见是没有一个确定概率基准的，个人把一般写应用的标准定义为基准)
二叉树就是一个最多: 一个爸爸，俩孩子 的树。
这样说，不形象，那形象点儿，直接上代码:
class Node {
E e;
Node left;
Node right;
}当然，理论教科书上肯定不会这么傻帽的直接告诉你具体情况，它要绕一下，先来一个递归定义，把你绕晕，有图有真相:
然后一个节点也是树，空(null) 也是树。
这里有一些行话，包括上面的认为 logN 就是树高(在一般性的时间复杂度分析时)，解释:
- 深度为 n 的二叉树，每层最多有 2^(n-1) 个节点
- 深度为 n 的二叉树，总共元素，最多有 2^n -1 个节点
(深度从 1 开始，从上往下看)(自己画一下图，脑海中想一下就知道了)
其他行话，满二叉树，完全二叉树，尤其完全二叉树这个概念，后续树结构中有很重要的意义。
- 满的很好理解吧，图上理解，就是所有父亲都有俩孩子；数据上就是元素总共为 2^n-1
- 完全二叉树: 如果你从上到下，从左到右给树的节点编号，那么树应该是你看到的方向排布。
设二叉树的深度为h，除第 h 层(最后一层)外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
个人经验，直接看最后一层是否靠左。
BST基础
BST 说白了也是一种查找树，只是它的存储是有序的。
- (删除的时候要调整，就知道维护的代价了)
存入的值要么是可比较的，要么不能自身提供比较方法时，要主动传入比较器(Comparator)
也就是说，任意一个节点(它作为根节点看待)，它的左子树的值都比它要小，右子树的值都比它大。（正是因为其存储的时候就有序，所以取的时候也高效）
哦，BST 和满二叉树没啥关系。
BST实现
基本框架
先设置好节点信息，大概如下:
package bst;
//二分搜索树
public class BST<E extends Comparable<E>> {
//声明节点类
private class Node {
public E e;
public Node left, right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
//成员变量
private Node root;
private int size;
//构造函数
public BST() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}清晰，简介，然后来补充增删查改，遍历等方法。
先做一个规定，对于重复元素的处理是: do nothing。
(它已经在树上了，就不要动了；或者你可以给 Node 增加一个属性 count，专门记录)
增加操作
想象一下，放一个元素到树上，从根节点开始比较，以后的比较也是根据当前树的根元素，从而决定放在左子树，还是右子树上。(上面已经说了，相等的元素，什么也不干)
上面的分析其实已经很清楚了，那么下面考虑一下写法:
- 递归怎么写: 每次切换当前 root 元素，即要搜索的子树
- 终结条件(base condition): 找到了相关的位置(null)，然后放入元素，返回以该节点为根的子树给上级树，的左/右孩子接收
- 子树不为空，且元素值不等，说明不是终极条件，那接着切换子树找啊
- 循环怎么写: 思想类似上面，不断下探的过程改成while循环的解法，即不断递推替换 currNode 为其左或者右子树的根节点(就是孩子啦)
- 技巧是，在寻找合适位置时，不仅需要记录 curr，还要记录 parent
- 并且实际插入的时候，还是以 parent，即子树的根为合适位置的依据(这根递归做法不同)
一般教科书上才会介绍循环的写法，大致如下: 《算法-C描述》
OK，我们还是用 递归去写吧，不是偷懒，而是递归更易于宏观理解啊傻
递归的写法: 不断的切换每层调用的 root 节点的指向 (相当于切换到子树)
大致写法如下: (注意柯里化包裹 — 柯里化参考阮一峰的博客JS语言部分)
- 上面已经说了优化过的递归终止条件，但是也可以像下面这样没有优化(即还没有判断到底就开始分情况返回) — 作为思考的中间结果吧 — 优化的结果看最后面的实现。
//向二分搜索树中添加元素
private void add(E e) {
if(root == null) {
root = new Node(e);
size++;
} else {
//切换当前 root 节点进行递归调用
add(e, root); //第一次调用时已经确定 root != null 了
}
}
private void add(E e, Node node) {
//这里的 node 相当于一个子树的 root
//复杂的递归终止条件
if(e.equals(node.e)) {
//已经存在了，do nothing
return;
} else if(e.compareTo(node.e)>0 && node.right == null) {
//不存在子树的情况
//右子树为空，直接插入
node.right = new Node(e);
size++;
return;
} else if(e.compareTo(node.e)<0 && node.left == null) {
node.left = new Node(e);
size++;
return;
}
//一般的情况，即存在左或者右子树的情况
//此时已经判断 right 或者 left 不为 null 了
if(e.compareTo(node.e)>0) {
//应该在右子树上找位置
add(e, node.right);
} else {
//在左子树上找位置
add(e, node.left);
}
}但是终止条件可以写的更加简单一点，即一直找到空位置再说插入的事儿，而不是分情况判断时就作为终止条件:
- 找到那个空位置，就在那个位置插入
此时，可以看到，递归函数 add 也需要修改成有返回值了，然后让这个返回值和原BST挂接。(返回以当前节点为根的子树，挂接给上级才对；思想就是: 上级只关心完整的结果!)
//返回插入新节点后BST的根 (每层调用都是如此)
private Node add(E e, Node root) {
if (root == null) {
size++;
return new Node(e);
}
if (e.compareTo(root.e) > 0) {
//放在右子树
//因为add 函数返回的就是 插入新节点后BST的根
root.right = add(e, root.right);
} else if (e.compareTo(root.e) < 0) {
root.left = add(e, root.left);
}
//相等的情况？抱歉，啥也做
return root;
}- 这里的症结就在于，给当前root的子树(不管左右哪一个)，插入完成后，都会对当前 root 的左或者右孩子进行重新赋值（后半句是，所以才不关心左右子树空不空）
而递归代码中已经包含了 root == null 的情况，即空BST的情况，所以主调函数可以直接调用 private 的 add，而不必再判断 root 为 null:
//client 调用
//向二分搜索树中添加元素
private void add(E e) {
root = add(e, root);
}查询操作
这就相当于二分查找，不断的折半 — 这里判断是否存在即可
也可以分为用递归和非递归的写法，然而递归的写法会简单很多，能写递归也能写循环。
递归的写法
- 不断的更换子树 (以根为子树的依据)
//查询元素是否存在
public boolean contains(E e) {
return contains(root, e);
}
//以 root 为根的BST中是否存在 e
private boolean contains(Node root, E e) {
if(root == null) {
return false;
}
if (e.compareTo(root.e) > 0) {
//去查右子树
return contains(root.right, e);
} else if (e.compareTo(root.e) < 0) {
return contains(root.left, e);
}
//return root.e.compareTo(e) == 0;
return true;
}最后的root.e.compareTo(e) 没有必要，因为除了 > 和 < 剩下的就是 == 的情况了。
遍历操作(递归)
遍历相对来说还是比较容易的，这里先说深度优先。
深度优先: 先序遍历，中序遍历，后序遍历；这些都是相对于根元素来说的。
以 先根遍历 来举个例子:
public void preOrder() {
preOrder(root);
}
private void preOrder(Node root) {
if(root == null) {
return;
}
System.out.println(root.e);
preOrder(root.left);
preOrder(root.right);
}到这里可以简单测试一下:
public static void main(String[] args) {
BST<Integer> bst = new BST<>();
int[] nums = {5, 3, 6, 8, 4, 2};
for(int num: nums){
bst.add(num);
}
bst.preOrder(); //5 3 2 4 6 8
}其他的遍历方式，其实就非常容易改写了。
例如 中根遍历:
//中序遍历
public void inOrder() {
inOrder(root);
}
private void inOrder(Node root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.println(root.e);
inOrder(root.right);
}
//测试输出: 2 3 4 5 6 8 (相当于一个排序结果)从输出的结果可以看到一个性质，BST的中序遍历结果是一个排序结果。
例如 后序遍历:
//后序遍历
public void postOrder() {
postOrder(root);
}
private void postOrder(Node root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.println(root.e);
}先把孩子处理好，再来弄自己的事儿。。。可以联系到内存释放，先释放子窗口的，最后在关闭 main。
遍历操作(非递归)
这里用变量的迭代器换也能写，不过我见过的比较高明的手段，用栈来写。
用栈记录后面需要操作(当前还不需要执行)，当前处理的则出栈(这里运用上，有一些技巧)，我直接说了:
- 每次都出栈当前子树根元素(打印操作)，然后把它的左右子节点反序放入栈中(反序是因为栈是后入先出的);
- 什么时候结束，树遍历完毕的时候；即栈里没有内容了
可以看下代码实现:
//先序遍历，非递归写法
public void preOrderNR() {
Stack<Node> stack = new Stack<>();
stack.push(root); //开始之前的准备，真正的根入栈
while (!stack.isEmpty()) {
Node curr = stack.pop(); //出栈当前的根元素
System.out.println(curr.e);
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}开始之前，根元素入栈，保证栈里面有内容，然后第一次检查栈，出栈一个元素，即真正的根元素，先打印它，接着其左右孩子反序入栈。下次循环，后入栈的左子树根出栈，进行左边子树的整个操作，全部完毕后才轮到右子树(的根出栈，然后完成类似结果)。
举一个形象的例子:
16 出栈后，此时压入 16 的右孩子 22，然后压入左孩子 13。(遍历的反序)
中序遍历，后序遍历的非递归实现？麻烦自己写一下，貌似没有太多实际参考。
层序遍历
就是广度优先啦，这个概念貌似应该用于图，但树也可以用到。
广度优先觉得更应该用于决策，因为它会避免你一条路走到黑。(不至于把一棵子树全部找完，然后发现没找到，才去找另一个子树。。。)
这个我比较熟悉，一般需要借助队列，写非递归实现:
- 每次出队一个元素(当前的根节点)时，把其孩子也先后放入队列中(等待后续遍历)
- 从结果来看，就是层序遍历了 (可以想象一下文件夹的遍历，把当前文件夹的子文件夹放入队列的尾部)
在脑海中可以想象一下，现实司令级别的班子先过，每次检查到一个司令(出队)，就把他手下的军长排在队列的尾部(即所有司令的后部)，这样一直不断，知道司令外部出去，检查第一个军长，同理把他手下的师长全部入队(即所有军长的后面)…直到队列为空，全部遍历完毕。
直接写代码:
//广度优先-层序遍历
public void levelOrder() {
Queue<Node> queue = new LinkedList<>(); //util linkedlist 实现了 queue 接口
queue.add(root);
while((!queue.isEmpty()) {
Node curr = queue.remove();
System.out.println(curr.e);
if(curr.left != null) {
queue.add(curr.left);
}
if(curr.right != null) {
queue.add(curr.right);
}
}
}忘了说了，层序遍历，先左后右。
在图中的遍历还需要记录某个节点是否访问过，因为二叉树的爸爸只有一个，但是图中节点的前驱可能有多个的，为避免重复遍历，所以必须标记一下是否访问过。
删除操作(重点)
整个 BST 的难点就在这里，想也知道啊，我删了一个元素，那么以这个元素为根的树怎么调整才能与当前元素的上级挂接(嫁接)好呢？
(复杂可能在于，需要重新排序树)
题外话:
我自个儿也是琢磨了一会儿，然后发现对付复杂，**先从特例上找规律，然后推广到一般**。
特例的规律如若不能推广到一般，那么就按照第二种思路: 分分合合。
* 分: 详细分析情况，不漏掉情况(暴力穷举)
* 合: 这些具体的，分情况的方案能否合并，上升到一个层级规律
这样的好处，即便不能合，那么分情况的穷举(暴力解法)，我们也能保底。(解决的不优雅，但按性质划分还是属于已解决的分类，有政治优势)直接说结论，这里采用的是(找到元素)替换(覆盖)要被删除的元素
找一个怎么样的节点去替换啊? 找一个最接近被删除元素大小的元素替换。
- 此时其实挪动和改变最少，且满足删除后该树仍旧是一棵BST的要求
最接近的元素: 要删除元素的左子树上找最大，要删除元素的右子树上找最小。
先看看一棵子树上怎么找最大最小:(铺垫)
- 查找最小值: 一直寻找左孩子，直到最左边的一个节点没有左孩子(null)。
- 查找最大值: 一直寻找右孩子，直到最右边的一个节点没有右孩子(null)。
大致实现如下:
//获取树的最小值 (递归写法)
public E getMin() {
if(isEmpty()) {
throw new IllegalArgumentException("Tree is Empty");
}
return getMin(root).e;//调用递归的写法
}
private Node getMin(Node node) {
if(node.left == null) {
return node;
}
return getMin(node.left);
}
//树的最大值 (非递归写法)
public E getMax() {
if(isEmpty()) {
throw new IllegalArgumentException("Tree is Empty");
}
Node curr = root;
while(curr.right != null) {
curr = curr.right;
}
return curr.e;
}这里是拿到值，所以简单，但是删除的话，处理的是 Node，而不仅仅是值。
所以拿到最小元素的节点(当然顺带也要删除这个值)，以及拿到最大元素的节点(顺带也要删除这个值)，这两个值一定是最接近当前元素的，用它们中的一个，来覆盖当前被删除的元素的位置即可。
找到并删除(当前元素相关的)最小元素:
- 最小元素: 向左找没有左节点的最终节点
- 该节点没有孩子，(左子树一定为空了)，直接删除 —— 叶子节点的情况
- 该节点有右子树，直接返回该右节点 (作为子树的根，进行下一次循环或者递归起点) —— 非叶子节点
- 维护 size 的大小
代码实现:
//删除最小值 (递归写法)
public E removeMin() {
E ret = getMin(); //不需要 isEmpty判断了
root = removeMin(root); //操作完毕返回新树的根
return ret;
}
//删除以 node 为根的子树的最小节点；返回该子树的根
private Node removeMin(Node node){
//base 情况
if(node.left == null) {
//当前子树的左子树为空(不管右子树如何)，说明当前节点最小
//当然，如果有右子树，要把右子树嫁接到父节点(返回右子树的根给上级即可)
//删除同时还要把当前节点的孩子置空
Node rightNode = node.right; //当前节点的左子树可能为空
node.right = null; //(当前节点的左子树已经为空了)
size--;
return rightNode;//返回给上级(具体说，上级的左子树)
}
//一般情况 (以 node 为根，还有左子树)
node.left = removeMin(node.left); //递归过程返回调整后的子树(根节点)
return node; //每次都返回该子树删除最小值之后的结果
}找到并删除(当前元素相关的)最大元素:
此过程类似于删除最小元素，递归操作时，每次都返回删除该node为根的子树的根节点，让上级节点的右节点接收。(末尾节点(右子树一定空)如果没有子节点，即左节点也为空，那么 base 就返回 null，否则把左子树嫁接到上级，具体说就是上级节点的右子树)
代码实现:
//删除最大值 (递归写法)
public E removeMax() {
E ret = getMax();
root = removeMax(root);
return ret;
}
//返回删除最大值后的根节点(子树)给上级节点
private Node removeMax(Node root) {
//Base 情况(末尾节点)
if(root.right == null) { //没右子树了
//判断其是否还有左子树，然后把左子树返回给上级节点(的右子树接收)
//同上，不必判断，因为 root.left 即便为 null 也包含在这种情况中
Node leftNode = root.left;
root.left = null;
size--;
return leftNode;
}
root.right = removeMax(root.right);//有右子树那就在右子树上找
return root;
}从上面删除最大，最小的逻辑，可以推广到一般情况，具体来说，举个例子:
- 删除 58 很容易，直接把 60 这个节点返回给右子树 (因为 41 为根的这棵树已经有左子树)
-
删除 22 则情况至少有两种(左右都有节点)，一种 15 上位(作为 41 的左子树)，然后 33 接在 15 的右子树上，另外一种则是 33 上位，然后 15 接在 33 的左子树上
- 这里 22 的子树比较特殊(只有半边子树)，所以可以很容易看出两种情况
- 也就是说，可以在左边找前驱，也可以在右边找后继
- 叶子节点更简单，不必单独拿出来，直接返回给上级一个 null 即可作为子树即可
若某节点的子树都是满的，则不那么容易，以后继为例，讲一下思路:
其实就是在右子树上找一个最节点最接近当前值的节点，替代当前要删除的节点。即 min(d->right)。换句话说，右子树中找到最小元素(其实是删除掉这个元素)，然后在 d 的位置填补这个元素，图例如下:
上面把 s 的一切设置好(left, right)，此时 s 就是整个调整完毕的子树根，把它返回给上级树的右子树即可。
这里已经可以看出，结论如下:
- 但凡有一边子树是空的，就是特殊情况，方便处理(下面代码也会证明这一点)
- 整整困难的是两边都是满的，此时需要 找前驱或者后继，替换 这种思路(至于用前驱还是后继，随意; 因为都能保证之后的树是一棵BST)
那么代码实现: (参考删除最大最小的逻辑，推到删除的一般逻辑，以后继为例)
/*找后继的实现*/
//用户指定删除某个值 e 的节点
public void remove(E e) {
root = remove(root, e); //每次递归都是返回操作后的子树(根节点)
}
/*
删除以 root 为根的子树中值为 e 的节点
返回操作完毕后子树的根
*/
private Node remove(Node root, E e) {
//先要找到这个元素
//base 情况 (前一次递归调用返回的是 null 的情况)
if (root == null) {
return null; //这个空值最终会作为上级树的孩子
}
//(分情况在子树上找)
if (e.compareTo(root.e) > 0) {
//在右子树上找
root.right = remove(root.right, e);
} else if (e.compareTo(root.e) < 0) {
//在左子树上找
root.left = remove(root.left, e);
} else {
// 找到的情况 e.compareTo(root.e) == 0
//从其左右子树上找替换元素 (这里采用后继进行替换)
//同时需要返回新的根节点给上级
/*
1.左右子树都在 (融合的情况) -- 找到右子树上最小元素进行替代
2.左子树在，但是没有右子树 (类似于删除最大值的逻辑)
3.右子树在，但是没有左子树 (类似于删除最小值的逻辑)
4.左右子树都空了，叶子节点(直接 return null) 即把空子树返回给上级节点(这一种情况已经包含在2, 3的写法中了)
先写 2, 3, 4 这类简单的情况 (返回值接在上层左子树还是右子树不确定，这要看上层的递归调用是哪种情况)
*/
if (root.right == null) {
Node leftNode = root.left;
root.left = null;
size--;
return leftNode; //包含了 leftNode 也为 null 的情况
}
if (root.left == null) {
//类似于查找最小值的情况
Node rightNode = root.right;
root.right = null;
size--;
return rightNode;
}
//左右子树都不空的情况(先找到替代节点 successorNode )
Node successorNode = getMin(root.right);
successorNode.right = removeMin(root.right); //返回的是删除最小元素后的根节点
successorNode.left = root.left;
//置空原来 root 的 left 和 right
root.left = root.right = null;
return successorNode; //返回设置好的元素给上级
}
return root;
}上面的代码，找到要替换的元素时，分情况分析，即:
1.左右子树都在 (融合的情况) — 找到右子树上最小元素进行替代
2.左子树在，但是没有右子树 (类似于删除最大值的逻辑) — 代码类似
3.右子树在，但是没有左子树 (类似于删除最小值的逻辑) — 代码类似
4.左右子树都空了，叶子节点(直接 return null) 即把空子树返回给上级节点(这一种情况已经包含在2, 3的写法中了)
这相当于在暴力穷举了，然后发现貌似确实不能合并，所以就这样划分了。
BST总结
这里会总一些可能有用的结论:
最重要的一条，BST的有序性(放入其中的元素，有序存储)是有维护代价的
- 遍历：中序遍历，所有元素是升序排列。
- 最大值，最小值: 不断向左找左子树，不断向右找右子树。
- 前驱和后继(节点): 左子树中找最大值就是前驱(predecessor)，右子树中找最小值就是后继(successor)。
- 每个节点Node可以维护额外的属性，比如 count, rank, depth 等，适用于业务查询
- floor 和 ceil: 寻找某个值的 floor 和 ceil
- 该元素可以不在树上
整个看下来，也就是删除上要仔细考虑好几种情况以及破天荒的有 替换 的思维。
它的实现基本上就先这样(应用上有很多变形，但这与其实现无关，后面再说)。
老规矩，代码请参考 gayhub。