学习BST(BinarySearchTree)前需要先了解一下二叉树的一些基本知识：
-
二叉树相关概念：
一棵树可以没有任何节点，称为空树
一棵树可以只有1个节点，也就是只有根节点
节点的度指的是拥有的子树个数
树的度是指所有节点中的最大值
叶子节点指度为零的节点
节点的深度：从根节点到当前节点唯一路径上的节点总数
节点的高度：从当前节点到最远节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
-
二叉树的特点
每个节点的度最大为2
非空二叉树的第i层最多有2(i-1)个节点
高度为h的二叉树上最多有2h-1个节点
为什么是2h-1？
2h-1=20+21+22+…+2h-1
任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有n0=n2+1
-
二叉树与链表：
从小到大顺序添加二叉树将会退化成链表
n比较大时，之间的性能差异会非常大，n=1000000时，二叉搜索树最低高度为20
Olog(n)怎么算出来的？
预备知识：二叉树的高度与节点的关系：高度为h的二叉树上最多有2h-1个节点
在一个树中查找一个数字
第一次在根节点判断，第二次在第二层节点判断
以此类推，树的高度是多少就会判断多少次(最坏情况)
节点总数 n=2h-1
h=log2(n+1) --> O(logn)
删除节点也可能会导致二叉树退化成链表
有没有办法防止二叉树退化成链表，将复杂度维持在O(logn)
-
满二叉树和完全二叉树
满二叉树：
1、深度为k且含有2k-1个结点的二叉树
2、所有节点的度要么为0，要么为2，且所有叶子节点都在最后一层
完全二叉树：
1、树中所含n个节点与满二叉树的节点编号一一对应
2、叶子节点只会出现在最后两层，且叶子节点都是靠左对齐
满二叉树和完全二叉树添加节点大小比较都是从上到下，从左到右。
完全二叉树的结构决定了同样节点的二叉树，完全二叉树的高度最小
-
真二叉树
真二叉树：所有节点的度要么为0，要么为2
由上面性质可知 满二叉树 一定是真二叉树，真二叉树 不一定是满二叉
-
二叉搜索树
问题：在n个数中搜索某个整数？
假设使用动态数组存放元素，从第0个位置开始遍历搜索，时间复杂度为O(n)，若使用二分搜索，将树中节点全部遍历，最坏时间复杂度为O(logn)，但是添加，删除的平均时间复杂度仍是O(n)
有没有更好的办法，将增加、删除、查找的时间复杂度都维持在O(logn)，就可以使用到二叉搜索树
二分搜索:不断将数组进行对半分割，每次拿中间元素和目标值进行比较
BST的特点：
1、任意节点的值大于左子树所有节点的值
2、任意节点的值小于右子树所有节点的值
3、任意节点的左右子树也是BST
-
BST
二叉搜索树接口设计：
int size() //元素的数量
boolean isEmpty() //是否为空
void clear() //清空所有元素
void add(E element) //添加元素
void remove(E element) //删除元素
boolean contains(E element) //是否包含某一元素
关键变量：
private int size;
private Node<E> root;
private Comparator<E> comparator;
size为节点数量，root是根节点，comparator为比较器
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
在新建一个二叉搜索树时，可以选择自定义的比较器 或者 如过没有自定义的比较器则默认为官方自带的（util里的comparator）
节点内部类：
private static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
add方法：
public void add(E element) {
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = newNode(element, null);
size++;
return;
}
// 添加的不是第一个节点
//先执行一次循环体逻辑
// 找到父节点
Node<E> parent;
Node<E> node = root;
//root.right.right.right
int cmp = 0;
do {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.element = element;
return;
}
} while (node != null);
//至此找到插入的父节点
// 连接指针（构建新节点指向父节点，父节点指向新节点）
Node<E> newNode = newNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
添加操作需要两步，第一步找到的插入位置节点和新节点的父节点，第二步将新节点与父节点连接
第一步中找到的插入位置节点此时这个节点是不存在的，等着在第二步中进行创建
需要两个变量（节点），一个变量用于查找插入位置节点，用于在查找过程中不断进行迭代更新；另一个变量为父节点负责连接新建的子节点
关键点说明
按照二叉树的原则（右节点 > 父节点，左节点 < 父节点）左小右大，因此新节点需要与父节点进行比较。官方comparable接口中comparaTo方法
Comparable接口将比较代码嵌入自身类中(类内部实现)，而Comparator既可以嵌入到自身类中，也可以在一个独立的类中实现比较
如果需要比较的element是基本类型，comparable接口已经对其进行了实现。但是如果是对象类型时，需要我们自己重写comparaTo方法。这里我们没有在对象类里面重写comparaTo方法，而是给二叉树提供一个私有的comparator比较器（官方也定义过comparator比较器）
private Comparator<E> comparator;
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
这样在外部调用时就可以实现多个比较器
比较返回结果相等时 node.element=element，这里为什么需要覆盖而不是直接返回，考虑到以下情况：
public static void main(Stirng args[]){
private static class Person{
public String name;
public int age;
public Person(name,age){
this.name=name;
this.age=age
}
}
BinarySearchTree<Person> bst2 = new BinarySearchTree<>(new Comparator<Person>() {
public int compare(Person o1, Person o2) {
return o2.getAge() - o1.getAge();
}
});
bst.add(new Person(10,"zhangsan"));
bst.add(new Person(8,"lisi"));
bst.add(new Person(10,"wangwu"));
}
如出现这种，不再是单一变量而是多个变量的情况，比较器是比较年龄，每个节点装着person，但年龄一样而名字却不一样，所以必须覆盖
Comparator和Comparable的区别comparable和comparator接口的区别城有万心各千寻的博客-CSDN博客
remove方法:
remove时会遇到三种情况：
1、删除叶子节点
判断节点位置，然后直接断掉父节点对其的依赖即可，分为根节点和普通节点
if(node.parent==null){
root=null;
}else{
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
}
2、删除度为1的节点
同样分为根节点还是普通节点两种情况，指向替代节点
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
3、删除度为2的节点
二叉搜索树任意节点都大于左子树所有节点，小于右子树所有节点
前驱节点：前驱节点是比待删除节点小且最接近它的节点，左子树中最右边的节点（左子树中的最大值）
后继节点：后继节点是比待删除节点大且最接近它的节点，它肯定是待删除节点的右子树上的最小值节点
所以删除度为2的节点所找的替代节点只能是前驱或者后继节点
后继节点
protected Node<E> successor(Node<E> node) {
if (node == null) return null;
//后继节点 右子树中的最小值
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找后继节点
// 比当前节点大的最小节点 一定是父节点的左子节点
//如果是父节点的右子树就需要一直往上找
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
}
}
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
源码解析：
为了满足二叉树的特性（父节点的值大于左边节点的值，小于右边节点的值），因此删除度为2的节点需要先找到前置或者后继节点进行取代，然后删除前置或者后继节点。而度为2节点的前置或后继节点的度只能为0或者1，所以可以重用删除度为0或者1的节点的代码。
node=s说明：
相当于将后继节点移动到了待删除节点的位置，然后再删除后继节点node。通过node.parent.left或者node.parent.right找到node
node本身的内存地址不会发生变化，node存储的内存地址发生了变化
clear方法
public void clear() {
root = null;
size = 0;
}
清除一颗二叉树，只需要将root设置为null即可
