Функция сравнения для упорядочения DFS произвольного дерева

Question

Представьте полное двоичное дерево, где узлы на каждом уровне глубины пронумерованы слева направо.

• Узел 1 имеет детей 2 и 3.
• Узел 2 имеет детей 4 и 5.
• Узел 3 имеет детей 6 и 7.

т.д.

на глубине D будут 2^D узлы с номерами 2^D ... 2^(D + 1) -1

Обход поиска по глубине для полного дерева любой глубины детерминированный.

Например, дерево глубины 4 всегда будет проходить: 1,2,4,8,9,5,10,11,3,6,12,13,7,14,15.

Я ищу способ сортировки списка чисел, где они будут попадать в обход DFS любого дерева.

В частности, мне нужна функция сравнения, которая может принимать два номера и определять, что на первом месте происходит при обходе DFS.

Любые идеи?

---

Предварительно вычисление обхода DFS для некоторого максимального размера дерева является одним из способов сделать это, но я бы предпочел математическое решение, которое не требует вычислений и хранения этой информации.

Answer 1

алгоритма с лучшей производительностью будет один предложенный FUD, так как вам нужно всего лишь пройти по дереву один раз, а затем сравнение будет только O(1).

Но если вы не хотите пересекать все дерево и просто хотите компаратор, то есть компаратор O(log n) (который можно оптимизировать до O(log log n) или практически O(1)).

Идея заключается в том:

Наблюдение 1: Если два узла находятся на одной и той же глубине, тем выше номером узел будет пройден позже.

Наблюдение 2: Если два узла не находятся на одной глубине, отметив, что родительский объект всегда посещается первым перед потомками, мы берем предка более глубокого узла, который находится на той же глубине, что и более мелкий узел. Затем сравните с помощью Наблюдение 1.

Использование системы счисления в полном бинарном дереве, вы можете получить родительский узел n, принимая n/2.Итак, после получения глубины каждого узла (можно сделать в O(log n) или предварительно вычисленном), скажем d1 < d2, мы делим более глубокий узел на 2^(d2-d1) (мощность может быть выполнена в O(log p), в этом случае p - O(log n), поэтому это O(log log n)). Тогда какой из них является большим =)

в C++:

// This method can be modified to be faster 
// See: http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i 
int depth(int n){ 
    int result=-1; 
    for(;n>0; result++, n/=2); 
    return result; 
} 

bool n1_before_n2(int n1, int n2){ 
    int d1 = depth(n1); 
    int d2 = depth(n2); 
    if(d1>d2) n1 >>= (d1-d2); 
    if(d2>d1) n2 >>= (d2-d1); 
    return n1<n2; 
} 

Answer 2

Вы можете предварительно вычислить максимальный уровень глубины в полном дереве. И присваивать каждому узлу возрастающий набор значений, например. в вашей глубине 4 дерева

v[1]=1, v[2]=3, v[4]=3 ... 

Тогда функция сравнения будет просто

int cmp(i,j): 
    return v[i]<v[j] 

Answer 3

Если вы заметили шаблон, вы можете попробовать следующее. Я не уверен, может потребоваться некоторое уточнение, но это дает вам некоторую идею для дальнейшего изучения.

1. Для каждого узла найдите наивысшую мощность двух, которая меньше значения. Например, если мы сравниваем 7 и 13, то для 7 это будет 4, а для 13 это будет 8.

2. Теперь вычислите разницу между значениями и их соответствующими степенями 2. Для 7 это будет 3, а для 13 будет 5.

3. Если полномочия двух одинаковы, то один с более низкой разницей должен быть выше той, которая имеет более высокую разницу.

4. Для нашего случая вычислите родительский элемент 13 в той же строке, что и 7. Это будет 13/2^(разница уровней между 7 и 13).

Следовательно, родитель 13 = 13/2^1 = 6.
С 6 < 7, можно сказать, что 13 предшествует 7.

EDIT: как это было предложено, ненужный шаг- удален.

Answer 4

Вот математическое решение проблемы, но я не мог получить замкнутую форму для уравнения: -

Чтобы найти индекс DFS из узла к в дереве общего узла N: -

DFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1)  if k is odd 

DFS-order(k) = DFS-order(k/2) + 1    if k is even 

Base Case: DFS-order(1) = 0 

Вы можете найти закрытую форму для вышеупомянутого уравнения, которое, я думаю, является математикой более высокого уровня.

Объяснение: -

Для нечетных узлов мы сначала пройти все оставшиеся substree узлы родителя и плюс 1 для нового индекса. Мы знаем, что левое поддерево имеет половину узлов полного двоичного дерева, корневого в родительском узле, исключая родителя. Всего узлов в полном BT - 2^d - 2, исключая корень. Левое поддерево имеет половину его 2^(d-1) - 1. d - глубина корня дерева у родителя. Глубина дерева, внедренная в узел k, равна Total depth - log(k). Общая глубина log(N+1). Следовательно, No of Nodes в левом поддереве - 2^(log(N+1) - log((k-1)/2) - 1) - 1. Мы добавляем 1 для еще одного обхода родительского профиля к текущему узлу, следовательно, final sum = 2^(log(N+1) - log((k-1)/2) - 1). Мы добавляем это к родительскому индексу, чтобы получить индекс текущего узла, следовательно, DFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1).

Для Даже узлу тривиально, что его индекс родительский индекс + 1

Примечание: Уравнение можно найти индекс узла к в O (журнал (к)) время & журнала оператора Использование функции пол, чтобы получить дискретные значения.

Answer 5

Вот реализация C @ из ответа Абхишек в:

//returns -1 if a before b; 0 if same; else 1 
int treesort(unsigned int a,unsigned int b) 
{ 
    int diff, swap=1, side=0; 
    unsigned int ra, rb; 
    if (a==b) return 0; 
    //ensure deeper node is always in b. 
    if (b<a) { int t=a;a=b;b=t;swap=-1;} 
    //treat 0 as before everything else 
    if (a==0) return -1*swap; 
    //clear all but the msb 
    ra=base(a); rb=base(b); 
    //move up to same level, tracking child side 
    while (rb!=ra) { side=b&1;rb/=2;b/=2; } 
    //compare parents at same level 
    diff = (b-rb)-(a-ra); 
    //if same parent, answer depends on side. 
    if (diff==0) diff = side; 
    //restrict to [-1,1], be sure to handle swap 
    return (diff>0?-1:1)*swap; 
} 

base это функция, которая очищает все, кроме самого старшего бита. Я тестировал с
int base(unsigned int x){return 1<<(msb32(x)-1);} используя Sir Slick's msb32() от this question.