二叉搜索树
二叉搜索树也叫二叉查找树或者二叉排序树，它要么是一颗空树，要么满足以下几点：
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3.任意节点的左、右子树也分别为二叉搜索树。
4.没有键值相等的节点。
二叉搜索树的实现
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 点的图例：
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 个节点的链表就是采用的红黑树。
所以二叉搜索树在查找上是非常快的，在一些需要很高查询效率上推荐使用。
PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。