以前上学的时候一直觉得树结构没有实际用处，也没有好好学，只是做了简单了解，可是往往不积跬步无以至千里，工作中往往很多大的架构设计和实现都是有着最初的简单而来，所以在此沉淀一下近几年所见所知，再一个也对很多认为树结构无用论初级点的码农（其实归根到底还是不清楚树的实际用途）普及下树结构在实际生产中的用途。

下面看一个例子：

一：场景

1：现状

前几天我的一个大学同学负责的网站出现了严重的性能瓶颈，由于业务是写入和读取都是密集型，如果做缓存，时间间隔也只能在30s左右，否则就会引起客户纠纷，所以同学也就没有做缓存，通过测试发现慢就慢在数据读取上面，总共需要10s，天啊…原来首页的加载关联到了4张表，而且表数据中最多的在10w条以上，可以想象4张巨大表的关联，然后就是排序+范围查找等等相关的条件，让同学抓狂。

2：我个人的提供解决方案

① 读取问题

既然不能做缓存，那没办法，我们需要自己维护一套”内存数据库“，数据如何组织就靠我们的算法功底了，比如哈希适合单key（等于性）的查找，树结构适合多key查找（”范围查找“），lucene适合字符串的查找，我们在添加和更新的时候同时维护自己的内存数据库，最终杜绝表关联，老同学，还是先应急，把常用的表灌倒内存，如果真想项目好的话，改架构吧…

② 添加问题

或许你的Add操作还没有达到瓶颈这一步，如果真的达到了那就看情况来进行”表切分“，”数据库切分“吧，让用户的Add或者Update操作分流，虽然做起来很复杂，但是没办法，总比用户纠纷强吧，可对…

二：二叉查找树

正式切入主题，从上面的说明我们知道了二叉树非常适合于范围查找，关于树的基本定义，这里我就默认大家都知道，我就直接从查找树说起了。

1：定义

查找树的定义非常简单，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序。

2：树节点

为了具有通用性，我们定义成泛型模板，在每个结点中增加一个”数据附加域”。

