2016-02-17 3 views
-1

Я реализовал красное черное дерево в C. На карте C++ можно предоставить произвольное сравнение, которое выполняет только значение операции1 < value2. Эта операция возвращает true или false, но как дерево реализуется без операции сравнения? Я хочу, чтобы моя функция сравнения возвращала только 1 или 0 без какого-либо оператора. Я попытался прочитать его в stl, но код не читается, хотя у меня есть опыт работы на C++.Функция сравнения красного черного дерева

Полный код не требуется, поскольку это тот же код, что и всякая другая реализация дерева. В настоящее время существует следующая функция сравнения:

int cmp(void *key1, void *key2){ 
    if(*(int*)key1 < *(int*)key2){ 
    return 1; 
    }else if(*(int*)key1 > *(int*)key2){ 
    return -1; 
    }else{ 
    return 0; 
    } 
} 

Я хочу функции сравнения, как это:

int cmp(void *key1, void *key2){ 
    if(*(int*)key1 < *(int*)key2){ 
    return 1; 
    }else{ 
    return 0; 
    } 
} 

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

+0

«Я реализовал красное черное дерево в C. На карте C++ ...» - Так какой это язык? C и C++ являются ** разными ** языками! – Olaf

+0

Мое намерение состояло в том, чтобы посмотреть в библиотеке C++ stl, чтобы понять, как это работает. – Gustavo

+0

Вы также можете посмотреть в библиотеке Python или Fortran. Но это не показывает, как реализовать его в C. And C очень хорошо ** имеет ** операторы сравнения. Чтобы узнать C, прочитайте книгу C, а не книгу C++ или роман. Если у вас есть ** конкретная проблема с вашим кодом C, четко укажите это и укажите [mcve]. – Olaf

ответ

3

Вы можете выразить равенство в условиях строгого неравенства:

(a == b) <==> !(a < b || b < a) 

Эквивалентность предполагает, что отношение сравнения строгое общее упорядочение. Это требуется для типов сравнения C++, а также того, что вы должны требовать от функции сравнения в реализации дерева.

Что касается поиска в двоичном дереве, ознакомьтесь с тем, как реализован первый cmp. Обратите внимание на то, как он узнает, когда возвращаться 0, используя только <. Ваша реализация может делать то же самое с использованием второго cmp.

+0

Конечно, предполагается, что оператор '<' описывает полное упорядочение. Не все типы предоставляют такой порядок, и не все «<» операторы предоставляют его. С другой стороны, те, которые, вероятно, не должны использоваться в дереве поиска. –

+0

@JohnBollinger действительно, мой ответ предполагает контекст типов сравнения C++, требующих строгого общего упорядочения. Я укажу это прямо. – user2079303

+0

OP, похоже, реинсталлируется в C. Не уверен, в чем его проблема, поскольку он даже не показывает код. – Olaf

1

Я считаю, что вы говорите об использовании компараторов. Если это так, this question's answer должен помочь вам.

+0

Мое дерево реализовано на C. Как работает алгоритм поиска, когда моя функция сравнения возвращает 0 или 1? В этом случае алгоритм поиска не может проверить, равен ли узел текущему узлу. Только <= or > = возможно. – Gustavo

+0

Либо в порядке. Вы реализуете сравнение, поэтому, если вы хотите сравнить '<' или '<=' между значениями узлов, это полностью зависит от вас. Какой красный/черный код вы используете? Apple, MIT или ядро ​​Linux? –

 Смежные вопросы

  • Нет связанных вопросов^_^