比较高度平衡树和重量平衡树
Compare height balanced tree to weight balanced tree
我在考虑高度平衡树胜过重量平衡树的场景。以下是我经过大量搜索仍无法找到答案的问题：
这两棵树的时间和 space 复杂度都相似，那么为什么我更喜欢一个呢？
在某些应用中，重量平衡树优于高度平衡树吗？
如果我想知道这些给定树中的哪一个可以满足我的需要，我应该在我的 CRUD 查询模式中观察哪些特征？
一棵高度平衡的树改善了最坏情况下的查找时间（对于二叉树，它总是以 log2(n) 为界），但代价是使典型情况下的查找次数减少大约一半（大约一半）的节点将处于最大深度）。
如果您的权重与查找频率相关，权重平衡的树将改善平均查找时间，但代价是使最坏情况变得更高（更频繁请求的项目具有更高的权重，并且会因此往往在较浅的树中，成本是较不频繁请求的项目的较深树）。
找出最佳效果的最佳方法是进行测量。如果您可以收集一些有代表性的查询流量，您可以简单地构建一个测试平台，在其中计算树操作（插入、跟随子指针，...）并针对高度平衡和重量平衡重放您的固定查询树。但作为一般规则，高度平衡的树在数据集中的请求频率越均匀越好，它越倾斜，您从权重平衡的树中获得的优势就越大。
我在考虑高度平衡树胜过重量平衡树的场景。以下是我经过大量搜索仍无法找到答案的问题：
这两棵树的时间和 space 复杂度都相似，那么为什么我更喜欢一个呢？
在某些应用中，重量平衡树优于高度平衡树吗？
如果我想知道这些给定树中的哪一个可以满足我的需要，我应该在我的 CRUD 查询模式中观察哪些特征？
一棵高度平衡的树改善了最坏情况下的查找时间（对于二叉树，它总是以 log2(n) 为界），但代价是使典型情况下的查找次数减少大约一半（大约一半）的节点将处于最大深度）。
如果您的权重与查找频率相关，权重平衡的树将改善平均查找时间，但代价是使最坏情况变得更高（更频繁请求的项目具有更高的权重，并且会因此往往在较浅的树中，成本是较不频繁请求的项目的较深树）。
找出最佳效果的最佳方法是进行测量。如果您可以收集一些有代表性的查询流量，您可以简单地构建一个测试平台，在其中计算树操作（插入、跟随子指针，...）并针对高度平衡和重量平衡重放您的固定查询树。但作为一般规则，高度平衡的树在数据集中的请求频率越均匀越好，它越倾斜，您从权重平衡的树中获得的优势就越大。