二進制搜索樹中的重複條目

我有一個關於BST的非常簡單的問題。我已經看到關於重複條目的BST的多個定義。有些定義BST不允許重複輸入，其他節點的左邊子節點爲< =節點值，右邊的子節點大於節點的值，其中一些定義與此相反（左邊的子節點爲<）孩子是> =）。二進制搜索樹中的重複條目

所以我的問題是關於重複條目的BST的官方定義（如果存在的話）是什麼？例如，在插入值後，BST的外觀如何：3,5,10,8,5,10？

非常感謝您澄清定義並回答我的問題！

2012-01-02 Tareq

「官方定義」？你認爲什麼是「官方」？這裏需要什麼樣的權限？ – 2012-01-02 18:35:25

我想這不是什麼級別的權威，因爲它是最常被接受的關於重複條目的BST的定義。 – Tareq 2012-01-02 19:14:11

一個在算法和數據結構區域中的公知的書籍是CLRS book，也被稱爲數據結構和算法的聖經：

enter image description here

根據該定義本書時，重複條目將放置在包含相同鍵的節點的右側樹中。作爲一個例子，從這本書採用一看BSTS的插入算法：

enter image description here

2012-01-02 18:32:56 hsalimi

哇非常有趣和溫和的答案。 – 2012-02-16 18:13:26

重要的一點是，而不是在樹中有重複確保快速查找時間。如果節點一側有重複項，則搜索時間將受到影響，因爲在繼續之前必須先通過所有重複項。

2012-01-02 18:25:05

在這種情況下，外部鏈接不是非常有用。 – 2012-01-02 18:27:56

在左子節點<節點且右子節點大於節點的樹中，這不是什麼大不了的事情。當找到第一個節點時，可以檢查正確的孩子以獲得所有重複。 – 2012-01-02 18:54:41

當然，每個節點可能只包含元素出現次數的計數 – 2012-01-02 19:03:53

回答