二叉查找树
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
public class TreeNode {
private int data;
private TreeNode leftNode;
private TreeNode rightNode;
}
public class BinarySearchTree {
private TreeNode rootNode;
public TreeNode find(int data) {
TreeNode currentNode = rootNode;
while (currentNode != null) {
if (currentNode.getData() == data) {
return currentNode;
} else if (currentNode.getData() > data) {
currentNode = currentNode.getLeftNode();
} else {
currentNode = currentNode.getRightNode();
}
}
return null;
}
public void insert(int data) {
if (rootNode == null) {
rootNode = new TreeNode(data);
return;
}
TreeNode currentNode = rootNode;
while (true) {
if (currentNode.getData() > data) {
if (currentNode.getLeftNode() == null) {
currentNode.setLeftNode(new TreeNode(data));
return;
}
currentNode = currentNode.getLeftNode();
} else {
if (currentNode.getRightNode() == null) {
currentNode.setRightNode(new TreeNode(data));
return;
}
currentNode = currentNode.getRightNode();
}
}
}
/**
* 删除的情况比较复杂
* 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的
* 指针置为 null。
* <p>
* 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要
* 更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
* <p>
* 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右
* 子树中的最小节点，把它替换到要删除的节点上（比要删除的节点大一点点的数）。
* 然后再删除掉这个最小节点（父节点的指针改变），因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），
* 所以，我们可以应用上面两条规则来删除这个最小节点
* <p>
* 注：左子树最大节点是可能有子节点的，左子树总是小于根节点的，右子树总是大于根节点的
*
* @param data
*/
public void delete(int data) {
TreeNode treeNode = rootNode;
TreeNode parentNode = null;
while (treeNode != null && treeNode.getData() != data) {
parentNode = treeNode;
if (treeNode.getData() > data) {
treeNode = treeNode.getLeftNode();
} else {
treeNode = treeNode.getRightNode();
}
}
if (treeNode == null) {
return;
}
if (treeNode.getLeftNode() != null && treeNode.getRightNode() != null) {
//有两个节点的时候
TreeNode minNode = treeNode.getRightNode();
TreeNode minParentNode =treeNode;
while (minNode.getLeftNode()!=null){
minParentNode = minNode;
minNode = minNode.getLeftNode();
}
treeNode.setData(minNode.getData());
//接下来删除这个最小节点，走下面的流程
treeNode = minNode;
parentNode = minParentNode;
}
//证明有一个节点或者0个节点的时候
TreeNode child;//删除节点的子节点
if (treeNode.getLeftNode() != null) {
child = treeNode.getLeftNode();
} else {
child = treeNode.getRightNode();
}
if (parentNode == null) {
rootNode = child;//清空二叉树
return;
}
if (parentNode.getLeftNode() == treeNode) {
parentNode.setLeftNode(child);
}
if (parentNode.getRightNode() == treeNode) {
parentNode.setRightNode(child);
}
}
public void printNode() {
inPrint(rootNode);
}
private void inPrint(TreeNode treeNode){
if (treeNode.getLeftNode()!=null){
inPrint(treeNode.getLeftNode());
}
System.out.println(treeNode.getData());
if (treeNode.getRightNode()!=null){
inPrint(treeNode.getRightNode());
}
}
}
通过上面的分析可知，我们的查找删除新增，其时间复杂度都和树的高度成正比，为O(height)，遍历的时间复杂度是O(n)，树的高度等于最大层数-1
包含 n个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点。
依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。
不过，对于完全二叉树来说，最后一层的节点个数有点儿不遵守上面的规律了。它包含的节点个
数在 1 个到 2^(L-1) 个之间（我们假设最大层数是 L）。如果我们把每一层的节点个数加起来
就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：
n >= 1+2+4+8+…+2^(L-2)+1 最后一层只有1个
n <= 1+2+4+8+…+2^(L-2) + 2^(L-1) 最后一层满了
借助等比数列的求和公式，我们可以计算出，L 的范围是 [log 2^(n+1), log2^(n) +1]。
完全二叉树的层数小于等于 log2^(n) +1，
也就是说，完全二叉树的高度小于等于 log2^n。
显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不
管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，一种特殊的二叉查找树，平衡二叉查找树。平衡二叉查找树的高度接近 log2^n，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。
相对于hash表来讲，其删除，增加，查找的时间复杂度都是O(1),为什么还要用二叉查找树呢；
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。