介绍 (Introduction)
 
 
 Power BI is enriched with many useful visualizations and helps to represent data in various forms. We have explored many use cases of PowerBI in SQLShack articles. 
 
 Power BI丰富了许多有用的可视化效果，并有助于表示各种形式的数据。 我们在SQLShack文章中探讨了PowerBI的许多用例。 
 
 
 Microsoft regularly provides updates to Power BI desktop and comes up with new enhancements, features. You should always work with the latest version. In this article, I am using the December 2019 Power BI desktop version. 
 
 
 Microsoft定期提供Power BI桌面的更新，并提供新的增强功能。 您应该始终使用最新版本。 在本文中，我正在使用2019年12月的Power BI桌面版本。 
 
 
 You can check the Power BI desktop from Help->About. 
 

  
 
 
 
 您可以从“ 帮助”->“关于”中检查Power BI桌面。 
 
 
 In November Power BI Desktop release, we have a new decomposition tree visual with the capability of artificial intelligence (AI). Yes, it is having inbuilt AI functionality and helps you to drill down the data. 
 
 在Power BI Desktop的11月发行版中，我们有了一个具有人工智能（AI）功能的新的分解树视图。 是的，它具有内置的AI功能，可以帮助您向下钻取数据。 
 
 
 Power BI桌面中的分解树可视化 (Decomposition Tree Visual in Power BI desktop)
 
 
 We can use the decomposition tree to visualize data in multiple dimensions. We can drill down and analyze data in the hierarchy for a quick analysis. Its’s artificial intelligence (AI) capability enables you to find the next dimension data as per defined criteria. We breakdown (decompose) data into individual categories and determine the high, low values using AI functions in this decomposition visual. 
 
 
 我们可以使用分解树来可视化多维数据。 我们可以向下钻取和分析层次结构中的数据以进行快速分析。 它的人工智能（AI）功能使您能够根据定义的条件查找下一个尺寸数据。 我们将数据分解（分解）为单独的类别，并在此分解视图中使用AI函数确定高值和低值。 
 
 
 It is a preview feature as of now and does not automatically show in the visualization pane. 
 
 
 到目前为止，它是预览功能，不会自动显示在可视化窗格中。 
 
 
 Launch Power BI dashboard and click on File -> Options and settings -> Options: 
 
 
 启动Power BI仪表板，然后单击文件 -> 选项和设置 -> 选项： 
 
 
 
 

  
 
 
 
 It opens an options page with different configurations. Navigate to the Preview features tab, and you see the checkbox for the Decomposition tree visual feature: 
 
 
 它会打开一个具有不同配置的选项页面。 导航到“ 预览功能”选项卡，然后看到“ 分解树”视觉功能的复选框： 
 
 
 
 

  
 
 
 
 Put a check on the Decomposition tree visual feature and click the OK button: 
 
 
 选中“ 分解树”视觉功能，然后单击“确定”按钮： 
 
 
 
 

  
 
 
 
 Once you click the OK button, it pops us a message that Power I Desktop restart will enable this preview feature: 
 
 
 单击确定按钮后，它会向我们弹出一条消息，即重启Power I Desktop将启用此预览功能： 
 
 
 
 

  
 
 
 
 After the restart, you get the Decomposition tree visualization icon as shown below: 
 
 
 重新启动后，您将获得“ 分解树”可视化图标，如下所示： 
 
 
 
 

  
 
 
 
 Click on this visual, and it opens the visual layout. You can adjust the layout for a better visual. It consists of two parts – Visual shape and a bulb that represents artificial intelligence: 
 
 
 单击此视觉效果，它将打开视觉效果布局。 您可以调整布局以获得更好的视觉效果。 它由两部分组成-视觉形状和代表人工智能的灯泡： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 Decomposition tree requires two inputs: 
 
 
 分解树需要两个输入： 
 
 
