Java 树构建最快算法

项目中经常会用到树构建，比如地区树型数据构建，测试中一个省到街道级别的地区数据，共有13828条，普通的递归构建树算法计算次数接近2亿次，内存暂用高，CPU占用高，耗时久，一般在5秒左右，数据量上万后基本无法使用。

思路：

普通树构建算法都是通过递归遍历所有节点来找出当前节点的子节点实现的，计算次数成指数级增长，数据量达到上万条效率就已经不能满足需求了，可以考虑利用LinkedHashMap来保存所有节点，查找过程用LinkedHashMap来实现，经过实践，运算次数从2亿次减少到了2万7千多次，耗时从5秒减少到了450ms左右，效率提升了10倍有余。

算法描述：

1、把所有数据放入LinkedHashMap中

2、然后遍历LinkedHashMap中的所有值，并从该LinkedHashMap中查找当前节点的父节点，把当前节点加入父节点的孩子中

3、从LinkedHashMap中将已经加入父节点子集中的节点移除掉，并将移除节点后的LinkedHashMap作为下一个递归的参数继续调用

4、直到LinkedHashMap中所有的节点都再找不到父节点为止，这些剩下的根节点就是一棵构造好的树

优点：时间复杂度和空间复杂度低，效率高速度快，处理大数据量效果好

import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * @description: 树构造工厂
 * @author: YinHeng
 * @date: 2020/11/6 16:27
 **/
public class TreeFactory<K, T extends TreeNode<K, T>> implements Serializable {

    /**
     * 递归向上查找法
     *
     * @param nodeList
     * @return
     */
    public List<T> buildTree(List<T> nodeList) {
        Map<K, T> nodeMap = new LinkedHashMap<>(16);
        for (T node : nodeList) {
            nodeMap.put(node.getId(), node);
        }
        return buildTree(nodeMap);
    }

    /**
     * 递归向上查找父节点
     *
     * @param nodeMap
     * @return
     */
    public List<T> buildTree(Map<K, T> nodeMap) {
        return findParent(nodeMap);
    }

    /**
     * 利用HashMap高效率递归向上查找，并每次减少遍历节点数
     *
     * @param nodeMap
     * @return
     */
    public List<T> findParent(Map<K, T> nodeMap) {

        //该循环结束后可以移除掉的节点
        List<K> removeNodes = new ArrayList<>();

        for (T node : nodeMap.values()) {
            T pNode = nodeMap.get(node.getPid());
            //如果当前节点的父节点存在，则将当前节点添加到父节点的子节点，并在循环结束后从Map中删除当前节点
            if (pNode != null && !pNode.getId().equals(node.getId())) {
                pNode.addChild(node);
                removeNodes.add(node.getId());
            }
        }
        //删除已经找到父节点的节点
        removeNodes.forEach(nodeMap::remove);

        return new ArrayList<>(nodeMap.values());
    }


}

import java.util.List;

/**
 * 树节点接口
 *
 * @author YinHeng
 * @date 2021/5/28 10:34
 */
public interface TreeNode<K, T extends TreeNode<K, T>> {
    /**
     * 设置节点id
     *
     * @param id
     */
    void setId(K id);


    /**
     * 获取节点id
     *
     * @return 节点id
     * @author xuyuxiang
     * @date 2020/7/9 18:36
     */
    K getId();

    /**
     * 获取节点父id
     *
     * @return 节点父id
     * @author xuyuxiang
     * @date 2020/7/9 18:36
     */
    K getPid();

    /**
     * 设置父节点
     *
     * @param pid
     */
    void setPid(K pid);

    /**
     * 获取孩子
     *
     * @return
     */
    List<T> getChildren();

    /**
     * 设置children
     *
     * @param children 子节点集合
     * @author xuyuxiang
     * @date 2020/7/9 18:36
     */
    void setChildren(List<T> children);

    /**
     * 添加子节点
     *
     * @param node
     */
    void addChild(T node);
}

总结：

普通的递归构建中，每次递归查找子节点或父节点都需要遍历整个集合，效率低下，LinkedHashMap底层是由红黑树组成，数据量越大，查找效率越明显，并且每个节点保存了上一条数据和下一条数据的地址，保证了原始数据的顺序。