數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 4.1：集合_基于二分搜索樹實(shí)現(xiàn)（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序?qū)崿F(xiàn)

• 2.1 增加操作

• 2.2 刪除操作

• 2.3 查找操作

• 2.4 其他操作

• 3. 算法復(fù)雜度分析

• 3.1 增加操作

• 3.2 刪除操作

• 3.3 查找操作

• 4. 完整代碼

1. 概念及基本框架

集合?是一種高級(jí)數(shù)據(jù)結(jié)構(gòu)，其實(shí)現(xiàn)方法也不唯一，但存儲(chǔ)上使用?鏈?zhǔn)酱鎯?chǔ)（即內(nèi)存的物理空間是不連續(xù)的）。這一節(jié)我們通過?二分搜索樹?來(lái)實(shí)現(xiàn)集合這種數(shù)據(jù)結(jié)構(gòu)。

集合?的基本特性：集合內(nèi)的元素?不能重復(fù)?。
注：有些集合（多重集合）中元素也可以重復(fù)。
顯然，二分搜索樹滿足集合的特性，所以我們嘗試?yán)枚炙阉鳂鋪?lái)實(shí)現(xiàn)集合。
我們先利用一個(gè)由?純虛函數(shù)?構(gòu)成的?抽象類?作為一個(gè)接口來(lái)定義這些操作。具體代碼如下：

下面只需要通過繼承?抽象類，并且重寫?純虛函數(shù)?，就可以完成?集合?的實(shí)現(xiàn)。集合類的框架如下：

這里為了避免重復(fù)設(shè)計(jì)就可以兼容更多數(shù)據(jù)類型，引入了?泛型?，即?模板?的概念。（模板的關(guān)鍵字是?class?或?typename）

這里的?bst?表示一棵?二分搜索樹?，同樣，為了保護(hù)數(shù)據(jù)，變量設(shè)置為?private?。
注：這里沒有顯式的給出構(gòu)造函數(shù)，因?yàn)樽宇愔谐硕炙阉鳂鋵?duì)象之外沒有特別需要初始化的東西。編譯器會(huì)默認(rèn)先調(diào)用?二分搜索樹?類（即父類）的構(gòu)造函數(shù)，再去調(diào)用?集合?類（即子類）的構(gòu)造函數(shù)。
實(shí)現(xiàn)了前面的程序之后，接下來(lái)就是一個(gè)集合的增、刪、查以及一些其他基本操作，接下來(lái)利用代碼去實(shí)現(xiàn)。

2. 基本操作程序?qū)崿F(xiàn)

2.1 增加操作

直接調(diào)用二分搜索樹的增加操作。（因?yàn)槎炙阉鳂渲械脑乇緛?lái)就不重復(fù)）

2.2 刪除操作

直接調(diào)用二分搜索樹的刪除操作。

2.3 查找操作

2.4 其他操作

集合還有一些其他的操作，包括?集合大小?的查詢等操作。

3. 算法復(fù)雜度分析

因?yàn)榧喜僮髦苯诱{(diào)用了二分搜索樹的操作，所以其操作的時(shí)間復(fù)雜度和二分搜索樹相同。

3.1 增加操作

3.3 刪除操作

3.3 查找操作

總體情況：

很顯然，利用二分搜索樹很容易實(shí)現(xiàn)集合這一高級(jí)數(shù)據(jù)結(jié)構(gòu)。

4. 完整代碼

程序完整代碼（這里使用了頭文件的形式來(lái)實(shí)現(xiàn)類）如下，本節(jié)不再提供?二分搜索樹?類的實(shí)現(xiàn)代碼，如有需要，可參看?3.1?。
抽象類?接口代碼：

集合類?代碼：