Analyze:  In this input, we specify a column for that you require a breakdown of the tree 分析：在此输入中，我们指定一列，您需要对树进行细分 
Explain by: We can add multiple dimensions in this column. We can analyze tree further using these breakdown columns 解释：我们可以在此列中添加多个维度。 我们可以使用这些细分列进一步分析树 
 
 We will use the AdventureWorksDW2017 sample database for this demonstration. If you do not have this database, visit GitHub and download the backup copy of this database. 
 
 
 我们将使用AdventureWorksDW2017示例数据库进行此演示。 如果您没有此数据库，请访问GitHub并下载该数据库的备份副本。 
 
 
 Click on the Get Data button in the Home tab and choose the data source as SQL Server: 
 
 
 单击“ 主页”选项卡中的“ 获取数据”按钮，然后选择数据源作为SQL Server： 
 
 
 
 

  
 
 
 
 It opens a pop-up window, and you can specify the SQL Server instance, database details. We can specify the Data Connectivity mode, either Import or DirectQuery: 
 
 
 它打开一个弹出窗口，您可以指定SQL Server实例，数据库详细信息。 我们可以指定数据连接模式，即Import或DirectQuery ： 
 
 
 
 

  
 
 
 
 Click the OK button and specify the credentials. We can use either Windows credentials (option – Use my current credentials) or specify alternate credentials: 
 
 
 单击确定按钮，然后指定凭据。 我们可以使用Windows凭据（选项–使用我当前的凭据），也可以指定备用凭据： 
 
 
 
 

  
 
 
 
 You get warning message of unencrypted connection: 
 
 
 您收到未加密连接的警告消息： 
 
 
 
 

  
 
 
 
 Click the OK button to ignore this. You get a list of database objects after authentication. Select the appropriate object and load it. In this article, we use vTargetMail view of AdventureWorksDW2017 database: 
 
 
 单击确定按钮忽略此。 身份验证后，您将获得数据库对象的列表。 选择适当的对象并加载它。 在本文中，我们使用AdventureWorksDW2017数据库的vTargetMail视图： 
 
 
 
 

  
 
 
 
 It creates connections and loads data, as shown below: 
 
 
 它创建连接并加载数据，如下所示： 
 
 
 
 

  
 
 
 
 Once the data load is complete, we get the fields (output columns) in the field section of Power BI Desktop: 
 
 
 数据加载完成后，我们将在Power BI Desktop的字段部分中获得字段（输出列）： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 Now, we need to drag the fields into Analyze and Explain by columns for the decomposition tree. First, drag the [YearlyIncome] field into the Analyze section. It shows the sum of the [YearlyIncome] into the visual: 
 
 
 现在，我们需要将字段拖到分解树的“ 分析”和“ 按列解释”中 。 首先，将[YearlyIncome]字段拖到“ Analyze”部分中。 它显示[YearlyIncome]的总和到视觉中： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 By default, we get the sum for the column in the Analyze column. We can change it as per requirement such as average, minimum, maximum, variance, median, standard deviation. For this article, we can go with the default option sum: 
 
 
 默认情况下，我们获得“ 分析 ”列中该列的总和。 我们可以根据要求进行更改，例如平均值，最小值，最大值，方差，中位数，标准偏差。 对于本文，我们可以使用默认选项sum： 
 
 
 
 

  
 
 
 
 The next requirement is to add the fields to Explain by section. We can add multiple fields in this section. Let’s drag few columns – BikeBuyer, MaritialStatus, NumberCarsOwned, YearlyIncome and CommuteDistance and Region. 
 
 
 下一个要求是将字段添加到“ 按部分解释” 。 我们可以在本节中添加多个字段。 让我们拖几列- BikeBuyer，MaritialStatus，NumberCarsOwned，YearlyIncome和CommuteDistance和地区 。 
 
 
 We can drag the fields in any order. The decomposition chart does not get any influence on the order of columns: 
 
 
 我们可以按任意顺序拖动字段。 分解图对列顺序没有任何影响： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 In the above screenshot, we can see that we have selected the fields in explain by column, but it does not show in the decomposition tree visual. 
 
 
 在上面的屏幕截图中，我们可以看到我们已经在“按列解释”中选择了字段，但是它没有显示在分解树视图中。 
 
 
 You can notice a plus (+) symbol on the sum of [YearlyIncome] column in the chart: 
 
 
 您可以在图表的[YearlyIncome]列的总和上看到一个加号（+）： 
 
 
 
 

  
 
 
 
 Click on plus (+) icon, and you get columns that we drag into the explain by section. You also get the column order the same as well. If we want to change the order of the columns in which they should appear in the chart, drag those columns in the same order in the explain by section: 
 
 
 单击加号（+）图标，您将获得我们拖入“按说明”部分的列。 您也将获得相同的列顺序。 如果我们要更改列在图表中应显示的顺序，请在“解释依据”部分中以相同的顺序拖动这些列： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 Now, from the chart column, click on any column for adding details in the chart. Let’s click on the Region, and it adds regions into the chart. 
 
 
 现在，在图表列中，单击任意列以在图表中添加详细信息。 让我们单击Region ，它将区域添加到图表中。 
 
 
 
 

  
 
 
 
 Now, to add further details, click on plus (+) sign on the region and it again populates rest of the fields list: 
 
 
 现在，要添加更多详细信息，请单击该区域上的加号（+），然后再次填充其余字段列表： 
 
 
 
 

  
 
 
 Click on the [NumberCarsOwned], and you get it in the chart. In the below chart, you can see [NumberCarsOwned] for North America: 
 
 
 单击[NumberCarsOwned] ，然后将其显示在图表中。 在下面的图表中，您可以看到北美的[NumberCarsOwned] ： 
 
 
 
 

  
 
 
 
 Click on Europe, and you get details of it: 
 
 
 单击欧洲，您将获得详细信息： 
 
 
 
 

  
 
 
 
 Similarly, we can add further details to the decomposition tree: 
 
 
 同样，我们可以向分解树添加更多细节： 
 
 
 
 

  
 
 
 
 We added further details for [MaritialStatus] in the decomposition tree: 
 
 
 我们在分解树中添加了[MaritialStatus]的更多详细信息： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 Once you click on any tree path, it highlights that particular path and fades color for others, as shown below: 
 
 
 单击任何树路径后，它将突出显示该特定路径，并为其他路径淡化颜色，如下所示： 
 
 
 
 

  
 
 
 
 In case we do not want any particular level in the tree, we can remove it as well. For example, let’s say we do not want [CommuteDistance] section, then click on cross (x) on from the top layer: 
 
 
 如果我们不需要树中的任何特定级别，也可以将其删除。 例如，假设我们不想要[CommuteDistance]部分，然后从顶层单击十字（x）： 
 
 
 
 

  
 
 
 
 It removes the field, and the decomposition tree automatically relates to the next level that is [MaritialStatus] in my example: 
 
 
 它删除该字段，并且分解树自动与下一个级别相关，在我的示例中为[MaritialStatus] ： 
 
 
 
 

  
 
 
 Power BI Desktop中的人工智能分解树拆分 (Artificial Intelligence decomposition tree split in Power BI Desktop)
 
 
 As highlighted earlier, Microsoft added artificial intelligence (AI) as well in the decomposition tree visual. Once we click on plus (+) symbol, we get a list of columns along with two fields having bulb icon as well as shown below: 
 
 
 如前所述，Microsoft在分解树视图中还添加了人工智能（AI）。 单击加号（+）后，我们将获得一列列表以及两个带有灯泡图标的字段，如下所示： 
 
 
 
 

  
 
 
 
 Let’s click on the high value and view the visual. It adds a new split [BikeBuyer] along with a bulb icon indicating that it is an AI split: 
 
 
 让我们单击较高的值并查看视觉效果。 它将添加一个新的拆分[BikeBuyer]以及一个灯泡图标，指示它是一个AI拆分： 
 
 
 
 

  
 
 
 
 You might think why it added this column into the decomposition tree. It gives you an answer for it as well in the visual. Hover your mouse to the bulb icon, and you get the answer: 
 
 
 您可能会想为什么将此列添加到分解树中。 它在视觉上也为您提供了答案。 将鼠标悬停在灯泡图标上，您会得到答案： 
 
 
 
 

  
 
 
 
 Our decomposition tree starting point is [YearlyIncome]. Once we use AI split in the tree, it finds the way to find out the highest [YearlyIncome] with available elements. 
 
 
 我们的分解树的起点是[YearlyIncome] 。 一旦我们在树中使用AI split，它就会找到找出具有可用元素的最高[YearlyIncome]的方法 。 
 
 
 Now, add another column [Age] into explain by section and remove the [YearlyIncome]. Let’s add another high value (AI) split from the [BikeBuyer] AI column: 
 
 
 现在，在“说明”部分中添加另一列[年龄]并删除[YearlyIncome] 。   让我们从[BikeBuyer] AI列中添加另一个高价值（AI）： 
 
 
 
 

  
 
 
 
 Once we hover mouse on bulb icon for Age, we get the answer of this AI split. [YearlyIncome] is highest when Age is 38: 
 
 
 一旦将鼠标悬停在Age的灯泡图标上，我们就会得到此AI拆分的答案。 [YearlyIncome]是最高时年龄是38： 
 
 
 
 

  
 
 
 
 Now, remove this Age AI split and click on Low Value field. It automatically checks for the lowest yearly income based on Age: 
 
 
 现在，删除此年龄 AI拆分，然后单击“ 低值”字段。 它会根据年龄自动检查最低的年收入： 
 
 
 
 

  
 
 
 
 It dynamically calculates the value for the selections. For example, once we change the selection to the Europe region, we can see the lowest yearly income when Age is 66: 
 
 
 它动态计算选择的值。 例如，一旦将选择范围更改为欧洲地区，则可以看到年龄为66岁时的最低年收入： 
 
 
 
 

  
 
 
 人工智能分析类型 (Artificial intelligence Analysis type)
 
 
 By default, the Decomposition tree analyzes the AI value mode as Absolute. We can view it from the chart format options: 
 
 
 默认情况下，分解树将AI值模式分析为Absolute 。 我们可以从图表格式选项中查看它： 
 
 
 
 

  
 
 
 
 
 
  
 
 
 Let’s change the AI split mode from Absolute to Relative. It changes the AI split in the decomposition tree. You get the answer of the calculation – YearlyIncome is noticeably high when Age is 59: 
 
 
 让我们将AI拆分模式从绝对更改为相对 。 它更改了分解树中的AI拆分。 您得到了计算的答案–当年龄为59岁时，年收入很高： 
 
 
 
 

  
 
 
 
 In the Relative mode, add a new high value AI column, and you see that it adds the Age column as shown below: 
 
 
 在相对模式下，添加一个新的高价值AI列，您会看到它添加了Age列，如下所示： 
 
 
 
 

  
 
 
 
 You can see the answer- YearlyIncome is noticeably high when BikeBuyer is 0. You can compare this with the absolute AI mode in which we get the same calculations at first place. You should use the required AI mode as per your requirements. We can add high value and low value in the same decomposition tree. As shown below, we added another low value AI split: 
 
 
 您可以看到答案 -BikeBuyer为0时， YearlyIncome很高。您可以将其与绝对AI模式进行比较，在绝对AI模式下，我们首先获得相同的计算结果。 您应该根据需要使用所需的AI模式。 我们可以在同一分解树中添加高值和低值。 如下所示，我们添加了另一个低值AI拆分： 
 
 
 
 

  
 
 
 Power BI Desktop中分解树的锁定行为 (Locking behavior for decomposition tree in Power BI Desktop)
 
 
 You can notice a small lock icon in the report. By default, the lock is opened for all levels: 
 
 
 您会在报告中注意到一个小的锁定图标。 默认情况下，将为所有级别打开锁： 
 
 
 
 

  
 
 
 
 What is the lock in the decomposition tree? Power BI Desktop allows the content creator to lock the level so that the user cannot remove it. Suppose we want to lock first two levels of the tree, click on the open lock icon and it changes to lock as shown below: 
 
 
 分解树中的锁是什么？ Power BI Desktop允许内容创建者锁定级别，以便用户无法删除它。 假设我们要锁定树的前两个级别，请单击打开锁定图标，它将变为锁定，如下所示： 
 
 
 
 

  
 
 
 
 Once we lock any level, users do not get any option to remove that level. You do not get a cross (x) icon to remove the level. 
 
 
 一旦我们锁定了任何级别，用户就没有任何选择来删除该级别。 您没有得到一个十字（x）图标来删除该级别。 
 
 
 We can lock many levels, but suppose we lock level 4; then, it automatically locks the previous level for you. 
 
 
 我们可以锁定许多级别，但是假设我们锁定了4级。 然后，它会自动为您锁定上一个级别。 
 
 
 For example, in the following screenshot, we have all the lock levels open: 
 
 
 例如，在以下屏幕截图中，我们打开了所有锁定级别： 
 
 
 
 

  
 
 
 
 Let’s lock level for [CommuteDistance] and notice that all previous levels locked automatically: 
 
 
 让我们锁定[CommuteDistance]的级别，并注意所有先前的级别都会自动锁定： 
 
 
 
 

  
 
 
 Power BI Desktop中分解树的限制 (Limitations of the decomposition tree in Power BI Desktop)
 
 
 We can have a maximum of 50 levels in a decomposition tree 
 分解树中最多可以包含50个级别 
 It supports maximum 5000 data points at one time in the tree 
 在树中一次最多支持5000个数据点 
 It does not support On-premises Analysis Services, Power BI Report Server, Direct Query, Azure Analysis Services 
 它不支持本地分析服务，Power BI报表服务器，直接查询，Azure分析服务 
 We cannot use features Q&A, Power BI Mobile, Show Data functionality, and Pinning to dashboard with the decomposition tree 
 我们无法使用功能Q＆A，Power BI Mobile，显示数据功能以及通过分解树固定到仪表板 
 It is a preview feature while writing this article and it might have few feature changes in the upcoming releases of Power BI Dashboard 
 它是撰写本文时的预览功能，在以后的Power BI Dashboard版本中可能没有多少功能更改 
 
 结论 (Conclusion)
 
 
 In this article, we explored the useful decomposition tree and its useful artificial intelligence (AI) features. It is an excellent visual for breakdown data into certain levels and performs root cause analysis. 
 
 
 在本文中，我们探索了有用的分解树及其有用的人工智能（AI）功能。 它是将故障数据划分为一定级别并执行根本原因分析的绝佳视觉效果。 
 
 

  
