Python中的二叉樹(shù)查找算法模塊使用指南
python中的二叉樹(shù)模塊內(nèi)容:
BinaryTree:非平衡二叉樹(shù)
AVLTree:平衡的AVL樹(shù)
RBTree:平衡的紅黑樹(shù)
以上是用python寫(xiě)的,相面的模塊是用c寫(xiě)的,并且可以做為Cython的包。
FastBinaryTree
FastAVLTree
FastRBTree
特別需要說(shuō)明的是:樹(shù)往往要比python內(nèi)置的dict類慢一些,但是它中的所有數(shù)據(jù)都是按照某個(gè)關(guān)鍵詞進(jìn)行排序的,故在某些情況下是必須使用的。
安裝和使用
安裝方法
安裝環(huán)境:
ubuntu12.04, python 2.7.6
安裝方法
下載源碼,地址:https://bitbucket.org/mozman/bintrees/src
進(jìn)入源碼目錄,看到setup.py文件,在該目錄內(nèi)運(yùn)行
python setup.py install
安裝成功,ok!下面就看如何使用了。
應(yīng)用
bintrees提供了豐富的API,涵蓋了通常的多種應(yīng)用。下面逐條說(shuō)明其應(yīng)用。
- 引用
如果按照一般模塊的思路,輸入下面的命令引入上述模塊
>>> import bintrees
錯(cuò)了,這是錯(cuò)的,出現(xiàn)如下警告:(×××不可用,用×××)
Warning: FastBinaryTree not available, using Python version BinaryTree. Warning: FastAVLTree not available, using Python version AVLTree. Warning: FastRBTree not available, using Python version RBTree.
正確的引入方式是:
>>> from bintrees import BinaryTree #只引入了BinartTree >>> from bintrees import * #三個(gè)模塊都引入了
- 實(shí)例化
看例子:
>>> btree = BinaryTree() >>> btree BinaryTree({}) >>> type(btree) <class 'bintrees.bintree.BinaryTree'>
- 逐個(gè)增加鍵值對(duì): .__setitem__(k,v) .復(fù)雜度O(log(n))(后續(xù)說(shuō)明中,都會(huì)有復(fù)雜度標(biāo)示,為了簡(jiǎn)單,直接標(biāo)明:O(log(n)).)
看例子:
>>> btree.__setitem__("Tom","headmaster") >>> btree BinaryTree({'Tom': 'headmaster'}) >>> btree.__setitem__("blog","http://blog.csdn.net/qiwsir") >>> btree BinaryTree({'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- 批量添加: .update(E) E是dict/iterable,將E批量更新入btree. O(E*log(n))
看例子:
>>> adict = [(2,"phone"),(5,"tea"),(9,"scree"),(7,"computer")] >>> btree.update(adict) >>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- 查找某個(gè)key是否存在: .__contains__(k) 如果含有鍵k,則返回True,否則返回False. O(log(n))
看例子:
>>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__contains__(5) True >>> btree.__contains__("blog") True >>> btree.__contains__("qiwsir") False >>> btree.__contains__(1) False
- 根據(jù)key刪除某個(gè)key-value: .__delitem__(key), O(log(n))
看例子:
>>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__delitem__(5) #刪除key=5的key-value,即:5:'tea' 被刪除. >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- 根據(jù)key值得到該kye的value: .__getitem__(key)
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__getitem__("blog") 'http://blog.csdn.net/qiwsir' >>> btree.__getitem__(7) 'computer' >>> btree._getitem__(5) #在btree中沒(méi)有key=5,于是報(bào)錯(cuò)。 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'BinaryTree' object has no attribute '_getitem__'
- 迭代器: .__iter__()
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> aiter = btree.__iter__() >>> aiter <generator object <genexpr> at 0xb7416dec> >>> aiter.next() #注意:next()一個(gè)之后,該值從list中刪除 2 >>> aiter.next() 7 >>> list(aiter) [9, 'Tom', 'blog'] >>> list(aiter) #結(jié)果是空 [] >>> bool(aiter) #but,is True True
- 樹(shù)的數(shù)據(jù)長(zhǎng)度: .__len__(),返回btree的長(zhǎng)度。O(1)
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__len__() 5
- 找出key最大的k-v對(duì): .__max__(),按照key排列,返回key最大的鍵值對(duì)。
- 找出key最小的鍵值對(duì): .__min__()
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__max__() (9, 'scree') >>> btree.__min__() (2, 'phone')
- 兩棵樹(shù)的關(guān)系運(yùn)算
看例子:
>>> other = [(3,'http://chabaoo.cn'),(7,'qiwsir')] >>> bother = BinaryTree() #再建一個(gè)樹(shù) >>> bother.update(other) #加入數(shù)據(jù) >>> bother BinaryTree({3: 'http://chabaoo.cn', 7: 'qiwsir'}) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__and__(bother) #重疊部分部分 BinaryTree({7: 'computer'}) >>> btree.__or__(bother) #全部 BinaryTree({2: 'phone', 3: 'http://chabaoo.cn, 7: 'computer', 9: 'scree'}) >>> btree.__sub__(bother) #btree不與bother重疊的部分 BinaryTree({2: 'phone', 9: 'scree'}) >>> btree.__xor__(bother) #兩者非重疊部分 BinaryTree({2: 'phone', 3: 'http://chabaoo.cn, 9: 'scree'})
- 輸出字符串模樣,注意僅僅是輸出的模樣罷了: .__repr__()
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__repr__() "BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})"
- 清空樹(shù)中的所有數(shù)據(jù) :.clear(),O(log(n))
看例子:
>>> bother BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'}) >>> bother.clear() >>> bother BinaryTree({}) >>> bool(bother) False
- 淺拷貝: .copy(),官方文檔上說(shuō)是淺拷貝,但是我做了操作實(shí)現(xiàn),是下面所示,還不是很理解其“淺”的含義。O(n*log(n))
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> ctree = btree.copy() >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__setitem__("github","qiwsir") #增加btree的數(shù)據(jù) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) #這是不是在說(shuō)明屬于深拷貝呢? >>> ctree.__delitem__(7) #刪除ctree的一個(gè)數(shù)據(jù) >>> ctree BinaryTree({2: 'phone', 9: 'scree'}) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
- 移除樹(shù)中的一個(gè)數(shù)據(jù): .discard(key),這個(gè)功能與.__delitem__(key)類似.兩者都不反悔值。O(log(n))
看例子:
>>> ctree BinaryTree({2: 'phone', 9: 'scree'}) >>> ctree.discard(2) #刪除后,不返回值,或者返回None >>> ctree BinaryTree({9: 'scree'}) >>> ctree.discard(2) #如果刪除的key不存在,也返回None >>> ctree.discard(3) >>> ctree.__delitem__(3) #但是,.__delitem__(key)則不同,如果key不存在,會(huì)報(bào)錯(cuò)。 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 264, in __delitem__ self.remove(key) File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove raise KeyError(str(key)) KeyError: '3'
- 根據(jù)key查找,并返回或返回備用值: .get(key[,d])。如果key在樹(shù)中存在,則返回value,否則如果有d,則返回d值。O(log(n))
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.get(2,"algorithm") 'phone' >>> btree.get("python","algorithm") #沒(méi)有key='python'的值,返回'algorithm' 'algorithm' >>> btree.get("python") #如果不指定第二個(gè)參數(shù),若查不到,則返回None >>>
- 判斷樹(shù)是否為空: is_empty().根據(jù)樹(shù)數(shù)據(jù)的長(zhǎng)度,如果數(shù)據(jù)長(zhǎng)度為0,則為空。O(1)
看例子:
>>> ctree BinaryTree({9: 'scree'}) >>> ctree.clear() #清空數(shù)據(jù) >>> ctree BinaryTree({}) >>> ctree.is_empty() True >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.is_empty() False
- 根據(jù)key、value循環(huán)從樹(shù)中取值:
>>.items([reverse])--按照(key,value)結(jié)構(gòu)取值;
>>.keys([reverse])--key
>>.values([reverse])--value. O(n)
>>.iter_items(s,e[,reverse]--s,e是key的范圍,也就是生成在某個(gè)范圍內(nèi)的key的迭代器 O(n)
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> for (k,v) in btree.items(): ... print k,v ... 2 phone 7 computer 9 scree github qiwsir >>> for k in btree.keys(): ... print k ... 2 7 9 github >>> for v in btree.values(): ... print v ... phone computer scree qiwsir >>> for (k,v) in btree.items(reverse=True): #反序 ... print k,v ... github qiwsir 9 scree 7 computer 2 phone >>> btree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> for (k,v) in btree.iter_items(6,9): #要求迭代6<=key<9的鍵值對(duì)數(shù)據(jù) ... print k,v ... 7 computer 8 eight >>>
- 刪除數(shù)據(jù)并返回該值:
>>.pop(key[,d]), 根據(jù)key刪除樹(shù)的數(shù)據(jù),并返回該value,但是如果沒(méi)有,并也指定了備選返回的d,則返回d,如果沒(méi)有d,則報(bào)錯(cuò);
>>.pop_item(),在樹(shù)中隨機(jī)選擇(key,value)刪除,并返回。
看例子:
>>> ctree = btree.copy() >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.pop(2) #刪除key=2的數(shù)據(jù),返回其value 'phone' >>> ctree.pop(2) #刪除一個(gè)不存在的key,報(bào)錯(cuò) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 350, in pop value = self.get_value(key) File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 557, in get_value raise KeyError(str(key)) KeyError: '2' >>> ctree.pop_item() #隨機(jī)返回一個(gè)(key,value),并已刪除之 (7, 'computer') >>> ctree BinaryTree({9: 'scree', 'github': 'qiwsir'}) >>> ctree.pop(7,"sing") #如果沒(méi)有,可以返回指定值 'sing'
- 查找數(shù)據(jù),并返回value: .set_default(key[,d]),在樹(shù)的數(shù)據(jù)中查找key,如果存在,則返回該value。如果不存在,當(dāng)指定了d,則將該(key,d)添加到樹(shù)內(nèi);當(dāng)不指定d的時(shí)候,添加(key,None). O(log(n))
看例子:
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.set_default(7) #存在則返回 'computer' >>> btree.set_default(8,"eight") #不存在,則返回后備指定值,并加入到樹(shù) 'eight' >>> btree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> btree.set_default(5) #如果不指定值,則會(huì)加入None >>> btree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> btree.get(2) #注意,.get(key)與.set_default(key[,d])的區(qū)別 'phone' >>> btree.get(3,"mobile") #不存在的 key,返回但不增加到樹(shù) 'mobile' >>> btree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
- 根據(jù)key刪除值
>>.remove(key),刪除(key,value)
>>.remove_items(keys),keys是一個(gè)key組成的list,逐個(gè)刪除樹(shù)中的對(duì)應(yīng)數(shù)據(jù)
看例子:
>>> ctree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.remove_items([5,6]) #key=6,不存在,報(bào)錯(cuò) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 271, in remove_items self.remove(key) File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove raise KeyError(str(key)) KeyError: '6' >>> ctree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.remove_items([2,7,'github']) #按照 列表中順序逐個(gè)刪除 >>> ctree BinaryTree({8: 'eight', 9: 'scree'})
##以上只是入門(mén)的基本方法啦,還有更多內(nèi)容,請(qǐng)移不到到文章開(kāi)頭的官方網(wǎng)站
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的建立實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的遍歷實(shí)例
- Python利用前序和中序遍歷結(jié)果重建二叉樹(shù)的方法
- python數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)簡(jiǎn)介
- python二叉樹(shù)遍歷的實(shí)現(xiàn)方法
- python二叉樹(shù)的實(shí)現(xiàn)實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例
- Python實(shí)現(xiàn)重建二叉樹(shù)的三種方法詳解
- Python簡(jiǎn)單定義與使用二叉樹(shù)示例
- Python二叉樹(shù)初識(shí)(新手也秒懂!)
相關(guān)文章
在dataframe兩列日期相減并且得到具體的月數(shù)實(shí)例
今天小編就為大家分享一篇在dataframe兩列日期相減并且得到具體的月數(shù)實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07Django 狀態(tài)保持搭配與存儲(chǔ)的實(shí)現(xiàn)
本文主要介紹了Django 狀態(tài)保持搭配與存儲(chǔ)的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06PyCharm+PySpark遠(yuǎn)程調(diào)試的環(huán)境配置的方法
今天小編就為大家分享一篇PyCharm+PySpark遠(yuǎn)程調(diào)試的環(huán)境配置的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-11-11Python 排序最長(zhǎng)英文單詞鏈(列表中前一個(gè)單詞末字母是下一個(gè)單詞的首字母)
這篇文章主要介紹了Python 排序最長(zhǎng)英文單詞鏈(列表中前一個(gè)單詞末字母是下一個(gè)單詞的首字母),列表中每個(gè)元素相當(dāng)于一個(gè)單詞,要實(shí)現(xiàn)列表中前一個(gè)單詞末字母是下一個(gè)單詞的首字母,并且這個(gè)鏈?zhǔn)亲铋L(zhǎng)的。感興趣的可以了解一下2020-12-12Flask??請(qǐng)求鉤子的實(shí)現(xiàn)
這篇文章主要給大家分享了Flask請(qǐng)求鉤子的實(shí)現(xiàn),在客戶端和服務(wù)器交互的過(guò)程中,有些準(zhǔn)備工作或掃尾工作需要處理,比如:在請(qǐng)求開(kāi)始時(shí),建立數(shù)據(jù)庫(kù)連接;在請(qǐng)求開(kāi)始時(shí),根據(jù)需求進(jìn)行權(quán)限校驗(yàn);在請(qǐng)求結(jié)束時(shí),指定數(shù)據(jù)的交互格式;下面來(lái)看看文章詳細(xì)介紹內(nèi)容吧2021-11-11pytorch中backward()方法如何自動(dòng)求梯度
這篇文章主要介紹了pytorch中backward()方法如何自動(dòng)求梯度問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02python threading和multiprocessing模塊基本用法實(shí)例分析
這篇文章主要介紹了python threading和multiprocessing模塊基本用法,結(jié)合實(shí)例形式詳細(xì)分析了Python中threading和multiprocessing模塊基本概念、功能、使用方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2019-07-07