2012-10-12 61 views
1

當我在學校時,我們有一個實施2-3樹的任務。我這樣做,並建立了以下2-3樹https://github.com/awm086/2-3-tree/blob/master/2_3_tree.cppC++中樹數據結構的實際使用示例?

現在我正在回顧並嘗試刷新我的C++知識,我忍不住想知道如何在實際生活中使用這個數據結構。我希望能夠編寫一個可以利用這種數據結構的程序。所以我想我要求一個使用樹型數據結構的真實生活示例(足夠簡單,我可以實現)?

+2

2-3樹的定義是什麼?你的代碼缺少最重要的部分:類型的文檔。 –

+1

一個簡單的現實生活中的問題:字典 –

+1

嘗試編寫一個拼寫檢查器。然後嘗試編寫一個應用程序,在鍵入時完成單詞完成。例如,當你輸入「comp」時,你的程序會提示一些可能的完成:「complete」,「computer」,「comprehend」等。 –

回答

2

樹例如在std::map這樣的關聯容器中使用,因爲它們提供了非常快的查找,插入和刪除。

+2

std :: map通常是一棵紅黑樹。 –

+1

C++標準沒有規定必須使用紅黑樹來實現std :: map,只是這是實現它們的常用方法。有幾種類型的樹木數據結構是平衡的(最佳搜索深度)並具有快速插入/刪除:紅黑樹是一種;另外2-3棵樹。 – reece

1

你的意思是爲什麼要使用樹 - 或爲什麼2-3樹?

樹讓您存儲一組有序數據的無(多)重新排序,當你添加新的數據

2-3樹optomised,使他們不會變得不平衡

+0

我知道樹是什麼,它是如何工作的。我需要增強我的理解力,是我可以實現自己的一棵樹(任何樹)的真實生活用例。例如上面評論中提到的例子。我不確定是否應該編輯我的問題以更好地解釋我需要的內容。 – awm

2

從維基百科2-3樹的頁面,

2-3樹是AA樹的等角,意味着它們是等效的數據結構。換句話說,對於每2-3棵樹,至少存在一個數據元素順序相同的AA樹。

和(來自AA樹)

在計算機科學中的AA樹是用於存儲和檢索有效有序數據平衡樹的形式。

最後,

的AA樹的性能相當於一個紅黑樹的性能。雖然AA樹比紅黑樹更多地旋轉,但更簡單的算法往往更快,並且所有這些均衡導致相似的性能。紅黑樹在性能上比AA樹更加一致,但AA樹趨於平坦,這會導致搜索時間稍快。

0

樹狀數據結構在很多地方被廣泛使用,您可以按如下方式進行操作。

  • Data base designing

你可以創建自己的數據庫來存儲數據,從而在一定的價值假設BST(二叉搜索樹),那麼你可以選擇的值,這將是更小和更大,立足於這些值可以將數據存儲在樹節點中。

  • Creating file system

這是樹的巨大的使用,所以你可以嘗試以下的區域。