翻译自: https://www.sqlshack.com/the-decomposition-tree-in-power-bi-desktop/
 

 1.引言
 
 渐进明细是项目的特点，但这并不意味着不需要计划。没有计划或者是随意的不负责任的计划的项目是一种无法控制的项目。在软件高技术行业，日新月异是主要特点，因此计划的制定需要在一定条件的限制和假设之下采用渐近明细的方式进行不断完善。例如对于较为大型的软件开发项目的工作分解结构WBS可采用二次WBS方法，即根据总体阶段划分的总体WBS和专门针对系统设计或编码阶段的二次WBS。这其中部分的原因是需求的颗粒度在一开始往往是比较粗的，因此根据功能点对于整体项目规模的估计误差范围也是比较大的。更为重要的原因是，需求往往不是编码工作分解的准确依据，因为一个需求的功能点可能对应多个代码模块，而多个需求的功能点也可能只对应一个或少数代码模块，同时还有软件复用等因素要考虑，因此只有在需求分析完成以后才能准确地得到系统设计或编码阶段的二次WBS，根据代码模块的合理划分而得出的二次WBS才能在系统设计、编码阶段乃至测试阶段起到有效把握和控制进度的作用。
 
  
 
 2.基本概念 
 
 WorkBreakdownStructure（WBS）工作分解结构：对应当由项目团队执行以便实现项目目标，并创造必要的可交付成果工作，按可交付成果所做的层次分解。WBS将项目的整个范围组织在一起并加以明确。每向下分解一个层次，就意味着项目工作的定义深入了一步。WBS最终分解为工作细目。WBS的层次结构以可交付成果为对象，包括内部和外部可交付成果。（2004年版PMBOK指南）
 
 WorkPackage（工作细目，也翻译为工作任务包），工作细目包括为完成该工作细目可交付成果或项目工作组成部分而必需的计划活动和进度里程碑。（2004年版PMBOK指南）
 
 ControlAcｃｏｕｎｔ（控制账目，CA），是综合范围、预算、实际费用和进度，并对绩效进行测量的管理控制点，控制账目设置在工作分解结构（在选定水平上的具体组成部分）的事先选定的管理点上。每一个控制账目都可以包含一个或多个的工作细目，但是每一个工作细目只可以在同一个控制账目相联系。（2004年版PMBOK指南）
 
  
 
 3.对WBS的理解
 
 从以上解释，我们得出如下结论，WBS是将项目加以定义，明确项目工作任务的。由此可见，WBS在项目管理的重要地位，所以“没有WBS，就没有项目管理”。
 
 对于WBS定义的理解，我个人认为应在以下两方面重点加以理解：
 
  
 
 第一方面，就是WBS的单元，即WBS层次结构的对象，它是以“Deliverables（可交付成果）”为分解导向，而不是以“ScheduleActivity（计划活动）”为分解导向。
 
 WBS的最底层次为WorkPackage（工作细目），工作细目包括为完成该工作细目可交付成果或项目工作组成部分而必需的计划活动和进度里程碑。
 
 为什么WBS的最底层次不是ScheduleActivity（计划活动）而是WorkPackage（工作细目）呢？
 
 首先WBS是作为项目范围管理的工具、技术，项目范围管理关注点是项目的组成部分，它面向的是可交付成果，而不是过程。
 
 其次WBS定义的是项目及其组成部分，是ScheduleActivity（计划活动）定义的依据，而不是去定义ScheduleActivity（计划活动）；
 
 第三ScheduleActivity（计划活动）是项目进度表的单个组成部分，不是WBS的组成部分。对于这一点，很多人理解上可能有困难。因为，习惯说法是活动是由各项具体工作构成的，而上面的定义我们从字面上看的习惯说法与PMBOK的定义正好相反，但是从本质上去理解两者应该是相同的，只是说法不同。因为在项目管理尚未引进中国以前，我们把活动等同于项目。
 
  
 
  
 
 第二方面，就是WBS的结构，WBS的结构包含了科学的逻辑结构，而不是单个的、离散的、在时间顺序上不连续的成果的描述结构。
 
 WBS的结构是由逻辑推演而成的，通过层层的包含关系，非常严谨。结构化是WBS的一大重要特性，WBS的逻辑结构错误会直接导致项目实施过程发生错误，严重的会带来项目的失败。
 
 “做正确的事，正确地做事”是我们从事项目管理的一句格言，WBS首先解决的就是“做正确的事”问题，只有明确了“做正确的事”，“正确地做事”才有基础，所以我们说WBS是现代项目管理的重要基石。 
 
  
 
 4.WBS的主要用途 
 
 WBS是一个描述思路的规划和设计工具。它帮助项目经理和项目团队确定和有效地管理项目的工作。
 
 WBS是一个清晰地表示各项目工作之间的相互联系的结构设计工具。
 
 WBS是一个展现项目全貌，详细说明为完成项目所必须完成的各项工作的计划工具。
 
 WBS定义了里程碑事件，可以向高级管理层和客户报告项目完成情况，作为项目状况的报告工具。
 
  
 
 5.WBS的作用 
 
 防止遗漏项目的可交付成果。
 
 帮助项目经理关注项目目标和澄清职责。
 
 建立可视化的项目可交付成果，以便估算工作量和分配工作。
 
 帮助改进时间、成本和资源估计的准确度。
 
 帮助项目团队的建立和获得项目人员的承诺。
 
 为绩效测量和项目控制定义一个基准。
 
 辅助沟通清晰的工作责任。
 
 为其他项目计划的制定建立框架。
 
 帮助分析项目的最初风险。
 
  
 
 6.WBS的主要分解原则 
 
 一个单位工作任务只能在WBS中出现一次。
 
 一个WBS项的工作内容是其对应下级各项工作之和。
 
 WBS中的每一项都只有一个人负责，即使这项工作要多人来做，也是如此。
 
 WBS必须与工作任务的实际执行过程一致。
 
 WBS应服务于项目资源，项目成员必须参与WBS的制定过程，以确保一致性和全员参与。
 
 每项WBS都必须归档，以确保准确理解项目包括和不包括的工作范围。
 
 在根据范围说明书对项目的工作内容进行适当控制的同时，WBS必须具有一定的灵活性，以适应无法避免的变更需要。
 
 工作包的定义应考虑80小时法则(80-HourRule)或两周法则(TwoWeekRule)，即任何工作包的完成时间应当不超过80小时。
 
 WBS一般不超过5层，如超过即外包。
 
  
 
 7.WBS的表示方式 
 
 WBS可以由树形的层次结构图或者行首缩进的表格表示。
 
 在实际应用中，表格形式的WBS应用比较普遍，特别是在项目管理软件中。
 
  
 
 8.WBS分解方法 
 
 类比法
 
 类比法就是以一个类似项目的WBS为基础，制定本项目的工作分解结构。例如，ABC飞机制造公司，曾设计制造多种类型的大型客机，当他们计划投入设计生产某种新型战斗机时，就可以使用以往制造大型客机而设计的子系统。以从前的子系统为基础，开始新项目的WBS的编制。比如，该WBS的第一层中有飞机机身顶，该项又包括了飞机前身、飞机中部、飞机后身和机翼等第二层的多个子项。这种一般性的产品导向的WBS就成为新飞机项目的范围定义和新型战斗机成本估算等工作的起点。即参考类似项目的WBS创建新项目的WBS。
 
  
 
 自上而下法
 
 自上而下法常常被视为构建WBS的常规方法，即从项目最大的单位开始，逐步将它们分解成下一级的多个子项。这个过程就是要不断增加级数，细化工作任务。这种方法对项目经理来说，可以说是最佳方法，因为他们具备广泛的技术知识和对项目的整体视角。
 
  
 
 自下而上法
 
 自下而上法，是要让项目团队成员从一开始就尽可能的确定项目有关的各项具体任务，然后将各项具体任务进行整合，并归总到一个整体活动或WBS的上一级内容当中去。仍以ABC飞机制造公司设计制造新型战斗机为例，用这种方法，则不是开始就考察WBS制定的指导方针或是参考其他类似项目的WBS，而是尽可能详细的列出那些项目团队成员认为完成项目需要做的任务。在列出详细的任务清单后，就开始对所有工作进行分类，以便于将这些详细的工作归入上一级的大项中。比如说，项目团队某小组中的商业分析人员会知道他们必须确定用户对项目的要求以及该项目的内容要求；工程师们也会知道他们必须确定对系统的要求和对发动机的要求。于是，该小组可能会将这四项任务都归入到战斗机制造项目的概念设计这个总项中去。自下而上法一般都很费时，但这种方法对于WBS的创建来说，效果特别好。项目经理经常对那些全新系统或方法的项目采用这种方法，或者用该法来促进全员参与或项目团队的协作。
 
  
 
 使用指导方针
 
 如果存在WBS的指导方针，那就必须遵循这些方针。许多DOD（国防部）项目都要求承包商按照国防部提供的WBS模板提交他们的项目建议书。这些建议书必须包括针对WBS中每一项任务的成本估算，既有明细估算项，也有归总估算项。项目整体的成本估算必须是通过归总WBS底层各项任务成本而得到的。当国防部有关人员对成本计划进行评审时，他们必须将承包商的成本估算与国防部的成本估算进行对比，如果某项WBS任务成本有很大的出入，那一般就意味着对要做的工作任务还没搞清楚。
 
  
 
 9.确定WBS是否已分解到足够详细的一层 
 
 是否需要改善WBS工作包的成本估算和时间进度估算的精确度？
 
 WBS工作包的负责人是否超过一人？
 
 WBS的工作包是否包含了多个交付成果或实施过程？
 
 是否需要分别定义工作过程的成本或WBS内的交付成果？
 
 是否需要更精确地了解WBS内的工作过程的时间进度？
 
 不同WBS工作包内的交付成果是否相互依赖？
 
 WBS内过程中的工作实施是否有明显的时间间隔？
 
 某一要素对资源的需求一段时间内会变化吗？
 
 衡量WBS某一工作包进度的明确的目标标准存在吗？
 
 这些验收标准在WBS的工作包全部完成前还适用吗？
 
 WBS中的一些工作包是否存在一些风险需要特别的注意？
 
 WBS工作包中的某一部分是否可作为单独的单元来做时间进度计划？
 
 项目经理，项目团队，以及其他利害关系者包括客户对WBS的工作包有清晰和完全的理解吗？
 
 是否有利害关系者有兴趣WBS某一工作包的现状和业绩？

 
 

   
  

   作者：disappearedgod
  
 
  

   文章出处：http://blog.csdn.net/disappearedgod/article/details/24423093
  
 
  

   时间：2014-4-24
  
 
  
 
 
 
 

  
 
 
 
 

   
  
前记
 
  
 
   

     
    

     本想在“查找 与 树”中完成有关树的介绍，但是由于树的东西实在太多，而面试笔试也是一个重点，所以分出来写了个"数据结构-树"，后来由于那篇单独介绍树的博客也太长，就暂时分开了成为了几个博客，在相关链接中能看到。
    
 
    

     July 博客是被大家所知的，其原因是因为面试笔试题比较多。尽管他写的思路比较好，但是还有有很难以阅读的问题，也许是他把好阅读的方式放在了线下。
    
 
    

     本文还是主要根据教材来进行书写《数据结构与算法》 Adam Drozdek的C++版本，代码还是用Java的较好一些。
    
 
   
 
   
 
  
 
  

   
 
  
 
  
前言
 
 
 
 

  
 
 
 
 

  学习数据结构时候，大家一定是先学习链表，然后学习树，最后学习图。但是单单从树来讲，却不改是先讲二叉树。原因有二：其一，二叉树是一个树的特例，掌握了二叉树很难以平移到多叉树；其二，二叉树不是一个非常好的数据结构，尽管非常的简单，仍需融入多叉树的性质。
 
 
 

  
 
 
 
 

  
 
 
 
 

  
 
 
 
 
正文
 
 

  
 
 
 
 
1.1 介绍
 
 

   
  

   学习多叉树之前，先要想到是为什么要有多叉树。一个很寻常的想法就是：现实数据很多，用树形结构建立索引来方便查找。这也就是数据库诞生之前的想法。
  
 
  

   
 
  
 
  

   树家族是为了实现方便快捷的查找而存在的。树的高度是命中查找的一个不可抗拒的时间下限。在一定的数据条件下，树的高度和宽度是互相制约的。（就像一定面积下，矩形的长和宽是互相制约的。）
  
 
  

   
 
  
 
  

   而树家族中最简单的二叉树，尽管易于实现，却不能有实际的价值。其最最令人发指的是二叉树的高度太高。尽管2-3树的流行和其简单实现（红黑树）已经逐渐成为面试的加分点，但是对于大量数据来说，用红黑树实现查找是不现实的。
  
 
  

   MySQL和Berkeley DB都是基于B树原理而建立数据库的。B树是一种可实现的平衡多路查找树。
  
 
  
 
 
 
 

  
 
 
 
 

  From：Oracle Berkeley DB Java Edition
 
 
 
 
1.2 定义
 
 

  
 
 
 
 

  树的每个节点可以有两个以上的子节点，称为m阶的多叉树，或者称为m叉树。
 
 
 

  后面会介绍一些多叉搜索树。
 
 
 

  
 
 
 
 
1.3 性质
 
 
 
  
每个节点有m个子节点和m-1个键值。
每个节点中的键值按升序排列。
前i个子节点中的键值都小于地i个键值。
后m-1个子节点中的键值都大于第i个键值。
 
  

   
 
  
 
 
 
 
1.4 B树家族
 
 

  
 
 
 
 

  访问时间 = 寻道时间 + 转动时延(latency) + 数据传送时间
 
 
 

  
 
 
 
 

  引用：
 
 
 
 
  
张明波, 陆锋, 申排伟, & 程昌秀. (2005). R 树家族的演变和发展. 计算机学报,28(3), 289-300.
 
  

   
 
  
 
 
 
 
1.4.1 B 树
 
 

  
 
 
 
 

  
 
 
 
 
1.4.1.1 定义及应用
 
 

  
 
 
 
 

  B树（B-tree）是有Bayer和McCreight在1972年提出的数据结构。（他们也同时提出了数据库的索引，1972）
 
 
 

 B树索引是数据库中存取和查找文件(称为记录或键值)的一种方法，应用于磁盘读取方面
 
 

 
 
 

 B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
 

 
 
 

 <Algorithms 4th Edition>
 

 Definition.A B-tree of order M (where M is an even positive integer) is a tree that
 either is an external k-node (with k keys and associated information) or comprises
 internal k-nodes (each with k keys and k links to B-trees representing each of the k
 intervals delimited by the keys), having the following structural properties: every
 path from the root to an external node must be the same length ( perfect balance);
 and k must be between 2 and M  1 at the root and between M/2 and M  1 at
 every other node.
 
 

 
 
 

 
 
 
1.4.1.2 一些性质
 

 
 
 

 根据Knuth's的定义，m阶B树（a B-tree of order m
 ）是具有以下性质：
 
 
 
每个点最多有m个孩子
每个非叶子节点（根节点除外）最多有m/2(向上取整)个孩子
root至少有2个子树，除非root的孩子是叶子节点
k个孩子的非叶子节点含有k-1个键值
所有的叶子节点都在同一层，并且内部节点不携带任何信息。（B树的阶指最大子节点数。优势，m阶的b树节点定义为有k个键值和k+1个指针，其中m<=k<=2m，用于指定最少的子节点数）
 
 

  
 
 
 
 

  一些
  提示：根结点为叶子结点，整棵树只有一个根节点
 
 
 

 According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:（wikipedia-BTree）
  
 
Every nod.e has at most m children.
 Every non-leaf node (except root) has at least [m/2] children
 The root has at least two children if it is not a leaf node.
 A non-leaf node with k children contains k-1 keys.
 All leaves appear in the same level, and internal vertices carry no information.
 
 

 
 
 

 
 
 

 
 
 

 
 
 
1.4.1.3 一些考点
 
1.4.1.3.1 B树与红黑树
 

 
 
 

 不同：B树可以有很多的node（一般50-500），从而一个节点可以放下辅助存储器上一页或一整块的信息。
 

 相同：一棵含有n节点的B树和红黑树的高度均为O(lgn).一般的，B树由于有多节点高度还是比红黑树要低一些。
 

 
 
 
1.4.1.4 实现
 

 根据性质，B数往往至少是半满的，有较少的层，而且是完全平衡的。
 

 下面通过类来实现，该类包含：
 

 一个有m-1个单元的数组：存储键值
 

 一个有m个单元的数组：存储指向其他节点的指针
 

 可能包含其他信心来方便对树维护（friend）
 

 
 
 

 
 
 

  
 

  
template
    
     
class BTreeNode{
public:
  BTreeNode();
  BTreeNode(const T&);
private:
  bool leaf;
  int keyTally;
  T keys[M-1];
  BTreeNode *pointers[M];
  friend BTree
     
      ;
}

     
    
 
 
 

  
 
 
 
 
B树查找：
 
 

  
 
 
 
 

   
  

   
BTreeNode *BTreeSearch(keyType K,BTreeNode *node){
  if(node != 0){
    for(i=1;i
     
      keyTally && node->keys[i-1]
      
       node->node->keyTally||node->keys[i-1]>K)
      return BTreeSearch(K,node->pointers[i-1]);
    else
      return node;
  }
  else 
    return 0;
}

      
     
  
 
  

   
   
 
  
 
  

   
   
 
  
 
  

   
 
  
 
  
 
 
 
 

  搜索最坏情况：when B树中每个非根节点只有最少的允许指针数目。 q=M/2（向下取整），而且搜索要一直到叶子节点（无论命中与否）
 
 
 
 
 
B树的插入
 

 B树特点：所有叶子节点在B树的最后一层，所以插入和删除并不简单。
 

 ===》》树自底向上建立。》》根节点处于不断变化中（until 所有插入完全后才能确定）
 

 3种插入情况
 
 
 
键值放入上有的空节点：叶节点内排序
要超如键值叶节点已经满：分解叶节点，创建一个心的叶节点，将已满的叶节点中的一半键值移到新的叶节点中，并将新叶节点合并到B树中。
B树根节点是满的（2成立，一直到父节点全满的情况）：创建一个心的根节点和一个与原根同级的新节点。（高度增加）
 
 

  
 
 
 
 

 
 
 

 
 
 

 
 
 

 伪代码
 

 
 
BTreeInsert(K)
	找到一个叶节点node来插入k
	while（true）
		在数组keys中为k找到一个合适的位置；
		if node 不满
			插入K并递增keyTally；
			return；
		else			
			将node分解为node1(=node)与node2(新节点)；
			在node1和node2之间平均分配键值和指针，并正确地初始化他们的keyTally；
		k=中间键值
		if node 是根节点
			穿件一个心的根节点，作为node1和node2的父节点
			将K及指针node1和node2的指针妨碍根节点中，并将根节点的keyTally设为1；
			return；
		else
			node = 其父节点。//处理父节点
		
  
 
B树的删除
 删除操作在很大程度上是插入操作的逆过程。但，删除有更多的特殊情形。应该注意避免在删除后节点出现不到半满的情形。这意味着有时节点要合并。
 

 2中情况：
 
 
 
从叶节点删除： 
   
如果删除键值K后，叶节点至少是半满的，只有大于K的键值向左移动，来填补空位。（第一种情况的你操作）
如果删除键值K后，叶节点中的键值个数少于【m/2】（向下取整）-1，则引起下溢。 
     
如果左或右同级节点的键值数目超过下限，于是该叶节点和同级叶节点中的所有键值将在这两个叶节点中重新分配，在重新分配过程中，将父节点中划分这两个叶节点的键值移到这两个叶节点中，并从中选择中间键值，移到父节点中。
如果叶节点下溢，其同级节点中键值的数目等于【m/2】-1，就合并该叶节点和同级节点。将该叶节点、同级叶节点及父节点中划分这两个叶节点的所有键值一起放进该叶节点中，然后删除同级节点，如果出现空位，就移动父节点中的键值。如果父节点出现下溢，则会引发以西医额擦做，这时候吧父节点当做叶节点，直到根部。（第二步的逆操作）
当父节点是只有一个键值的根节点时，会出现一个特殊的情形，即合并叶节点或非也节点和他的同级节点。在这种情形下，该节点和其同级节点的键值，以及根节点的唯一键值一起放在一个心节点中，变成新的根节点。并删除源节点和其同级节点。这是两个节点在一次操作中一同消失的惟一情形。同时，树的高度-1.（第三步的逆过程）
 
 
从非也节点中删除；（采用二叉搜索树中使用过的deleteByCopying（）） 
   
这或许会引起树结构的重组。因此从非叶子节点删除键值可以简化为从叶节点中删除键值。被删除的键值用其前驱取代（或后继）。这个后继键值从该叶节点中删除，回到第一种情形。
 
 
 

  
 
 
 
 

 
 
BTreeDelete(K)
	node = BTreeSearch(K,root)
	if(node!=null)
		if node 不是叶节点
			寻找一个带有最接近K的后继S的叶节点；
			把S赋值到K所在的node中；
			node = 包含S的叶节点；
			从node中删除S；
		else 从node 中删除K
		while（1）
			if node没有下溢
				return；
			else if node 有同级节点，且同级节点有足够多的键值
				在node和同级节点之间重新分配键值；
				return；
			else if node的父节点是根节点
				if 父节点只有一个键值
					合并node、它的同级节点以及父节点，形成一个心的根节点；
				else
					合并node和它的同级节点；
					return；
				else 合并node和它的同级节点；
					node = 它的父节点；
		
 
 
 
 

 
 
 
Java 版本（4 Edition）
 
 
 

  API for a B-tree page(JAVA)
 
 
 
 

                                                                               public class P age<Key>
 Page(boolean bottom) 
 
 
 

                                                                               create and open a page
 
 
 

  void close() 
 
 
 

                                                                               close a page
 
 
 

  void add(Key key) 
 
 
 

                                                                               put key into the (external) page
 
 
 

  void add(Page p)
 
 
 

                                                                               open p and put an entry into this (internal) page that 
 
 
 

                                                                               associates thesmallest key in p with p
 
 
 

  boolean isExternal() 
 
 
 

                                                                               is this page external?
 boolean contains(Key key) 
 
 
 

                                                                               is key in the page?
 Page next(Key key) 
 
 
 

                                                                               the subtree that could contain the key
 boolean isFull()
 
 
 

                                                                               has the page overflowed?
 Page split() 
 
 
 

                                                                               move the highest-ranking half of the keys in the page to a 
 
 
 

                                                                               new page
 Iterable<Key> keys()
 
 
 

                                                                               iterator for the keys on the page
 
 
 

  
/*************************************************************************
 *  Compilation:  javac BTree.java
 *  Execution:    java BTree
 *
 *  B-tree.
 *
 *  Limitations
 *  -----------
 *   -  Assumes M is even and M >= 4
 *   -  should b be an array of children or list (it would help with
 *      casting to make it a list)
 *
 *************************************************************************/


public class BTree
    
     , Value>  {
    private static final int M = 4;    // max children per B-tree node = M-1

    private Node root;             // root of the B-tree
    private int HT;                // height of the B-tree
    private int N;                 // number of key-value pairs in the B-tree

    // helper B-tree node data type
    private static final class Node {
        private int m;                             // number of children
        private Entry[] children = new Entry[M];   // the array of children
        private Node(int k) { m = k; }             // create a node with k children
    }

    // internal nodes: only use key and next
    // external nodes: only use key and value
    private static class Entry {
        private Comparable key;
        private Object value;
        private Node next;     // helper field to iterate over array entries
        public Entry(Comparable key, Object value, Node next) {
            this.key   = key;
            this.value = value;
            this.next  = next;
        }
    }

    // constructor
    public BTree() { root = new Node(0); }
 
    // return number of key-value pairs in the B-tree
    public int size() { return N; }

    // return height of B-tree
    public int height() { return HT; }


    // search for given key, return associated value; return null if no such key
    public Value get(Key key) { return search(root, key, HT); }
    private Value search(Node x, Key key, int ht) {
        Entry[] children = x.children;

        // external node
        if (ht == 0) {
            for (int j = 0; j < x.m; j++) {
                if (eq(key, children[j].key)) return (Value) children[j].value;
            }
        }

        // internal node
        else {
            for (int j = 0; j < x.m; j++) {
                if (j+1 == x.m || less(key, children[j+1].key))
                    return search(children[j].next, key, ht-1);
            }
        }
        return null;
    }


    // insert key-value pair
    // add code to check for duplicate keys
    public void put(Key key, Value value) {
        Node u = insert(root, key, value, HT); 
        N++;
        if (u == null) return;

        // need to split root
        Node t = new Node(2);
        t.children[0] = new Entry(root.children[0].key, null, root);
        t.children[1] = new Entry(u.children[0].key, null, u);
        root = t;
        HT++;
    }


    private Node insert(Node h, Key key, Value value, int ht) {
        int j;
        Entry t = new Entry(key, value, null);

        // external node
        if (ht == 0) {
            for (j = 0; j < h.m; j++) {
                if (less(key, h.children[j].key)) break;
            }
        }

        // internal node
        else {
            for (j = 0; j < h.m; j++) {
                if ((j+1 == h.m) || less(key, h.children[j+1].key)) {
                    Node u = insert(h.children[j++].next, key, value, ht-1);
                    if (u == null) return null;
                    t.key = u.children[0].key;
                    t.next = u;
                    break;
                }
            }
        }

        for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1];
        h.children[j] = t;
        h.m++;
        if (h.m < M) return null;
        else         return split(h);
    }

    // split node in half
    private Node split(Node h) {
        Node t = new Node(M/2);
        h.m = M/2;
        for (int j = 0; j < M/2; j++)
            t.children[j] = h.children[M/2+j]; 
        return t;    
    }

    // for debugging
    public String toString() {
        return toString(root, HT, "") + "\n";
    }
    private String toString(Node h, int ht, String indent) {
        String s = "";
        Entry[] children = h.children;

        if (ht == 0) {
            for (int j = 0; j < h.m; j++) {
                s += indent + children[j].key + " " + children[j].value + "\n";
            }
        }
        else {
            for (int j = 0; j < h.m; j++) {
                if (j > 0) s += indent + "(" + children[j].key + ")\n";
                s += toString(children[j].next, ht-1, indent + "     ");
            }
        }
        return s;
    }


    // comparison functions - make Comparable instead of Key to avoid casts
    private boolean less(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) < 0;
    }

    private boolean eq(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) == 0;
    }


   /*************************************************************************
    *  test client
    *************************************************************************/
    public static void main(String[] args) {
        BTree
     
       st = new BTree
      
       ();

//      st.put("www.cs.princeton.edu", "128.112.136.12");
        st.put("www.cs.princeton.edu", "128.112.136.11");
        st.put("www.princeton.edu",    "128.112.128.15");
        st.put("www.yale.edu",         "130.132.143.21");
        st.put("www.simpsons.com",     "209.052.165.60");
        st.put("www.apple.com",        "17.112.152.32");
        st.put("www.amazon.com",       "207.171.182.16");
        st.put("www.ebay.com",         "66.135.192.87");
        st.put("www.cnn.com",          "64.236.16.20");
        st.put("www.google.com",       "216.239.41.99");
        st.put("www.nytimes.com",      "199.239.136.200");
        st.put("www.microsoft.com",    "207.126.99.140");
        st.put("www.dell.com",         "143.166.224.230");
        st.put("www.slashdot.org",     "66.35.250.151");
        st.put("www.espn.com",         "199.181.135.201");
        st.put("www.weather.com",      "63.111.66.11");
        st.put("www.yahoo.com",        "216.109.118.65");


        StdOut.println("cs.princeton.edu:  " + st.get("www.cs.princeton.edu"));
        StdOut.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
        StdOut.println("simpsons.com:      " + st.get("www.simpsons.com"));
        StdOut.println("apple.com:         " + st.get("www.apple.com"));
        StdOut.println("ebay.com:          " + st.get("www.ebay.com"));
        StdOut.println("dell.com:          " + st.get("www.dell.com"));
        StdOut.println();

        StdOut.println("size:    " + st.size());
        StdOut.println("height:  " + st.height());
        StdOut.println(st);
        StdOut.println();
    }

}

      
     
    
 
 
 

  
 
 
 
 
1.4.1.5 评价
 
 
 
  

   根据B树的定义，B树应该保证至少半满。所以，基本上会浪费50%的空间。当这种品庐出现过高时候，就应该对G树定义加以限制。
  
 
  

   模拟和分析表明，在执行大量的随机插入和删除操作后，B树大约69%满。
  
 
  
 
 
 
 
 
 
Reference：
 

  
 

  Bayer, R.; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes", Acta Informatica 1 (3): 173–189
 
 
 
 

  
 
 
 
 
 
 
1.4.2 B* 树
 

  
 

  1.4.2.1 介绍
 
 
 

  B*树有Donald Knuth提出，有Douglas Comer命名，是B树的一种变形。在B*树中，除了根节点外，其他节点都必须至少2/3满，而不像B树一样是半满。
 
 
 

  更精确的是，在m阶的B树中，所有非根节点的键值个数k为k在（2m-1）/3 (想下取整)和m-1之间。
  通过分解的延迟，减低了节点分解的频率。当进行分解时，是将两个节点分解为3个，而不是将一个节点分解为两个，使B*树的平均使用率达到了81%（Leung于1984提出）
 
 
 

  1.4.2.2 定义
 
 
 

  
 
 
 
 

  1.4.2.3 性质
 
 
 

  
 
 
 
 

  1.4.2.4 应用
 
 
 
 
 
1.4.3 B+ 树
 

 1.4.3.1 来源
 

 由于B树的一个节点代表辅助的一个页或者块。一个节点到另一个节点的传送要求一次耗时的页交换，因此应该尽可能的减少节点访问。（如果要求B树中所有节点按升序打印，可以采用终须树遍历算法，这是很容易实现。）但对非叶子节点，每次只能显示一个键值，然后就得访问另一页。因此，应该改进B树，以更快的方式顺序访问数据，而不是使用终须遍历。B+树解决了这个问题。（Weddkind）
 

 
 
 

 在B数中，对数据的引用指向树中的任意节点。但是B+树中，这种引用只指向叶节点。为了快速访问数据，对B+树的内部节点进行了索引，树的这个部分称为索引集。
 

 
 
 

 
 
 

 插入
 

 
 
 

 删除
 

 
 
 
1.4.4 前缀B+ 树
 

 
 
 
1.4.5 位树
 

 
 
 
1.4.6 R树
 

 
 
 
1.4.7 2-4 树
 

 
 
 
1.5 应用
 

  
 
后记
 
 
 
 
学习资料
 
 Insertion Into a B-Tree
 
 
 
 
 
 
 
 
 
相关链接
 
 

   
  

   数据结构-树（多叉树、二叉树、二叉搜索树、平衡二叉树、字典树、红黑树、线段树）
 
  
 
  

   树
 
  
 
  

   多叉树
 
  
 
  

   二叉树
  
 
  

   二叉搜索树
 
  
 
  

   平衡二叉树
 
  
 
  

   字典树
 
  
 
  

   红黑树
 
  
 
  线段树
 
 
 

  
 
 
 
 

主要是利用了反证法：

 

 假设 s-t这条路径为树的直径，或者称为树上的最长路

 

 现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路

 

 证明：

 

 1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则

 

 dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾

 

 2 设u不为s-t路径上的点

 

 首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了

 

 所以现在又有两种情况了：

 

 1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)

 

 2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，

 

 则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾

 

 
附上一张第二种情况的图
 

 
 
树的“重心”的一些性质及动态维护
 
 
还记得曾经提到过的树的“重心”吗？重心的定义是：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。
 
 树的重心的一个的性质：
 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
 这也是“道路修建”带来的启发。（证明：调整法）
 
 树的重心的另一个性质：
 把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
 这个让“重心”名副其实了。。。（证明：。。。自己好好思考一下吧。。。）
 
 还有一个性质：
 把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
 （证明：提示：张放想都没想说，要不然那两个不等式就矛盾了）
 
 嗯，不错，有这么多性质，可以出不少恶心题了。。。
 
 不过，我还是更关心一个事情：重心的动态维护。
 如何动态呢？
 情景1：添加一片叶子
 根据已有性质，添加一片叶子之后新的重心要么不动要么向那片叶子的方向移动一下。这样，可以用一个link-cut tree来维护。
 我们以重心为根建立这个动态树。每个节点维护它所在的子树的大小。添加叶子等于向一条路径上的维护值增加1，这个可以通过打标记实现。发现不得不移动的时候进行一次换根的操作。因为只可能移动1，所以换根的操作是可以完成的。
 我们甚至还可以维护所有点到重心的距离和！这个只需给每个点加一个维护值：这个点为根的子树中所有点到这个点的距离和，通过稍微有点复杂的标记系统还是可以维护的。
 
 情景2：删除一片叶子
 只有删除操作？那么离线改成添加吧。。。
 不允许离线？那么我们要换一个思路：
 定义稍微广义的树的重心：每个点有一个非负权，每个边有个正的长度，到所有点的权乘以距离的和最小的点定义为重心。
 注意：树的重心的位置和边的长度没有关系！。
 在只有权值修改的情况下，我们可以利用树分治配合基本数据结构来维护树的重心：
 注意到，我们可以维护一个子树内的点的权值和（利用dfs序）。这样给定一条边，我们就能够知道树的重心在这条边的哪边（看看哪边权值和大就行了）。
 这样，我们可以先找一个比较靠近中心的边，问问应该向哪边走，再分治下去，就像树分治那样（类似二分查找？）。
 当然，要想一下其他的技巧来对付”星型数据“，这个应该不难（通过拆点、拆边的技巧）。
 利用这个广义一点的重心，我们发现，删除操作其实就是把权修改成0而已，可以在log^2N的时间内动态维护了。
 如何处理多重心的情况？”抖动“一下权值使得只有一个重心不就行了。。。那另一个重心在哪里？这个只是个细节问题。。。
 能否维护距离和？能否在logN的时间内维护？欢迎讨论（将子树和查询与树分治结合起来？。。。）。
 
 情景3：移动一片叶子
 把一个叶子移动到另一个地方。
 这个怎么维护呢？其实，我们发现，新的重心应该在原来的重心和叶子新的位置的连线上（证明？应该是对的吧），移动距离很小。于是，也就可以维护了。
 
 情景4：移动一个子树（被移动的子树小于原树的一半，并且保持它的根不变）
 这个可以维护吗？
 新的重心在原来重心和新子树的接合点的连线上吗？（证出来的欢迎留言）
 有一个可以和link-cut tree配合使用的工具，叫做Euler-tour tree，它维护树的欧拉回路，基本元素是边。利用它，可以方便的完成子树的移动，并且给定一条有向边，可以回答这条边指向的子树的大小（Eurler-tour tree中没有”根“以及”父亲“这个概念！）。如果上面的那个论断是对的，那么这个应该可以维护了（复杂度？log^2N吧。。。）
 另一个思路是树块划分，把树划分成若干联通块，并且在查询的时候合并相邻的联通块使得每个联通块的大小都是sqrt(N)的级别。这个东西对维护是否有帮助？欢迎交流。。。
 
 情景5：开始N个一个点的树，每次用一条边合并两个树，要求回答新的树的重心
 离线？在线？logN？log^2N？sqrt(N)？
 等待你去探索
 
 
POJ 1655 - DP 树的重心，经典 #P
 
 
题意：求树的重心。
 树的重心：删去重心后，生成的多棵树尽可能平衡。
 重心的意义，在对树进行分治的时候可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度。
 
 解法：
 一开始想到的是模仿求树的直径那样子去Dp，两次DFS。
 son[i] - 结点i的儿子结点数目
 第一遍求出son；
 h[i] - 结点i向上的结点数目
 h[i] = h[k] + son[k] - son[i] - 1；
 blance = max(son[j] , h[i])
 第二遍求出h，和blance；
 
 后来去看题解，才发现有更简单的方法。
 应用一个性质，h[i] = n - son[i] -1；
 blance = max(son[j] , n - son[i] -1)；
 这样只需要一次DFS。
 
 
 
 
 
 
  [cpp] 
  view plain
  copy 
  
 
  
 
  
 
  
 
 
 
 
 #include <cstdio>  
 #include <iostream>  
 #include <fstream>  
 #include <cstring>  
 #include <string>  
 #include <vector>  
 #define OP(s) cout<<#s<<"="<<s<<" ";  
 #define PP(s) cout<<#s<<"="<<s<<endl;  
 using namespace std;  
 int n;  
 vector <int> adj[20010];  
   
 int son[20010];  
 bool vd[20010];  
 int ans,asize = 1<<29;  
 void DFS(int s)  
 {  
     vd[s] = 1;  
     son[s] = 0;  
     int blance = 0;  
     int size = adj[s].size();  
     for (int j = 0;j < size;j++)  
     {  
         int u = adj[s][j];  
         if (vd[u]) continue;  
         DFS(u);  
         son[s] += son[u]+1;  
         blance = max(blance,son[u]+1);  
     }  
     blance = max(blance,n - son[s] - 1);  
     if (blance < asize || blance == asize && s < ans)  
         ans = s,asize = blance;  
 }  
   
 int main()  
 {  
 //    freopen("test.txt","r",stdin);  
     int T;  
     cin>>T;  
     while(T--)  
     {  
         cin>>n;  
         for (int i = 1;i <= n;i++) adj[i].clear();  
         for (int i = 1;i <= n-1;i++)  
         {  
             int u,v;  
             scanf("%d%d",&u,&v);  
             adj[u].push_back(v);  
             adj[v].push_back(u);  
         }  
   
         memset(vd,0,sizeof(vd));  
         asize = 1<<29;  
         DFS(1);  
         cout<<ans<<" "<<asize<<endl;  
     }  
   
     return 0;  
 }
 

 
 
poj 1741 (树的分治)
 
