Блог

Главная - Вопросы по программированию - Итератор для красно-черного двоичного дерева поиска в C

Итератор для красно-черного двоичного дерева поиска в C

#c #iterator #red-black-tree

#c #итератор #красно-черное дерево

Вопрос:

Мне нужно найти точку из красно-черного BST, которая ближе всего к заданной точке. Для этого я рассмотрел обход по порядку, для которого мне нужно отслеживать минимальное расстояние и ближайшую точку в каждый момент времени.

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

 typedef struct minimum {
    point x;
    int m;
}minpoint;

обход по порядку

 minpoint nearest(struct node *root,point p,minpoint min ){
    if (root == NULL)
        return min;
    min = nearest(root-&&t;left,p,min);
    if(distanceSquared(root-&&t;data,p) < min.m) {
    min.m=distanceSquared(root-&&t;data,p);
    min.x=root-&&t;data;
    }
    min =nearest(root-&&t;ri&ht,p,min);
    return min;
}

Есть ли лучший или оптимальный способ выполнить итерацию по красно-черному двоичному дереву поиска?

структуры точки и узла следующие:

точка

 typedef struct point2d {
    double x;
    double y;
}point;

Узел

 struct node{
    point data;
    char color;
    struct node *left, *ri&ht, *parent;
};

Комментарии:

1. Дерево обычно организовано в соответствии с некоторым принципом. Знаете ли вы, каков принцип организации вашего дерева? Можем ли мы, например, предположить, что узлы слева имеют меньший цвет, или меньшее значение x, или меньшее расстояние от начала координат, или что?

2. Красно-черное дерево — это самобалансирующееся дерево. Он соответствует следующим условиям: 1) Каждый узел имеет красный или черный цвет. 2) Корень дерева всегда черный. 3) Нет двух смежных красных узлов (у красного узла не может быть красного родительского или красного дочернего узла). 4) Каждый путь от узла (включая корневой) к любому из его дочерних нулевых узлов имеет одинаковое количество черных узлов. Подробная информация .

3. Красно-черное дерево обычно является бинарным деревом поиска. Двоичному дереву поиска не требуется обход inorder (или любого другого), чтобы найти значение, наиболее близкое к чему-либо. Вам нужно запустить обычный поиск в ванильном дереве. Если вы не нашли точное значение, вы запоминаете свой узел и переходите к следующему большему (или предыдущему меньшему) узлу. Одно из двух будет наиболее близким к вашему значению. Это операция O (lo& n). Идентификатор обхода по порядку O (n).

4. @n.’местоимения’m. это верно только в том случае, если узлы дерева используют ключ, который вы ищете. Но если дерево является деревом поиска, скажем, на node.color или только на node.data.x , то нет никакого способа использовать его для отношений расстояния.

5. Вы не используете свойство BST вашего дерева (вы не можете использовать его в 2D случае). Неясно, какой цели служит дерево. Если назначение заключается просто в создании алгоритма O (N), поместите точки в массив или связанный список или что-то еще. BST не будет иметь никакого значения в алгоритме O (lo& N), поэтому вам все равно нужно будет заменить его какой-либо другой структурой. Если назначение явно требует размещения 2d-точек в красно-черном дереве, то я не думаю, что это имеет какой-либо смысл.