专栏首页T客来了打牢地基-映射的底层实现(LinkedListMap、BSTMap)

打牢地基-映射的底层实现(LinkedListMap、BSTMap)

章节

  • 映射 Map
  • 基于链表- LinkedList 的映射实现
  • 基于二分搜索树- BST 的映射实现
  • 链表、二分搜索树实现的映射复杂度分析

1. 映射-Map 的基本形态

1.Map 是一个顶级容器,map中存储的是键值对元素,key:value
 
2.Map 中的key 不能重复
 

2. 基于链表- LinkedList 的映射实现

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/11 上午11:01
 
# @Author  : bofengliu@tencent.com
 
# @Site    :
 
# @File    : LinkedListMap.py
 
# @Software: PyCharm
 
""" 


 
class Node:
 
 def __init__(self, key=None, val=None, next=None):
 
        self.key = key
 
        self.val = val
 
        self.next = next


 
 def to_string(self):
 
 return self.key + ' : ' + self.val 


 
class LinkedListMap:
 
 def __init__(self):
 
        self._dummy_head = Node(None, None, None)
 
        self._size = 0


 
 def add(self, key, val):
 
        node = self._get_node(key)
 
 if node is None:
 
            self._dummy_head.next = Node(key, val, self._dummy_head.next)
 
            self._size += 1
 
 else:
 
            node.val = val
 
 
 def remove(self, key):
 
        prev = self._dummy_head
 
 while prev.next is not None:
 
 if prev.next.key == key:
 
 break
 
            prev = prev.next
 


 if prev.next is not None:
 
            del_node = prev.next
 
            prev.next = del_node.next
 
            del_node.next = None
 
            self._size -= 1
 
 return del_node.val
 
 return None
 


 
 def contains(self, key):
 
 return self._get_node(key) is not None
 


 
 def get(self, key):
 
        node = self._get_node(key)
 
 if node is not None:
 
 return node.val
 
 return None
 


 
 def set(self, key, new_val):
 
        node = self._get_node(key)
 
 if node is None:
 
 raise (Exception, key + " doesn't exist!")
 
        node.val = new_val
 


 
 def get_size(self):
 
 return self._size
 


 
 def is_empty(self):
 
 return self._size == 0
 


 
 def _get_node(self, key):
 
        cur = self._dummy_head.next
 
 while cur is not None:
 
 if cur.key == key:
 
 return cur
 
            cur = cur.next
 
 return None
 

注意:设置了 getnode 辅助函数, contains()、get()、set() 都会用的到

3. 基于二分搜索树- BST 的映射实现

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/11 上午11:01
 
# @Author  : bofengliu@tencent.com
 
# @Site    :
 
# @File    : BSTMap.py
 
# @Software: PyCharm
 
"""
 


 


 
class Node:
 
 def __init__(self, key=None, val=None, left=None, right=None):
 
        self.key = key
 
        self.val = val
 
        self.left = left
 
        self.right = right
 


 


 
class BSTMap:
 
 def __init__(self, root: Node = None):
 
        self._root = root
 
        self._size = 0
 


 
 def get_size(self):
 
 return self._size
 


 
 def is_empty(self):
 
 return self._size == 0
 


 
 def contains(self, key):
 
 return self._get_node(self._root, key) is not None
 


 
 def _get_node(self, node, key):
 
 """
 
        递归获取 key 对应的 node
 
        :param node:
 
        :param key:
 
        :return:
 
        """
 
 if node is None:
 
 return None
 


 
 if node.key == key:
 
 return node
 


 
 if key < node.key:
 
 return self._get_node(node.left, key)
 
 if key > node.key:
 
 return self._get_node(node.right, key)
 


 
 def add(self, key, val):
 
        self._root = self._add_element(self._root, key, val)
 


 
 def _add_element(self, root, key, val):
 
 """
 
        递归构建二分搜索树
 
        :param root:
 
        :param e:
 
        :return:
 
        """
 
 if root is None:
 
            self._size += 1
 
 """
 
            返回的是子树根节点
 
            """
 
 return Node(key, val)
 
 elif key < root.key:
 
            root.left = self._add_element(root.left, key, val)
 
 elif key > root.key:
 
 # insert
 
            root.right = self._add_element(root.right, key, val)
 
 else:
 
 # or update
 
            root.val = val
 
 return root
 


 
 def get(self, key):
 
        node = self._get_node(self._root, key)
 
 if node is None:
 
 return None
 
 return node.val
 


 
 def set(self, key, new_val):
 
        node = self._get_node(self._root, key)
 
 if node is None:
 
 raise (Exception, key + " doesn't exist!")
 
        node.val = new_val
 


 
 def _minimum(self, node: Node):
 
 """
 
        递归-找到二分搜索树中最小元素
 
        :param node:
 
        :return:
 
        """
 
 if node.left is None:
 
 return node
 
 return self._minimum(node.left)
 


 
 def _remove_minimum(self, node: Node):
 
 """
 
        删除二分搜索树中的最小节点,返回删除节点后新的二分搜索树的根
 
        :param node:
 
        :return:
 
        """
 
 if node.left is None:
 
 # 此刻已经遍历到底,当前node为已经遍历到的值
 
            right_node = node.right
 
            node.right = None
 
            self._size -= 1
 
 return right_node
 
        node.left = self._remove_minimum(node.left)
 
 return node
 


 
 def remove(self, key):
 
 """
 
        从bst 中删除元素为key的节点
 
        :param key:
 
        :return:
 
        """
 
        node = self._get_node(self._root, key)
 
 if node is not None:
 
            self._root = self._remove(self._root, key)
 
 return node.val
 
 return None
 


 
 def _remove(self, node: Node, key):
 
 """
 
        删除以node为根的BST 中节点为e的节点,递归算法
 
        返回删除节点后新的二分搜索树中的根
 
        :param node:
 
        :param key:
 
        :return:
 
        """
 
 if node is None:
 
 return None
 
 if key < node.key:
 
            node.left = self._remove(node.left, key)
 
 return node
 
 elif key > node.key:
 
            node.right = self._remove(node.right, key)
 
 return node
 
 else: # key == node.key
 
 if node.left is None:
 
                right_node = node.right
 
                node.right = None
 
                self._size -= 1
 
 return right_node
 
 if node.right is None:
 
                left_node = node.left
 
                node.left = None
 
                self._size -= 1
 
 return left_node
 


 
            del_node = node
 
 # 找到后继节点,当前被删除的右子树的最小元素
 
            next_node = self._minimum(del_node.right)
 
            next_node.right = self._remove_minimum(del_node.right)
 
            next_node.left = del_node.left
 
            del_node.left = del_node.right = None
 
 return next_node
 

