自平衡二进制搜索树(AVL-tree)的Python实现。有助于练习、研究和了解SBBST的工作原理。
self-balancing-binary-search-tree的Python项目详细描述
自平衡二进制搜索树(AVL-tree)的Python实现。有助于实践、研究和了解SBBST是如何工作的。(有一个较短的版本here)。在
简介
self-balancing binary search tree是一种数据结构,我可以说是一种高级的数据结构,它优化了插入、删除和搜索的时间。尽管有几种类型的sbbst(2€“3树、AA树、AVL树、B树、Red–black tree,…),但在这个库中,我决定实现AVL树,因为我认为它是最简单的一种。在
它在内存中有O(N)空间,其相应的时间和功能是:
Time complexity | Function in the class | Action |
---|---|---|
O(1) | SBBT.getSize() | Size of the tree |
O(1) | SBBT.getHeightTree() | Height of the tree |
O(logN) | SBBT.search(x) | Search value |
O(logN) | SBBT.insert(x) | Insert value |
O(logN) | SBBT.delete(x) | Delete value |
O(logN) | SBBT.getMinVal() | Minimum value |
O(logN) | SBBT.getMaxVal() | Maximum value |
O(K+logN) | SBBT.kthsmallest(k) | Kth Minimum value |
O(K+logN) | SBBT.kthlargest(k) | Kth Maximum value |
O(N) | str(SBBT) | Visualize the tree |
我创建了库self_balancing_binary_search_tree(抱歉名称太长,虽然有一个较短的实现here),目的是让您可以轻松地将其用于您自己的项目,学习或编码竞赛(在这种情况下,我建议用Pypy而不是Python3编译程序,然后直接从Github下载代码,并根据需要进行修改)。在脸谱网黑客杯2020中,我使用了这个结构(有一些改变,可以用间隔来代替数字),而且它足够快地传递时间复杂度,虽然我建议迁移到C++(我还没有做正确的事情[SEPT 2020 ])。在
要求
- Python 2.7+或3.4+
安装
要从PyPi安装稳定版本:
~$ pip install self_balancing_binary_search_tree
或者只是
^{pr2}$或者直接从我的GitHub下载\u init_uy.py文件并使用它。在
该库使用的树节点定义为:
classTreeNode():def__init__(self,val):self.val=valself.place=0# helps in the print processself.height=1# mandatory in the AVL Treesself.left=Noneself.right=None
入门
要开始使用库,只需要2行:
>>>fromself_balancing_binary_search_treeimportSBBST>>>ST=SBBST()
这就足够开始使用它了。以下面的脚本为例
fromself_balancing_binary_search_treeimportSBBSTST=SBBST()nums=[128,131,4,134,135,10,1,3,140,14,142,145,146,147,149]# random numbersfornuminnums:ST.insert(num)# It also works out: ST = SBBST(nums)print(ST)print("Number of elements:",ST.getSize())print("Height:",ST.getHeightTree())print("Min val:",ST.getMinVal())print("Max val:",ST.getMaxVal())print("3rd smallest val:",ST.kthsmallest(3))print("2nd largest val:",ST.kthlargest(2))print("Pre Order:",ST.inOrder())print("In Order:",ST.preOrder())print("Post Order:",ST.postOrder())ST.delete(128)ST.delete(140)print(ST)ST.insert(55)print(ST)print("Number of elements:",ST.getSize())
这将是您将在终端中看到的输出:
____128_________ / \ _4 ___140___ / \ / \ 1 10 134 145___ \ \ / \ / \ 3 14 131 135 142 147 / \ 146 149 Number of elements: 15 Height: 5 Min val: 1 Max val: 149 3rd smallest val: 4 2nd lasrgets val: 145 Pre Order: [1, 3, 4, 10, 14, 128, 131, 134, 135, 140, 142, 145, 146, 147, 149] In Order: [128, 4, 1, 3, 10, 14, 140, 134, 131, 135, 145, 142, 147, 146, 149] Post Order: [3, 1, 14, 10, 4, 131, 135, 134, 142, 146, 149, 147, 145, 140, 128] ________131______ / \ _4__ ___142 / \ / \ 1 14 134 145 \ / \ \ \ 3 10 21 135 149 \ 50 __________131______ / \ _4__ ___142 / \ / \ 1 14__ 134 145 \ / \ \ \ 3 10 50 135 149 / \ 21 55 Number of elements: 14
另外,我添加了3个额外的功能(其中3个在O(N)时间内工作),以防您想在LeetCode或{a6}等平台上练习编码时使用它。(一开始,我很难想象在树和DFSs、交换或插入中发生了什么,所以我在这个库中以草图的形式工作,然后像今天一样进行改进。)在这些页面中,树的input将如下所示:
- :
- s=“1 2 3-1 4-1 5-1 6-1-1 1” s=“1,2,3,null,4,null,5,null,null,6,null,null,null” s=[1,2,3,无,4,无,5,无,无,6,无,无,无]
您可以使用以下功能:
fromself_balancing_binary_search_treeimport*# Any of the following s works out# s = "1 2 3 -1 4 -1 5 -1 -1 6 -1 -1 -1"# s = "1 2 3 None 4 None 5 None None 6 None None None"# s = "1,2,3,null,4,null,5,null,null,6,null,null,null"s=[1,2,3,None,4,None,5,None,None,6,None,None,None]head=getTree(s)print(getStr(head))print("The list of the Tree is:",getList(head))
终端输出如下:
_1 / \ 2 3_ \ \ 4 5 / 6 The list of the Tree is: [1, 2, None, 4, None, None, 3, None, 5, 6, None, None, None]
贡献
最好的学习方法是复制代码并根据自己的需要进行编辑。您还可以在我的GitHub https://github.com/Ualabi/Useful_Data_Structures中找到其他有用的数据结构。在
如果您想对此库作出贡献,请在提交请求之前查看此page。谢谢!在
更改日志
- 0.1.4(2020年9月9日)
- 第一次尝试失败
- 项目
标签: