在平衡树中获取节点父节点的索引，传递其索引

Question

示例：

我有下面的例子，说明了锦标赛的时间表：

1 2  3 4  5 6  7 8
 |    |    |    |
 9   10    11  12
   |         |    
  13         14 
        |
       15

规则：

数字表示节点(匹配(的值。价值从上到下，因为根是冠军的最后一场比赛

树将始终保持平衡，并且可以有N个顶部位置，其中N={2,4,8,16,32,64128256…}

问题：

我需要找到一个数学函数，它将返回节点父节点的值，并传递其值。这个数学函数必须可以用C#表示。

GetNodeParent(9); // must return 13
GetNodeParent(10); // must return 13
GetNodeParent(4); // must return 10
GetNodeParent(15); // must return null

功能应该如何？

Answer 1

在我看来，处理这一问题的最简单方法是以另一种方式存储树。通常，平衡树可以表示为一个数组，根在第一个位置，叶在最后一个n/2位置，如下所示：

         1
         |
   2            3 
   |            |  
 4   5       6      7  
 |    |      |      |
8 9 10 11  12 13 14 15

在内存中是这样的：

1|2|3|4|5|6|7|8|9|10|11|12|13|14|15

现在，这个构造的一个有趣的属性是，父对象在Math.Floor(index/2)处总是(所以子对象在n*2和n*2+1处(

例如，13的父级是13/2 = 6.5 =floored= 6。它确实简化了操作。

如前所述，所有叶节点都位于最后n/2个位置。这是另一个有趣的脂肪；如果你正在寻找第一轮比赛，只需砍下你的阵列并获得Math.Ceiling(n/2)最后一项：

1|2|3|4|5|6|7|8|9|10|11|12|13|14|15

对于第二轮，移除上一轮，并在Math.Ceiling(n/2):处再次切碎

1|2|3|4|5|6|7|

---

因此，知道了这一点，GetParent可以看起来如下：

public static int? GetParent(int childIndex)
{
    int parentIndex = (int) Math.Floor((double)childIndex/2);
    return parentIndex == 0 ? (int?)null : parentIndex;
}

如果不需要空值，则直接使用return (int)Math.Floor((double)index/2);。

这可以通过这个简单的单元测试来验证，该测试是根据您的示例值的位置进行的：

[TestMethod]
public void TestMethod1()
{
    Assert.AreEqual(2, Stuff.GetParent(4));
    Assert.AreEqual(2, Stuff.GetParent(5));
    Assert.AreEqual(6, Stuff.GetParent(13));
    Assert.AreEqual(null, Stuff.GetParent(1));
}

另外，别忘了使用索引而不是值，你不能直接应用你的例子中的9和13，现在是4和2，因为这是它们在树中的索引，根在第一个位置，它的结构是这样的。你提供的例子是这样构建的：

15|13|14|9|10|11|12|1|2|3|4|5|6|7|8

如果需要按值工作，可以使用IndexOf。由于您是从1开始的，而不是从0开始的，因此还需要在每个索引中添加1。看起来是这样的：

    [TestMethod]
    public void TestMethod1()
    {
        List<int> values = new List<int>{15, 13, 14, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8};
        Assert.AreEqual(values.IndexOf(13) + 1, Stuff.GetParent(values.IndexOf(9) + 1));
        Assert.AreEqual(values.IndexOf(13) + 1, Stuff.GetParent(values.IndexOf(10) + 1));
        Assert.AreEqual(values.IndexOf(10) + 1, Stuff.GetParent(values.IndexOf(4) + 1));
        Assert.AreEqual(null, Stuff.GetParent(values.IndexOf(15)));
    }

Answer 2

选项1：构建一个相反的新树，这样您就可以使用二进制树。

---

选项2:

打电话给我的list_name.Count()，我已经为你的使用了15

GetNodeParent(9,15); // return 13
GetNodeParent(10,15);// return 13
GetNodeParent(4,15); // return 10

这是有效的，但你必须检查最终情况(在你的情况下是15(：

int GetNodeParent(int aNodeValue, int aListSize) {
    aNodeValue.Dump("Look for the parent of");
    var depth = (int)(Math.Log(aListSize,2) ); // this rounds down
    var level = Math.Pow(2,depth);
    while (aNodeValue > level) {
        depth--;
        level += Math.Pow(2,depth);
    }
    var target = level+1;   // this will be our accumulator
    var search = level;     // for our "binary search"
    var search_width = Math.Pow(2,depth).Dump("width");
    // This runs a "binary search", adding 1 to our result
    // if we are on the right side.
    while (search_width!=0){
       if (aNodeValue > level)
            target++;
        search -= search_width / 2;
        search_width /=2;
    }       
    return (int)target;
}

经过深思熟虑，在为null调用该方法之前添加一个if (aNodeValue == list_name.Count())，或者将签名更改为int?并在该方法中进行检查，使其返回null

Answer 3

你试过这个简单的公式吗？

GetNodeParent(k) = (k + 1) div 2 + N
(if >=2N then null)

其中div是整数除法(7div 2=3(