Получить все возможные узлы на одном уровне для данной позиции

Question

Линейный массив с родителем в i = 0 и дочерними элементами в 2i + 1 и 2i + 2

Выяснить всех братьев и сестер человека X. Вернуть отсортированный список братьев и сестер.

Если никакие братья и сестры не возвращают -1.

Example:

arr = 1,2,3,4,5,6
X = 5

Output: 4,6

    Explanation : 2,3 are children of 1. 
                  4,5 are children of 2.
                  6 are children of 3.
Here get children of 2 and 3 (because 3 is sibling of 2)  
So siblings of 5 are 4,6.

Как правильно решить эту программу.

Answer 1

Сначала найдите позицию значения. Затем получите начальный индекс родного брата и конечный индекс в массиве. Начальный индекс - это наибольшая степень двойки позиции значения, а удвоение начального индекса -1 - конечный индекс. Получите подмассив и отфильтруйте значение из массива.

  public int[] getSiblings(int[] arr, int x) {
    int pos = 0;
    for (int i = 0; i < arr.length; i++) {
      if(arr[i]==x) pos = i+1;
    }
    int start = Integer.highestOneBit(pos); // get max power of 2
    int end = start*2-1 >= arr.length ? arr.length: start*2-1;
    return IntStream.range(start-1, end).map(i -> arr[i]).filter(v -> v!=x).toArray();
  }

Answer 2

Если я правильно прочитал этот вопрос, вам нужны все индексы одного поколения, а не просто одного и того же родителя.

Индекс i принадлежит полу поколения (база журнала 2 (i + 1)).

index generation
0     0
1     1
2     1
3     2
4     2
5     2
6     2
7     3   etc...

Диапазон индексов, принадлежащих поколению g для g> 0, составляет от (2 ^ g) -1 до (2 ^ (g + 1)) - 2. Это не относится к поколению 0, которое является самим собой.

Затем, чтобы найти индексы-братья для данного индекса:

1. Find its generation
2. Find the range of indices for that generation 
3. Eliminate the input index
4. Truncate the range if it extents past the end of the array.

E.g. arr = 1,2,3,4,5,6
X = 5
i = index of 5 = 4.
g = floor(log base 2(5)) = 2
range = 3 through 6.
after eliminating the input and truncating, the valid indices are 3, 5.
values at these indices are 4, 6.

Answer 3

Как я понял, это проблема печати всех элементов на той же глубине, что и X в дереве.

Сначала выясняем глубину X:

depth = floor(log2(X));

Теперь мы имеют глубину X. Нам просто нужно вывести все элементы с той же глубиной, что и X в массиве. Уровень i-th (глубины i) начинается с позиции 2^i - 1, поэтому:

if(depth == 0) {print(-1); return;}

int sibbling_count = 0;
for(int i = 2^depth - 1; i < 2^(depth + 1) - 1; i++){
    if(i < arr.size() && arr[i] != X){
         sibbling_count++;
         print(arr[i]);
    }
}
if(sibbling_count == 0) print(-1);