注意:与之前的BST 不同,BST 的数据域e 变成了 key,val;

4. 链表、二分搜索树实现的映射复杂度分析

时间复杂度:

映射的时间复杂度.png注意:二分搜索树在最差情况下会退化成链表,解决这个问题需要用AVL树

有序映射 & 无序映射

有序映射即键是具有顺序性的->基于搜索树实现的 ,无序映射中的键是没有顺序的

本文分享自微信公众号 - T客来了(ltdo11),作者:bofeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之映射Map

    1、映射Map,存储键值数据对的数据结构(key,value),可以根据键key快速寻找到值Value,可以使用链表或者二分搜索树实现的。

    别先生
  • 数据结构之集合和映射

    本小节演示一下如何基于二分搜索树实现一个集合,我们都知道二分搜索树通常不存放重复元素,且不采用中序遍历的情况下访问元素是“无序”的(但通常基于树实现的集合是有序...

    端碗吹水
  • 6.2 集合和映射--集合Set->底层基于链表实现

    在6.1中我们实现了底层基于二叉搜索树的集合,本节就底层如何基于链表实现进行学习,注意:此处的链表是之前自己封装的.

    wfaceboss
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • 6.1 集合和映射--集合->底层基于二叉搜索树实现

    前言:在第5章的系列学习中,已经实现了关于二叉搜索树的相关操作,详情查看第5章即可。在本节中着重学习使用底层是我们已经封装好的二叉搜索树相关操作来实现一个基本的...

    wfaceboss
  • 大数据开发如何学习之Mybabits

    大数据开发有大量的基础理论需要进行切实的学习与讨论,只有将基础打牢,才能更好的将它利用起来,今天是关于大数据开发基础JAVA部分Mybatis。

    成都加米谷大数据
  • 【Java】基础27:Map集合

    Map,这个单词很多人都认识,不过第一反应应该是“地图”,其实它还有一个意思叫“映射”。

    刘小爱
  • Java程序员从京东、阿里、携程面试回来,已成功拿到京东offer

    美的让人心动
  • Java程序员从京东、阿里、携程面试回来,已成功拿到京东offer携程(一面)京东(笔试+两面技术+一面hr,拿到offer)总结

    美的让人心动
  • JAVA NIO之文件通道

    通道是 Java NIO 的核心内容之一,在使用上,通道需和缓存类(ByteBuffer)配合完成读写等操作。与传统的流式 IO 中数据单向流动不同,通道中的数...

    田小波
  • 干货!大话EXT4文件系统完整版

    我们知道SSD是一场存储革命,设计和制造一个好的SSD固然重要,但如何正确使用以充分发挥SSD性能同样重要。SSD内在的并行性和先擦再写的特性决定了它不同于机械...

    Linux阅码场
  • 国民老公的撒币游戏,互联网巨头的囊中之物

    孟永辉
  • LINQ to SQL(2):生成对象模型

    在LINQ to SQL中,可以使用自己的编程语言的对象模型映射到关系数据库,在上一节课,已经有一部分内容,简单的介绍了一下这种对象模型的结构,这一节,我们主要...

    小白哥哥
  • 大数据预测欧洲杯决赛:C罗成法国夺冠最大变数

    结论:综上可见,东道主法国不仅在纸面实力、大赛底蕴、实际战绩上占优,进攻效率和防守抢断等技战术关键数据也更为出色,葡萄牙则是低开高走,表现中规中矩。目前,媒体风...

    华章科技
  • MyBatis:基本应用

    软件开发常用的架构是三层架构,之所以流行是因为有着清晰的任务划分。一般包括以下三层:

    RendaZhang
  • 终于有人把Docker讲清楚了!

    富 Web 时代,应用变得越来越强大,与此同时也越来越复杂。集群部署、隔离环境、灰度发布以及动态扩容缺一不可,而容器化则成为中间的必要桥梁。

    架构师修炼
  • Docker 极简入门指南,10 分钟就能看懂

    富 Web 时代,应用变得越来越强大,与此同时也越来越复杂。集群部署、隔离环境、灰度发布以及动态扩容缺一不可,而容器化则成为中间的必要桥梁。本节我们就来探索一下...

    子润先生
  • 渗透测试-地基篇-隧道之Neo-reGeorg内网穿透

    建立成功隧道~接下来试试! python3 neoreg.py -k dayuxiyou -u http://192.168.175.160/tunnel...

    潇湘信安
  • 【小家MyBatis】MyBatis封装结果集时,Integer类型的id字段被赋值成了Long类型---读源码找原因

    为了追查此问题根源,本人通过复现现象、控制变量、调试源码等方式,苦心全身心投入连续查找近4个小时,终于找出端倪。现通过本文分享给大家,希望对各位有所帮助。

    YourBatman

扫码关注云+社区

领取腾讯云代金券