紅黑樹比較函數

-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; 
    } 
}

我不明白這個搜索是如何工作的比較功能，因爲沒有當停止條件找到了一個節點。

來源

2016-02-17 Gustavo

「我用C實現了一棵紅黑樹。在C++地圖中......」 - 那它是哪種語言？ C和C++是**不同的**語言！ – Olaf

我的目的是查看C++ stl庫來了解它是如何工作的。 – Gustavo

您還可以查看Python或Fortran庫。但是這並沒有說明如何在C中實現它。而且C很好**有**比較運算符。學習C，閱讀C書，而不是C++書或小說。如果您的C代碼中存在**特定的**問題，請清楚地說明並提供[mcve]。 – Olaf

您可以表達不全等方面的平等：

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

等價假設比較關係是嚴格全序。這是C++ Compare類型所需的，也是您的樹實現中的比較函數必須要求的。

就你的二叉樹搜索而言，看看第一個cmp是如何實現的。注意它是如何發現什麼時候只使用<來返回0。使用第二個cmp，您的實現可以完全相同。

來源

2016-02-17 20:59:49 user2079303

當然，這假定'<'運算符描述了總排序。並不是所有的類型都提供這樣的排序，並且並非所有的'<'運算符都提供了一個。另一方面，那些不大可能不應該被用在搜索樹中。 –

@JohnBollinger的確，我的答案假設了需要嚴格總排序的C++比較類型的上下文。我會明確提及它。 – user2079303

OP似乎在C中重新實現。不知道他的問題是什麼，因爲他甚至不顯示代碼。 – Olaf

我相信你在談論使用比較器。如果是這樣，this question's answer應該幫助你。

來源

2016-02-17 20:59:01 Panda

我的樹在C中實現。當我的比較函數返回0或1時，搜索算法如何工作？在這種情況下，搜索算法無法檢查節點是否等於當前節點。只需<= or > =是可能的。 – Gustavo

兩者都很好。您正在實施比較，因此如果您想比較節點值之間的<<或<<=，則完全取決於您。你使用哪種紅/黑色代碼？ Apple，MIT還是Linux內核？ –

紅黑樹比較函數

回答

相關問題