二叉搜索树
二叉搜索树也叫二叉查找树或者二叉排序树，它要么是一颗空树，要么满足以下几点：
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3.任意节点的左、右子树也分别为二叉搜索树。
4.没有键值相等的节点。
image
二叉搜索树的实现
1.二叉搜索树的存储结构
public class BinarySearchTree {
public static Node root;
public BinarySearchTree(){
this.root = null;
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
2.二叉搜索树的插入
a.循环二分查找到需要插入的地方。
b.假如插入的值小于当前的值，并且当前左节点为空，那么左节点就指向新节点。
c.假如插入的值大于当前的值，并且当前右节点为空，那么右节点就指向新节点。
public void insert(int id){
Node newNode = new Node(id);
if(root == null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id < current.data){
current = current.left;
if(current == null){
parent.left = newNode;
return;
}
} else {
current = current.right;
if(current == null){
parent.right = newNode;
return;
}
}
}
}
3.二叉搜索树的删除
a.当删除节点为叶子节点时，直接删除节点。
b.当删除节点只有左子树时，重接左子树。
c.当删除节点只有右子树时，重接右子树。
d.当删除节点既有左子树，又有右子树时，先找一个可以替换删除节点的节点。由于二叉树的性质，左子树的值小于根节点的值，右子树的值大于根节点的值。所以右子树的最左的节点就是替换删除的节点，然后在重接右子树。
第 d 点的图例：
image
public boolean delete(int id) {
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while (current.data != id) {
parent = current;
if (current.data > id) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
if (current == null) {
return false;
}
}
//删除的节点既没左节点，也没右节点
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
}
if (isLeftChild == true) {
parent.left = null;
} else {
parent.right = null;
}
}
//删除的节点只有左节点
else if (current.right == null) {
if (current == root) {
root = current.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
//删除的节点只有右节点
else if (current.left == null) {
if (current == root) {
root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
//删除的节点既有左节点，又有右节点
else if (current.left != null && current.right != null) {
//找到右子树的最左节点
Node successor = getSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode) {
Node successsor = null;
Node successsorParent = null;
Node current = deleleNode.right;
while (current != null) {
successsorParent = successsor;
successsor = current;
current = current.left;
}
if (successsor != deleleNode.right) {
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
4.二叉搜索树的查找
public boolean find(int id) {
Node current = root;
while (current != null) {
if (current.data == id) {
return true;
} else if (current.data > id) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
总结
由于它是一颗有序的树，就可以进行折半查找，每一次查找，假如不是匹配的值，都可以排除一半的值。所以一般的时间复杂度是 O(log n)。假如这棵树退化为斜树，就差不多是线性表了，它的时间复杂度就是 O(n)。
虽然二叉搜索树的最坏时间复杂度是 O(n)，但通过一些改进可以把最坏时间复杂度降至 O(log n)，比如 AVL树、红黑树等。红黑树不需要绝对的平衡，所以插入和删除效率上要高，在 JDK1.8 中哈希表存储大于等于 8 个节点的链表就是采用的红黑树。
所以二叉搜索树在查找上是非常快的，在一些需要很高查询效率上推荐使用。
