self-balancing-binary-search-tree 0.1.4

简介

self-balancing binary search tree是一种数据结构，我可以说是一种高级的数据结构，它优化了插入、删除和搜索的时间。尽管有几种类型的sbbst（2€“3树、AA树、AVL树、B树、Red–black tree，…），但在这个库中，我决定实现AVL树，因为我认为它是最简单的一种。在

它在内存中有O（N）空间，其相应的时间和功能是：

我创建了库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

或者只是

或者直接从我的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日）

  • 第一次尝试失败

  在