题意：给定一棵N(1<= N <=10000)个结点的带权树，定义dist(u,v)为u,v两点间的最短路径长度，路径的长度定义为路径上所有边的权和。再给定一个 K ，如果对于不同的两个结点a,b，如果满足dist(a,b) <=K，则称(a,b)为合法点对。求合法点对个数。
 思路：看了论文《分治算法在树的路径问题中的应用》，里面讲解的很清楚，一条路径要么过根节点，要么在一颗子树中，所以用分治算法。找到树的重心作为根节点，这样每次树的节点数至少减少一半。处理经过当前根节点路径<=k的点对数，然后把根节点去掉后就把原来的树分成几颗子树了，再处理子树。我们在求经过一个根节点的路径时，里面还包含了点对属于同一颗子树的情况，所以要去掉这部分的点。
 dis(i)+dis(j)<=k(i,j的父节点不为根节点的同一个儿子）
 =dis(i)+dis(j)<=k-dis(i)+dis(j)<=k(i,j的父节点属于根节点的同一儿子).
 
 
 
 
 
 
  [cpp] 
  view plain
  copy 
  
 
  
 
  
 
  
 
 
 
 
 #include <algorithm>  
 #include<stdio.h>  
 #include<string.h>  
 const int N=10010;  
 using namespace std;  
 int head[N],num,f[N],son[N],n,D,root,size,ans,dis[N],d[N],cum;  
 bool vis[N];  
 #define max(a,b) (a<b?b:a)  
 struct edge  
 {  
     int st,ed,w,next;  
 }e[N*2];  
 void addedge(int x,int y,int w)  
 {  
     e[num].st=x;e[num].ed=y;e[num].w=w;e[num].next=head[x];head[x]=num++;  
     e[num].st=y;e[num].ed=x;e[num].w=w;e[num].next=head[y];head[y]=num++;  
 }  
 void getroot(int u,int father)//求树的重心  
 {  
     int i,v;  
     f[u]=0;son[u]=1;  
     for(i=head[u];i!=-1;i=e[i].next)  
     {  
         v=e[i].ed;  
         if(vis[v]||v==father)continue;  
         getroot(v,u);  
         son[u]+=son[v];  
         f[u]=max(f[u],son[v]);  
     }  
     f[u]=max(f[u],size-son[u]);  
     if(f[u]<f[root])root=u;  
 }  
 void getdis(int u,int father)//求节点到根节点的距离  
 {  
     int i,v;  
     son[u]=1;//更新子树的节点的子节点数，不更新也能ac  
     d[cum++]=dis[u];//将点到根节点的距离加入数组  
     for(i=head[u];i!=-1;i=e[i].next)  
     {  
         v=e[i].ed;  
         if(vis[v]||v==father)continue;  
         dis[v]=dis[u]+e[i].w;  
         getdis(v,u);  
         son[u]+=son[v];  
     }  
 }  
 int cont(int u,int mit)  
 {  
     int res=0,L,R;  
     dis[u]=mit;  
     cum=0;  
     getdis(u,0);  
     sort(d,d+cum);//将点到根节点的距离排序  
     for(L=0,R=cum-1;L<R;)  
     {  
         if(d[L]+d[R]<=D)//如果d[L]+d[R]<=D,L代表的节点可以与（R-L）个节点成对  
             res+=(R-L++);  
         else R--;  
     }  
     return res;  
 }  
 void work(int u)  
 {  
     int i,v;  
    vis[u]=true;  
    ans+=cont(u,0);//路径经过该根节点的点对数  
    for(i=head[u];i!=-1;i=e[i].next)  
    {  
       v=e[i].ed;  
       if(vis[v])continue;  
       ans-=cont(v,e[i].w);//减去属于v子树的点对数  
       root=0;f[root]=size=son[v];  
       getroot(v,0);//求v子树的根节点  
       work(root);//求v子树的点对  
    }  
 }  
 int main()  
 {  
     int i,x,y,w;  
     while(scanf("%d%d",&n,&D),n||D)  
     {  
         memset(head,-1,sizeof(head));  
         num=0;  
         for(i=1;i<n;i++)  
         {  
             scanf("%d%d%d",&x,&y,&w);  
             addedge(x,y,w);  
         }  
         memset(vis,false,sizeof(vis));  
         root=0;f[root]=size=n;ans=0;  
         getroot(1,0);  
         work(root);  
         printf("%d\n",ans);  
     }  
     return 0;  
 }
 

 
 
WC2010 重建计划
 
This post is written in Chinese. If you have trouble to read it, please use Google Translate
 
 问题简述
 
 给定一棵边上带权的树，求一个平均价值最大的简单路径。路径的平均价值定义为路径的带权长度与不带权长度的比值。
 
 问题分析
 
 在一棵树上直接找这样的路径是很困难的，因此我们考虑将问题分解。一个基本的想法是在树上分治，为保证对数级别的时间复杂度，必须使用基于点的剖分[1]。每次找到树的重心[2]作为根节点，然后将根节点的子树平均分为两部分，两部分共用根节点。对每一部递归求解，然后把这两部分合并。求树的重心的方法是随便找一个根，求出每个子树的大小，找到max{i.child.size,N-i.size}最小的i，i就是树的重心。重心可能有多个，找一个即可。
 
 对于一个分治的局面，每一部分都是当前根节点的一些子树组成的森林，再加上根节点，所以每一部分仍然是一棵树。最优的路径可能在某一个分治的部分中，也可能跨过根节点在两个部分中。前者可以直接递归下去求解，重点是处理后者的情况。这时需要做的一个重要转化是二分答案，由于答案的范围是已知的，我们可以在答案的范围内二分答案的值A，然后把树上每一条边的权值都减去A。判断有解的方法也就变成了判断是否存在一条带权长度大于等于0的路径，继续转化就是，判断最长的带权路径的带权长度是否大于等于0。
 
 如何找出跨两部分的最长带权路径呢？由于路径的长度必须满足在[L,U]之间，简单的想法是在一个部分中枚举路径的一个端点的深度i，那么这条路径的另一端在另一个部分中的深度一定是在[L-i,U-i]之间。为保证路径最长，第一个部分中深度为i的一段显然应该是这个部分中深度为i的所有路径中带权长度最大的那一条，第二部分也同理，不过要枚举深度在[L-i,U-i]的最大值。如果我们确定i的枚举顺序以后，[L-i,U-i]区间的移动就是单调的，因此可以用单调队列维护最大值，因此时间复杂度就是线性的。
 
 算法描述
 
 求出当前树的重心，对当前树进行点剖分。
 
 二分当前树中平均长度最大值A，判断二分范围是否满足精度，如果满足转到步骤5，否则转到步骤3。
 
 将树上所有边权值减去A，求出剖分的两部分每个深度上的最长带权路径长度。
 
 用单调队列维护，求出跨两部分的带权路径长度最大值，判断该值是否大于等于0，转到步骤2。
 
 对剖分的两部分分别递归求解，如果这一部分大小大于等于L的话。
 
 复杂度分析
 
 对树点剖分的时间复杂度为O(logN)，求重心的时间复杂度为O(N)，二分答案时间复杂度为O(logV)，求带权路径长度最大值时间复杂度为O(N)，因此总时间复杂度为O(NlogNlogV)。
 
 
 
/* 
 * Problem: NOI Winter Camp 2010 Rebuild
 * Author: Guo Jiabao
 * Time: 2010.3.12 14:01
 * Label: Solved
 * Memo: Binary Search + Monoqueue + Devide & Conquer on tree
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <deque>
#include <string>
#include <queue>
using namespace std;
#define var(a,b) typeof(b) a(b)
#define foreach(a,b) for (var(a,b.begin());a!=b.end();++a)

const int MAXN = 100001,MAXM=MAXN*2,INF=~0U>>1;
const double LIM=1e6,FINF = 1e20;

struct Monoqueue
{
    struct element
    {
        int key;
        double value;
    }Q[MAXN];
    int head,rear;
    void reset()
    {
        rear = 0;
        head = 1;
    }
    void insert(int k,double v)
    {
        while (rear >= head && v > Q[rear].value)
            rear--;
        Q[++rear].value = v;
        Q[rear].key = k;
    }
    int getmax(int L)
    {
        while (Q[head].key < L)
            head++;
        return Q[head].key;
    }
}MQ;

struct edge
{
    edge *next;
    int t,c;
};

int N,L,U,EC,timestamp,Total;
int t_ctd,t_ctd_csm,md1,md2,*t_maxdpt;
int size[MAXN],depth[MAXN];
double length[MAXN],d1m[MAXN],d2m[MAXN],*t_dm;
edge *V[MAXN],ES[MAXM];
int ava[MAXN];
double Ans,t_delta;

inline void addedge(int a,int b,int c)
{
    edge *e=ES+ ++EC;
    e->next = V[a];
    e->t = b;
    e->c = c;
    V[a] = e;
}

void init()
{
    freopen("rebuild.in","r",stdin);
    freopen("rebuild.out","w",stdout);
    scanf("%d%d%d",&N,&L,&U);
    for (int i=1;i<N;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
        addedge(b,a,c);
        if (L == 1 && c > Ans)
            Ans = c;
    }
}

void get_depth(int i)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (depth[j] == -1)
        {
            depth[j] = depth[i] + 1;
            get_depth(j);
        }
    }
}

int get_longest_line(int start)
{
    int i,maxdepth;
    memset(depth,-1,sizeof(depth));
    depth[start] = maxdepth = 0;
    get_depth(start);
    for (i=1;i<=N;i++)
        if (ava[i] == 0 && depth[i] > maxdepth)
        {
            maxdepth = depth[i];
            start = i;
        }
    memset(depth,-1,sizeof(depth));
    depth[start] = maxdepth = 0;
    get_depth(start);
    for (i=1;i<=N;i++)
        if (ava[i] == 0 && depth[i] > maxdepth)
            maxdepth = depth[i];
    return maxdepth;
}

void get_size(int i)
{
    int csm = 0;
    size[i] = 1;
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (size[j] == -1)
        {
            get_size(j);
            size[i] += size[j];
            if (size[j] > csm)
                csm = size[j];
        }
    }
    if (Total - size[i] > csm)
        csm = Total - size[i];
    if (csm < t_ctd_csm)
    {
        t_ctd_csm = csm;
        t_ctd = i;
    }
}

int get_centroid(int i)
{
    memset(size,-1,sizeof(size));
    t_ctd_csm = INF;
    get_size(i);
    memset(size,-1,sizeof(size));
    return t_ctd;
}

void count_size(int i)
{
    size[i] = 1;
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (size[j] == -1)
        {
            count_size(j);
            size[i] += size[j];
        }
    }
}

void count_depth_max_length(int i)
{
    //求最大深度
    if (depth[i] > *t_maxdpt)
        *t_maxdpt = depth[i];
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        //求該深度最大帶權長度
        if (length[i] > t_dm[depth[i]])
            t_dm[depth[i]] = length[i];
        if (depth[j] == -1)
        {
            length[j] = length[i] + e->c - t_delta;
            depth[j] = depth[i] + 1;
            count_depth_max_length(j);
        }
    }
}

bool check(double delta,int ctd,edge *f)
{
    edge *e;
    int i,j,k;
    for (i=0;i<=N;i++)
        d1m[i] = d2m[i] = -FINF;
    t_delta = delta;
    memset(depth,-1,sizeof(depth));
    memset(length,-1,sizeof(length));
    md1 = md2 = 0;
    length[ctd] = depth[ctd] = 0;

    //統計部份1
    t_dm = d1m;
    t_maxdpt = &md1;
    for (e=V[ctd];e != f;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        length[j] = e->c - t_delta;
        depth[j] = 1;
        count_depth_max_length(j);
    }
    //統計部份2
    t_dm = d2m;
    t_maxdpt = &md2;
    for (e=f;e;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        length[j] = e->c - t_delta;
        depth[j] = 1;
        count_depth_max_length(j);
    }
    //單調隊列維護最大值
    //確定左邊界
    i = U-1;
    if (i > md1)
        i = md1;
    //確定右邊界
    k = L-i;
    if (k < 1)
        k = 1;
    MQ.reset();
    for (j=k;j<U-i && j<=md2 ;j++)
        MQ.insert(j,d2m[j]);
    double curv,maxv=-INF;
    for (;i>0 && L-i<=md2;i--)
    {
        j = U-i;
        if (j<=md2)
            MQ.insert(j,d2m[j]);
        int k = MQ.getmax(L-i);
        curv = d1m[i] + d2m[k];
        if (curv > maxv)
            maxv = curv;
    }
    return maxv >= 0;
}

double binary(int ctd,edge *f)
{
    double a=0,b=LIM,m;
    while (b - a >= 0.0001)
    {
        m = (a+b)/2;
        if (check(m,ctd,f))
            a = m;
        else
            b = m;
    }
    return a;
}

void dct(int start)
{
    int nowt = ++timestamp;
    int line = get_longest_line(start);
    if (line<=L || line<=2)
        return;
    int ctd = get_centroid(start); //取得重心
    double cur;
    //分割兩部份
    count_size(ctd);
    int pls = 0,pls2 = 0;
    edge *e,*f;
    for (e=V[ctd];e;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        pls += size[j];
        if (pls + pls + 1 >= size[ctd] - 1)
        {
            f = e->next;
            pls2 = size[ctd] - pls;
            pls++;
            break;
        }
    }
    //合併兩部份
    cur = binary(ctd,f);
    if (cur > Ans)
        Ans = cur;
    //遞歸部份1
    int j;
    if (pls-1 >= L)
    {
        for (e=f;e;e=e->next)
            if (ava[j=e->t] ==0)
                ava[j] = nowt;
        Total = pls;
        dct(ctd);
        for (edge *e=f;e;e=e->next)
            if (ava[j=e->t] ==nowt)
                ava[j] = 0;
    }
    //遞歸部份2
    if (pls2-1 >= L)
    {
        for (e=V[ctd];e!=f;e=e->next)
            if (ava[j=e->t] ==0)
                ava[j] = nowt;
        Total = pls2;
        dct(ctd);
        for (e=V[ctd];e!=f;e=e->next)
            if (ava[j=e->t] ==nowt)
                ava[j] = 0;
    }
}

void solve()
{
    memset(ava,0,sizeof(ava));
    Total = N;
    dct(1);
}

int main()
{
    init();
    solve();
    printf("%.3lf\n",Ans);
    return 0;
}
 
 
 
 
 
[1]
 具体证明参见2009年集训队论文《分治算法在树的路径问题中的应用》。
 
 
 
 [2] 树的重心就是满足“删除该点后，剩余的最大的子树顶点数最少”的点。