《python算法教程》Day8 - 构建二分搜索树二分搜索树介绍二分搜索树创建代码

billyang916

发布于 2018-05-02 10:21:37

7480

发布于 2018-05-02 10:21:37

文章被收录于专栏：python读书笔记

今天是《python算法教程》的第8篇读书笔记，笔记的主要内容是构建二分搜索树。

二分搜索树介绍

若要对一组有序值中执行操作（如查找），二分搜索法是一个优秀的选择，因为其时间复杂度仅为对数级。但很多时候，对序列的操作不仅仅是查找，还涉及到插入新数据。若此时选用数组作为存储数据的结构，插入数据的时间复度是线性级的，显然无法满足快速插入数据的需求。因此，这里引入二分搜索树这一既能利于二分搜索又能以对数级的时间完成搜索的数据结构。

二分搜索树创建代码

二分搜索树是一个对象，其提供插入、搜索节点和判断是否存在某个节点的方法。

#构建二分搜索树

#二分搜索树的节点的自定义类
class Node:
    lft=None
    rgt=None
    def __init__(self,key,val):
        self.key=key
        self.val=val

#定义插入节点的函数
def insert(node,key,val):
    if node is None :
        return Node(key,val)
    #如插入的节点的键与已存在的键相同，则更新节点的值
    if node.key==key:
        node.val=val
    elif key<node.key:
        insert(node.lft,key.val)
    else:
        insert(node.rgt,key,val)
    return node

#从指定节点开始搜索节点
def search(node,key):
    if node is None:
        raise KeyError
    if node.key==key:
        return node.val
    if key<node.key:
        return search(node.lft,key)
    else:
        return search(node.rgt,key)

#定义二分搜索树类
class tree:
    root=None
    #
    def __setitem__(self,key,val):
        self.root=insert(self.root,key,val)
    def __getitem__(self,key):
        return search(self.root,key)
    def __contians__(self,key):
        try:
            search(self.root,key)
        except KeyError:
            return False
        return True

t=tree()
t['root']=10

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.04.19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python