上一个博客介绍了堆结构，这种结构非常有利于查找最大/最小元素。但是其也有一个非常显著的缺点，对于其他的元素的查找非常困难。这一节将要介绍的是二叉查找树，这种结构保持了这样的特性：其父节点大于左子节点，而小于其右子节点。
另外因为放假的原因将博客停了一段时间，接下来会恢复这个系列。由于后面博主主要打算找java开发相关的岗位，后续的实例代码和讲解可能要偏向于java，这点和之前一直用c++讲解稍有区别。
数据表示
二叉查找树和其他的树结构一样都是基于节点Node的一种数据结构。每个节点都含有一个键、一个值、一条左链接和一条右链接。这里有所不同的是，为了后续某些操作的方便，每个节点还有一个节点计数器。如下代码所示（java）：
private class Node { private Key key; // 键 private Value val; // 值 private Node left, right; // 左和右子节点 private int size; // 以该节点为根的子树中的节点总数 public Node(Key key, Value val, int size) { this.key = key; this.val = val; this.size = size; }} 基本操作的分析
查找
在二叉查找树里进行查找是简单的。假设我们在一棵根节点为root的二叉查找树中查找值为value的节点。我们只需将value和root.val相比较就行了，如果value更大，则在右子树里进行查找；反之则在左子树里进行查找。如此迭代下去即可。代码如下：
public Value get(Key key) { return get(root, key);}private Value get(Node x, Key key) { if (key == null) throw new IllegalArgumentException("calls get() with a null key"); if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val;} 插入
插入也是类似的，只不过这里要注意的是：由于插入改变了树的结构，所以一定不要忘了更新被插入元素的size。如果是递归的话，将更新写在最后就能够保证先计算子节点的size，再计算父节点的size，这一点一定要注意，代码如下：
public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("calls put() with a null key"); if (val == null) { delete(key); return; } root = put(root, key, val); assert check();}private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; x.size = 1 + size(x.left) + size(x.right); return x;} 总结
以上就是二叉查找树的两个核心操作了，另外还有更多的代码和操作请戳。由于二叉查找树不能保证树的平衡性，最差的时候其性能会退化到N(平均情况下是1.39lgN)。所以在实际中很少使用，在java集合以及c++ stl中用的是平衡的二叉树，例如红黑树等。这是后一博客要讨论的内容。
参考资料：
《算法》第四版
《STL源码剖析》See you next time. Happy Coding!!!