java - 改变多维树的 "perspective"

Question

|-- Car                                |-- Green     
|   |-- Audi                           |   |-- Car        
|   |   |-- Green                      |   |   `-- Audi           
|   |   |-- Blue                       |   `-- Bike             
|   |   `-- Red                        |       `-- BMW  
|   `-- BMW                            |-- Blue     
|       |-- Red                        |   `-- Car         
|       `-- Yellow     ==========>     |       `-- Audi     ==========>     etc.                 
`-- Bike                               |-- Red         
    |-- BMW                            |   |-- Car    
    |   |-- Yellow                     |   |   |-- Audi 
    |   |-- Blue                       |   |   `-- BMW
    |   `-- Green                      |   `-- Bike       
    `-- Honda                          |       `-- Honda       
        |-- Red                        `-- Yellow          
        `-- Yellow                         |-- Car         
                                           |   `-- BMW
                                           `-- Bike
                                               |-- BMW
                                               `-- Honda

我想在树构建器中以通用方式实现多个“透视图”。

这棵树有 6 种可能的排列方式，我只画了其中 2 种。

我尝试了什么:

• 我使用的是通用树结构，其中每个节点都知道其父节点和子节点，并且都有有效载荷。
• 类:TreeBuilder、AbstractNode、VehicleNode、ColorNode、MakerNode、和另一个定义级别顺序的有序枚举列表:BY_VEHICLE、BY_COLOR、BY_MAKER - 您可以切换它们以获得所需的视角
• 遍历枚举列表，收集特定于该枚举值的所有实体(汽车、制造商、颜色)作为对象等。使用工厂方法，使用 enumValue 创建节点，同时传递树构建器和 parentEnumValue(对于顶级，父枚举值为 NULL)。
• child 有一个 getParentMember_Internal，它根据 parentEnumValue 获取正确的父级(通过使用包含所有数据映射的 treeBuilder)<
• 在我提到的之前的迭代中，使用结果节点的父对象，我们可以搜索树并查看它是哪个节点(记住层次是自上而下创建的，所以父对象已经存在)

为什么不起作用:

• 在搜索正确的 parent 时，树中可能有多个实例，因此我们也不得不查看祖 parent 。
• 此外，分支可能会重复(见第二棵树)

我在问什么:

• 这种树/算法是否有特定的命名？我想不出在 Google 中使用的英文术语。
• 它与“K-D 树”有什么关系吗？
• 有没有通用的方法来做这类事情？

---

编辑 1 @Andreas

树中只有 3 个可能的实体:Vehicle、Color、Maker。没有“车型”。树中的所有有效载荷都是这三个的子类。

我称它们为“有效负载”，因为每个对象都包装在一个 AbstractNode 子类(它是树结构的一部分)中，以将数据与表示层分开。示例:VehicleNode 有一个 Vehicle 负载。

由于实体之间独立，所以层次可能是隐藏的。 这将是一个有效的案例:

|-- Green
|   |-- Audi
|   `-- BMW
|-- Blue
|   `-- Audi
|-- Red
|   |-- Audi
|   |-- BMW
|   `-- Honda
`-- Yellow
    |-- BMW (notice this doesn't appear twice under 'yellow', like in the second tree above)
    `-- Honda

Answer 1

在 SQL 中，这就像一个 Star Schema , 在数据仓库数据库中用于 Online Analytical Processing (OLAP) .

在您的情况下，这将是一个事实表 Vehicle 和 3 个维度(Type、Brand、Color).

我建议将车辆保存在列表中，并从列表中构建 6 棵树/索引，而不是尝试将一棵树转换为另一棵树。

一个完全类型化的实现可能是定义一个通用的抽象树:

public abstract class Tree<F, D1, D2, D3> {
    protected Tree(List<F> facts) {
        // code here using getDimensionN() to build tree
    }
    protected abstract D1 getDimension1(F fact);
    protected abstract D2 getDimension2(F fact);
    protected abstract D3 getDimension3(F fact);
    public List<F> get(D1 dimension1) {
        // code here
    }
    public List<F> get(D1 dimension1, D2 dimension2) {
        // code here
    }
    public List<F> get(D1 dimension1, D2 dimension2, D3 dimension3) {
        // code here
    }
    // other public accessor methods here
}

然后您可以使用如下代码构造一棵特定的树:

List<F> facts = ...;
Tree<Vehicle, Type, Brand, Color> typeBrandColorTree = new Tree<Vehicle, Type, Brand, Color>(facts) {
    protected Type getDimension1(Vehicle vehicle) { return vehicle.getType(); }
    protected Brand getDimension2(Vehicle vehicle) { return vehicle.getBrand(); }
    protected Color getDimension3(Vehicle vehicle) { return vehicle.getColor(); }
};

// Use of tree
List<Vehicle> audiCars = typeBrandColorTree.get(Type.CAR, Brand.AUDI);

---

更新

Star Schema 可能不适合您的特定问题，因此这里更多的是关于 Star Schemas 的信息。让我用一个例子来说明事实可能是什么。

事实可能是车辆的销售，其中跟踪的销售统计信息包括:

• 类型(汽车、自行车)
• 品牌(奥迪、宝马、本田)
• 颜色(绿色、蓝色、红色、黄色)
• 日期
• 价格

然后可以使用树/索引来回答如下问题:

• 显示奥迪汽车的销量。
• 卖出了多少辆蓝色自行车？
• 按品牌列出总销售额。

为了更快地访问，树节点甚至可以有预先聚合的值，如 Count 和 TotalPrice，这样你就不需要迭代所有的事实来获得你的答案。

主要用于海量数据集(比如10年的全国销售数据)，帮助管理者按需快速获取各种汇总统计数据。因此，术语“在线分析处理”。