public class BinaryNodeInteger{

/// 节点元素

private Long key;

private User value;

/// 左节点

private BinaryNodeInteger left;

/// 右节点

private BinaryNodeInteger right;

public BinaryNodeInteger(){

}

public BinaryNodeInteger(Long key,User value, BinaryNodeInteger left, BinaryNodeInteger right)

{

this.key = key;

this.value = value;

this.left = left;

this.right = right;

}

public Long getKey() {

return key;

}

public void setKey(Long key) {

this.key = key;

}

public BinaryNodeInteger getLeft() {

return left;

}

public void setLeft(BinaryNodeInteger left) {

this.left = left;

}

public BinaryNodeInteger getRight() {

return right;

}

public void setRight(BinaryNodeInteger right) {

this.right = right;

}

public User getValue() {

return value;

}

public void setValue(User value) {

this.value = value;

}

3：添加

根据查找树的性质我们可以很简单的写出Add的代码，一个一个的比呗，最终形成的效果图如下

这里存在一个“重复节点”的问题，比如说我在最后的树中再插入一个元素为15的结点，那么此时该怎么办，一般情况下，我们最好不要在树中再追加一个重复结点，而是在“重复节点”的附加域中进行”+1“操作。

/// 添加操作

public static BinaryNodeInteger Add(Long key,User value, BinaryNodeInteger tree){

if (tree == null)

tree = new BinaryNodeInteger(key,value, null, null);

BinaryNodeInteger tmpNode = new BinaryNodeInteger(key, value, null, null);

//左子树

if (key <= tree.getKey()){

if(tree.getLeft() == null){

tree.setLeft(tmpNode);

}else{

tree.left = Add(key,value, tree.getLeft());

}

}else{//右子树

if(tree.getRight() == null){

tree.setRight(tmpNode);

}else{

tree.right = Add(key,value, tree.getRight());

}

return tree;

}

4:范围查找

这个才是我们使用二叉树的最终目的，既然是范围查找，我们就知道了一个”min“和”max“，其实实现起来也很简单，

第一步：我们要在树中找到min元素，当然min元素可能不存在，但是我们可以找到min的上界，耗费时间为O(logn)。

第二步：从min开始我们中序遍历寻找max的下界。耗费时间为m。m也就是匹配到的个数。

最后时间复杂度为M+logN，要知道普通的查找需要O(N)的时间，比如在21亿的数据规模下，匹配的元素可能有30个，那么最后的结果也就是秒杀和几个小时甚至几天的巨大差异，后面我会做实验说明。

// 树的指定范围查找

public static List<User> SearchRange(Long min,Long max,List<User> result,BinaryNodeInteger tree){

if (tree == null)

return null;

if(result == null){

result = new ArrayList<User>();

}

//遍历左子树（寻找下界）

if (min < tree.getKey())

SearchRange(min, max,result,tree.getLeft());

//当前节点是否在选定范围内

if (min <= tree.getKey() && max >= tree.getKey()){

//等于这种情况

result.add(tree.getValue());

}

//遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）

if (min > tree.getKey() || max > tree.getKey())

SearchRange(min, max,result,tree.getRight());

return result;

}

5：删除

对于树来说，删除是最复杂的，主要考虑两种情况。

<1>单孩子的情况

这个比较简单，如果删除的节点有左孩子那就把左孩子顶上去，如果有右孩子就把右孩子顶上去，然后打完收工。

<2>左右都有孩子的情况。

首先可以这么想象，如果我们要删除一个数组的元素，那么我们在删除后会将其后面的一个元素顶到被删除的位置，如图

那么二叉树操作同样也是一样，我们根据”中序遍历“找到要删除结点的后一个结点，然后顶上去就行了，原理跟”数组”一样一样的。

同样这里也有一个注意的地方，在Add操作时，我们将重复元素的值追加到了“附加域”，那么在删除的时候，就可以先判断是

不是要“-1”操作而不是真正的删除节点，其实这里也就是“懒删除”，很有意思。

=================>>>>>>下面代码只是伪代码，具体实现可以自己研究写哦<<<<<<====================

/// 删除当前树中的节点

public BinaryNode<K, V> Remove(K key, V value, BinaryNode<K, V> tree){

if (tree == null)

return null;

//左子树

if (key.CompareTo(tree.key) < 0)

tree.left = Remove(key, value, tree.left);

//右子树

if (key.CompareTo(tree.key) > 0)

tree.right = Remove(key, value, tree.right);

/*相等的情况*/

if (key.CompareTo(tree.key) == 0){

//判断里面的HashSet是否有多值

if (tree.attach.Count > 1){

//实现惰性删除

tree.attach.Remove(value);

}else{

//有两个孩子的情况

if (tree.left != null && tree.right != null){

//根据二叉树的中顺遍历，需要找到”有子树“的最小节点

tree.key = FindMin(tree.right).key;

//删除右子树的指定元素

tree.right = Remove(key, value, tree.right);

}else{

//单个孩子的情况

tree = tree.left == null ? tree.right : tree.left;

}

return tree;

}

这样一个普通的二叉树就构建好了，接下来就可以写实现代码进行测试了。

具体代码如下：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

package com.goomoon.tree.BinaryTree;

import java.util.ArrayList;

import java.util.List;

public class BinaryNodeInteger{

/// 节点元素

private Long key;

private User value;

/// 左节点

private BinaryNodeInteger left;

/// 右节点

private BinaryNodeInteger right;

public BinaryNodeInteger(){

}

public BinaryNodeInteger(Long key,User value, BinaryNodeInteger left, BinaryNodeInteger right)

{

this.key = key;

this.value = value;

this.left = left;

this.right = right;

}

public Long getKey() {

return key;

}

public void setKey(Long key) {

this.key = key;

}

public BinaryNodeInteger getLeft() {

return left;

}

public void setLeft(BinaryNodeInteger left) {

this.left = left;

}

public BinaryNodeInteger getRight() {

return right;

}

public void setRight(BinaryNodeInteger right) {

this.right = right;

}

public User getValue() {

return value;

}

public void setValue(User value) {

this.value = value;

}

/// 添加操作

public static BinaryNodeInteger Add(Long key,User value, BinaryNodeInteger tree){

if (tree == null)

tree = new BinaryNodeInteger(key,value, null, null);

BinaryNodeInteger tmpNode = new BinaryNodeInteger(key, value, null, null);

//左子树

if (key <= tree.getKey()){

if(tree.getLeft() == null){

tree.setLeft(tmpNode);

}else{

tree.left = Add(key,value, tree.getLeft());

}

}else{//右子树

if(tree.getRight() == null){

tree.setRight(tmpNode);

}else{

tree.right = Add(key,value, tree.getRight());

}

return tree;

}

// 树的指定范围查找

public static List<User> SearchRange(Long min,Long max,List<User> result,BinaryNodeInteger tree){

if (tree == null)

return null;

if(result == null){

result = new ArrayList<User>();

}

//遍历左子树（寻找下界）

if (min < tree.getKey())

SearchRange(min, max,result,tree.getLeft());

//当前节点是否在选定范围内

if (min <= tree.getKey() && max >= tree.getKey()){

//等于这种情况

result.add(tree.getValue());

}

//遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）

if (min > tree.getKey() || max > tree.getKey())

SearchRange(min, max,result,tree.getRight());

return result;

}

public static void main(String[] args) {

int count = 5000000;

BinaryNodeInteger node = null;

System.out.println("Begin build Tree contruct...");

long s1 = System.currentTimeMillis();

while(count > 0){

long userId = (long)(Math.random() * 1000000000);

String userName = "用户"+userId;

int age = (int)(Math.random() * 60);

int sexInt = (int)(Math.random() * 2);

String sex = (sexInt == 1?"男":"女");

User user = new User(userId, userName, age, sex);

node = BinaryNodeInteger.Add(userId, user, node);

count--;

}

long s2 = System.currentTimeMillis();

System.out.println("End build Tree contruct...cost time:"+(s2-s1));

System.out.println("Begin search Tree...");

long s3 = System.currentTimeMillis();

List<User> userList = BinaryNodeInteger.SearchRange(2000000L, 2500000L, null, node);

long s4 = System.currentTimeMillis();

System.out.println("End search Tree...size:"+userList.size()+"...cost time:"+(s4-s3));

// for(User _u : userList){

// System.out.println(_u);

// }

}

经过测试：

可以看到，构建500万的树节点，需要17秒的时间，但是查询起来花了3毫秒，同样用另外一种构建一个HashMap的结构，然后从Map里取值，所花的时间节点图如下：

经过测试，这个普通二叉树比Map结构着实快上不少，从数量级来说还不是非常明显，为什么说不是非常明显，这是因为普通的查找树的时间复杂度不是严格的log(N)，在最坏的情况下会出现“链表”的形式，复杂度退化到O(N)

不过总会有解决办法的，下一篇我们继续聊如何旋转，保持最坏复杂度在O(logN)。

==============================================>>>>>>>>>

文章部分内容摘自 http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html

转载请注明：刘召考的博客 » 刨根问底之树结构_二叉树

一：场景

1：现状

2：我个人的提供解决方案

① 读取问题

② 添加问题

二：二叉查找树

1：定义

2：树节点

3：添加

4:范围查找

5：删除

<1>单孩子的情况

<2>左右都有孩子的情况。

与本文相关的文章