精华内容
下载资源
问答
  • 描述众所周知,合并果子是堆的入门题,而 合并果子就是构造哈夫曼树。现在问题就是,在给定有序的数组aa下,如何O(n)O(n)构造哈夫曼树。算法使用两个队列,从小到大将数组aa的元素加入队列firfir,队列secsec为空。...

    描述

    众所周知,合并果子是堆的入门题,而 合并果子就是构造哈夫曼树。现在问题就是,在给定有序的数组 a 下,如何O(n)构造哈夫曼树。

    算法

    使用两个队列,从小到大将数组 a 的元素加入队列fir,队列 sec 为空。

    每次我们将两个元素合并,可以证明一定是三种之一。

    1. 队列 fir 中的队首和第二位合并
    2. 队列 sec 中的队首和第二位合并
    3. 队列 fir 中的队首和 sec 中的队首合并

    优先考虑合并的两个数的和较小的情况。

    将每次合并完的数放入 sec 队列,直到 sec 队列只有一个元素,结束算法。

    展开全文
  • 声明:本帖子专为个人面试所写,本身只是... 时间复杂度:计算规则常见时间复杂度常见时间复杂度比较List常见内置操作的时间复杂度Dict常见内置操作时间复杂度:二. 顺序表:定义存储方式三. python中的顺序表(列...

    03fe2d218434b2700f21275c977851ca.png

    声明:本帖子专为个人面试所写,本身只是为了加深自己的记忆,写完想着分享出来万一有人也需要呢。所以内容较浅,也比较基础,大佬们请绕道!参考链接在最后!不够看的可以看视频,老师讲的很好,就是有点浅,不过对于新手很友好!


    目录:

    一. 时间复杂度:

    1. 计算规则
    2. 常见时间复杂度
    3. 常见时间复杂度比较
    4. List常见内置操作的时间复杂度
    5. Dict常见内置操作时间复杂度:

    二. 顺序表:

    1. 定义
    2. 存储方式

    三. python中的顺序表(列表):里面一系列操作及时间比较

    四. 链表:

    1. 为什么需要链表
    2. 链表的多种形式
    3. 链表与顺序表的时间复杂度比较
    4. 主要需要掌握的操作

    五. 栈:

    六. 队列:

    七. 双端队列:

    八. 排序算法:(包括定义,步骤,实现代码,时间复杂度及个人理解)

    1. 冒泡排序
    2. 选择排序
    3. 插入排序
    4. 快速排序
    5. 希尔排序
    6. 归并排序
    7. 常见排序算法时间复杂度比较

    九. 树结构:

    1. 树的概念
    2. 树的术语
    3. 树的种类
    4. 树的存储

    十. 二叉树:

    1. 完全二叉树
    2. 满二叉树
    3. 二叉树的节点和树的创建及添加节点
    4. 树的遍历
    5. 树的广度优先遍历
    6. 树的深度优先遍历

    正文:

    一. 时间复杂度(关于算法不得不提的东西):

    • 计算规则:
    1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
    2. 顺序结构,时间复杂度按加法进行计算
    3. 循环结构,时间复杂度按乘法进行计算
    4. 分支结构,时间复杂度取最大值
    5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    • 常见时间复杂度:

    b138fefc1871c1112a56fe3eab99e081.png
    • 常见时间复杂度的关系:

    ac121997b4a18ffd4fda79258d7eabdf.png
    • List常见内置操作的时间复杂度:
    1. 列表的索引,给指定索引赋值,在末尾添加元素,在末尾弹出元素,时间复杂度都为O(1),因为都是直接一步到位的找到所需元素。
    2. 从任意位置弹出/插入/删除元素,判断是否在列表中,删除某一段切片,反转整个列表,时间复杂度都为O(n),因为所有这些操作看似只有一步,但其内部影响着每一个元素。
    3. 切片操作取决于切片的长度所以是O(k)。
    4. 注意排序的时间也不短,用之前需要考虑,O(nlongn)

    7352bb876b7e288f178bb5ecd37d2079.png
    • Dict常见内置操作时间复杂度:
    1. 可以看出字典的查找,插入,获取,删除,时间复杂度都是O(1)
    2. 迭代和拷贝是O(n)

    e772e2be65b3bcc07c4f3dca6b95163f.png

    二. 顺序表:

    • 定义:将元素顺序地存放在一块连续的存储区里,切记在内存中是连续存放的
    • 存储方式:内置和外置。
      • 内置的话要求元素的存储单元大小固定相同,可以直接存放物理地址,如列表里只有一种基本数据结构
      • 外置的话是元素的存储单元大小不相同,顺序表中存放着元素的地址信息,这些地址信息链接着实际存放的数据元素,如一个列表里既有数字,又有字符串,数字

    6a2cb82dcb298a49206165da7c6f9b3e.png
    • 如上图所示,因为顺序存放的因素,列表在索引是时间复杂度为O(1),因为知道了第一个元素的地址后直接经过加法计算即可得到其他元素
    • 更详细的顺序表的两种实现方式(一体式/分离式)在这里就不继续展开了

    三. Python中的顺序表(列表):

    • 在python中列表和元素都采用的是顺序表实现的,此处总结一下list的个人需要熟记的操作,为刷题时可以灵活使用(可能一次性想不全,日后刷题时再碰到时再补充)
    • 生成列表:
      • 列表推导式:a = [i for i in range(5)]
      • list(range(5))
    • 添加元素:
      • list.append(x):在列表末尾添加元素(添加元素时速度最快)
      • list.insert(index,x):在任意位置添加元素(速度最慢)
      • list.extend():在末尾,既可只添加一个元素,也可添加一整个存储单元,即列表,元组,字符串,并将里面的元素依次拆开当作单独的元素插入列表的末尾(速度适中)
      • list1 + list2 :用+号直接链接(速度仅次于append)

    c0c1f065c62c5509f81ba26cf649f1f7.png
    • 删除元素(三者速度差不多):
      • del list[0]:删除指定位置元素
      • list.remove('a'):删除某元素,注意如果有多个相同元素在列表中,删除时是从头开始删除,一次删除一个,若不存在该元素则报错
      • a = list.pop(0):删除指定位置元素,并返回

    344d9652271c1deb397fcc41da3dceef.png
    • 列表切片(格式为[start:end:step])
      • list[:]:以列表形式输出,代表截取全部内容,可以用来将一个列表拷给另一个列表
      • list[::-1]:反向索引,相当于反转列表
      • 并非在原列表上操作,切片相当于创建一个新的列表
    • 列表元素查找:
      • list.index('a'):若该值在列表中则返回索引,否则报错
      • 'a' in list:返回布尔值
    • 列表排序:
      • list.sort():对原列表进行排序,直接改变原列表,默认为升序,里面有个参数reverse,如果改成reverse=True则变为升序排序
      • sorted(list):对list进行排序,返回一个新的排序后的list,这点于上面区分
    • 列表反转(仅是反转,并非排序):
      • list.reverse():在原列表上操作
      • reversed(list):这里有点不同,这里生成一个新的迭代器,而非列表
      • list[::-1]:用切片也可以操作,返回一个新列表
    • 列表的enumerate:
      • for i,j in enumerate(list):其中i为索引,j为元素
    • 列表拷贝:
      • list.copy():两种方式相同
      • list[:]:两种方式相同
    • 其他(后续慢慢补充):
      • zip函数:
        • >>>a = [1,2,3]
        • >>> b = [4,5,6]
        • >>> c = [4,5,6,7,8]
        • >>> zipped = zip(a,b)# 打包为元组的列表[(1, 4), (2, 5), (3, 6)]
        • >>> zip(a,c)# 元素个数与最短的列表一致[(1, 4), (2, 5), (3, 6)]
        • >>> zip(*zipped)# 与 zip 相反,*zipped 可理解为解压,返回二维矩阵式[(1, 2, 3), (4, 5, 6)]
      • ''.join(list):将list里的字符元素,按照join前那个字符拼接,例如:
        • c = ['1','2','3','4']
        • '-'.join(c)
        • 得到:'1-2-3-4'
      • list.count(x):统计列表中某元素的次数

    四. 链表:

    • 为什么需要链表:顺序表的构建需要预先知道数据大小来申请连续的存储空间, 而在进行扩充时又需要进行数据的搬迁, 所以使用起来并不是很灵活。使用链表的话,如果某个数据因为太大存不下,可以放在其他位置,用链表串起来
    • 链表有多种形式:单向链表,双向链表,单向循环链表等
    • 链表与顺序表时间复杂度比较:

    c029b84a3812ab98f87eb053880e1c95.png
    • 主要需要掌握的操作(详细内容后面有空了附上代码):
      • 遍历链表(由于链表的数据结构,基本每个操作都需要遍历):
      • 头部插入元素
      • 尾部插入元素
      • 任意位置插入元素
      • 删除元素

    五. 栈:

    • 定义:栈( stack), 有些地方称为堆栈, 是一种容器, 可存入数据元素、 访问元素、 删除元素, 它的特点在于只能允许 在容器的一端(称为栈顶端指标, 英语: top) 进行加入数据(英语: push) 和输出数据(英语: pop) 的运算。 没有了位置概念, 保证任何时候可以访问、 删除的元素都是此前最后存入的那个元素, 确定了一种默认的访问顺序。
    • 用一句话概括:进出口是同一个口,所有元素保证先进后出。

    ddacc22a546a506b5a8f37d21b1a684f.png
    • 栈可以用链表或者顺序表实现,一般python中用顺序表的列表实现栈的操作。
    • 需要掌握的操作:
      • Stack() 创建一个新的空栈
      • push(item) 添加一个新的元素item到栈顶
      • pop() 弹出栈顶元素
      • peek() 返回栈顶元素
      • is_empty() 判断栈是否为空
      • size() 返回栈的元素个数

    六. 队列:

    • 定义:与栈不同,保持先进先出,像排队一样,不允许在中间操作元素,即不允许插队

    f04c6e146bfcefbe1c0103074078a950.png
    • 实现:和栈一样,也可以用顺序表或链表实现,在python中,通常也是用列表来实现队列
    • 需要掌握的操作:
      • Queue() 创建一个空的队列
      • enqueue(item) 往队列中添加一个item元素
      • dequeue() 从队列头部删除一个元素
      • is_empty() 判断一个队列是否为空
      • size() 返回队列的大小

    七. 双端队列:

    • 定义:是一种具有队列和栈的性质的数据结构,双端队列中的元素可以从两端弹出, 其限定插入和删除操作在表的两端进行。 双端队列可以在队列任意一端入队和出队。

    e9ddd3132f4f267b7ddf938717124054.png
    • 实现:同上面两个
    • 需要掌握的操作:
      • Deque() 创建一个空的双端队列
      • add_front(item) 从队头加入一个item元素
      • add_rear(item) 从队尾加入一个item元素
      • remove_front() 从队头删除一个item元素
      • remove_rear() 从队尾删除一个item元素
      • is_empty() 判断双端队列是否为空
      • size() 返回队列的大小

    八. 排序算法:

    1. 冒泡排序:

    • 定义:冒泡排序(英语: Bubble Sort) 是一种简单的排序算法。 它重复地遍历要排序的数列, 一次比较两个元素, 如果 他们的顺序错误就把他们交换过来。 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序 完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
    • 具体操作流程:
      • 比较相邻的元素。 如果第一个比第二个大(升序) , 就交换他们两个。
      • 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对。 这步做完后, 最后的元素会是最大的数。
      • 针对所有的元素重复以上的步骤, 除了最后一个。
      • 持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较。

    6cf051dc72cd48c29b89a5ab36e6b8da.png
    • 代码

    5d98ea66db6324d9d167ac66d487f747.png
    • 时间复杂度:
      • 最优时间复杂度: O(n) (表示遍历一次发现没有任何可以交换的元素, 排序结束。 )
      • 最坏时间复杂度: O(n^2) (需要两个循环,一个确保每个元素都操作一遍,一个确保从头走到尾)
      • 稳定性: 稳定

    2. 选择排序:

    • 定义:它的工作原理: 首先在未排序序列中找到最小(大) 元素, 存放到排序序列的起始位置, 然后, 再从剩余未排序元素中继续寻找最小(大) 元素, 然后放到已排序序列的末尾。 以此类推, 直到所有元素均排序完毕。

    bdfe14e292022b203efbeb79e797ae7d.png
    • 优点:如果某个元素位于正确的最终位置上, 则它不会被移动。 选择排序每次交换 一对元素, 它们当中至少有一个将被移到其最终位置上, 因此对n个元素的表进行排序总共进行至多n-1次交换。 在 所有的完全依靠交换去移动元素的排序方法中, 选择排序属于非常好的一种。
    • 个人理解:可以想象把一个列表分成了两部分,一部分是未排序的,一部分是已经排序好的,每次从未排序的里面找出最大或最小,然后放在已排序好的末尾(挨着放)。在写代码时,每次要先记录下来这次要找的元素应该放在什么位置,然后遍历一遍列表,找到最大或最小的元素,与记录下来的位置交换,然后变更记录下来的位置,下次遍历时,不必再遍历已经排序好的部分。
    • 代码:

    2a237a910a14328b9caeb93fcf25291c.png
    • 时间复杂度:
      • 最优时间复杂度: O(n^2)
      • 最坏时间复杂度: O(n^2)
      • 稳定性: 不稳定(考虑升序每次选择最大的情况)

    3. 插入排序:

    • 定义:工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入。 插入排序在实现上, 在从后向前扫描过程中, 需要反复 把已排序元素逐步向后挪位, 为最新元素提供插入空间。

    0072fcfb2032ecdee9fc81ca2ddc9be3.png
    • 个人理解:和选择排序很像,选择排序是每次先在无序中选出最大或最小直接放在已排序好的后面;插入排序不选择,直接遍历整个数组,遍历到一个就把该元素插入到已排序好的部分里,插入到哪,取决于该元素和已排序好的元素之间的大小关系。
    • 代码:

    5c3947f061ac6ab350f4793991eabfe4.png
    • 时间复杂度:
      • 最优时间复杂度: O(n) (升序排列, 序列已经处于升序状态)
      • 最坏时间复杂度: O(n^2)
      • 稳定性: 稳定

    4. 快速排序:

    • 定义:通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分 别进行快速排序, 整个排序过程可以递归进行, 以此达到整个数据变成有序序列。
    • 步骤:
      • 从数列中挑出一个元素, 称为"基准"(pivot)
      • 重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面(相同的数可以到任一边) 。 在这个分区结束之后, 该基准就处于数列的中间位置。 这个称为分区(partition) 操作。
      • 递归地(recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序。

    4937589b4a348bb4d905144fc57f0991.png
    • 代码:

    019e3ae7dc5e7b93808b564a8f3e0ae0.png

    2538028073772065695af036f5575d1d.png

    时间复杂度:

      • 最优时间复杂度: O(nlogn)
      • 最坏时间复杂度: O(n^2)
      • 稳定性: 不稳定

    5. 希尔(shell)排序:

    • 定义:是插入排序的一种。 也称缩小增量排序, 是直接插入排序算法的一种更高效的改进版本。 希尔 排序是非稳定排序算法。 该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至1时, 整个文件恰被分成一组, 算法便终止。
    • 基本思想:将数组列在一个表中并对列分别进行插入排序, 重复这过程, 不过每次用更长的列(步长 更长了, 列数更少了) 来进行。 最后整个表就只有一列了。 将数组转换至表是为了更好地理解这算法, 算法本身还 是使用数组进行排序。

    9742e1a0cd5dfcf7a838de82ed6e5a5c.png
    • 代码:

    17bc6bac1dcb098f6723eee9bc805bd6.png
    • 时间复杂度:
      • 最优时间复杂度: 根据步长序列的不同而不同
      • 最坏时间复杂度: O(n^2)
      • 稳定想: 不稳定

    6. 归并排序:

    • 定义:归并排序是采用分治法的一个非常典型的应用。 归并排序的思想就是先递归分解数组, 再合并数组。 将数组分解最小之后, 然后合并两个有序数组, 基本思路是比较两个数组的最前面的数, 谁小就先取谁, 取了后相应的指针就往后移一位。 然后再比较, 直至一个数组为空, 最后把另一个数组的剩余部分复制过来即可。
    • 个人理解:先拆后合并,拆成每个都只有一个元素,合的时候就按大小排序(借助两个游标)。主要思想:先拆后合,合的时候排序。
    • 代码:

    6ebbe2b2b4c63c9e3c3594dab0a5427b.png
    • 时间复杂度:
      • 最优时间复杂度: O(nlogn)
      • 最坏时间复杂度: O(nlogn)
      • 稳定性: 稳定

    8. 常见排序算法比较:

    e9b7dc98c49358eb9d478db440d724a1.png

    九. 树结构:

    1. 树的概念:树(英语: tree) 是一种抽象数据类型(ADT) 或是实作这种抽象数据类型的数据结构, 用来模拟具有树状结构性 质的数据集合。 它是由n(n>=1) 个有限节点组成一个具有层次关系的集合。 把它叫做“树”是因为它看起来像一棵 倒挂的树, 也就是说它是根朝上, 而叶朝下的。 它具有以下的特点:
    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外, 每个子节点可以分为多个不相交的子树

    2. 树的术语:

    • 节点的度: 一个节点含有的子树的个数称为该节点的度;
    • 树的度: 一棵树中, 最大的节点的度称为树的度;
    • 叶节点或终端节点: 度为零的节点;
    • 父亲节点或父节点: 若一个节点含有子节点, 则这个节点称为其子节点的父节点;
    • 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点;
    • 兄弟节点: 具有相同父节点的节点互称为兄弟节点;
    • 节点的层次: 从根开始定义起, 根为第1层, 根的子节点为第2层, 以此类推;
    • 树的高度或深度: 树中节点的最大层次;
    • 堂兄弟节点: 父节点在同一层的节点互为堂兄弟;
    • 节点的祖先: 从根到该节点所经分支上的所有节点;
    • 子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。
    • 森林: 由m(m>=0) 棵互不相交的树的集合称为森林;

    3. 树的种类:

    • 无序树: 树中任意节点的子节点之间没有顺序关系, 这种树称为无序树, 也称为自由树(没有什么研究的意义);
    • 有序树: 树中任意节点的子节点之间有顺序关系, 这种树称为有序树;
      • 二叉树: 每个节点最多含有两个子树的树称为二叉树;
        • 完全二叉树: 对于一颗二叉树, 假设其深度为d(d>1)。 除了第d层外, 其它各层的节点数目均已达最大值, 且第d层所有节点从左向右连续地紧密排列, 这样的二叉树被称为完全二叉树, 其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
        • 平衡二叉树(AVL树) : 当且仅当任何节点的两棵子树的高度差不大于1的二叉树;
        • 排序二叉树(二叉查找树(英语: Binary Search Tree) , 也称二叉搜索树、 有序二叉树) ;
      • 霍夫曼树(用于信息编码) : 带权路径最短的二叉树称为哈夫曼树或最优二叉树;
      • B树: 一种对读写操作进行优化的自平衡的二叉查找树, 能够保持数据有序, 拥有多余两个子树

    4. 树的存储:

    顺序存储: 将数据结构存储在固定的数组中, 然在遍历速度上有一定的优势, 但因所占空间比较大, 是非主流二叉树。 二叉树通常以链式存储

    f506ba4461da562be667d37b5a75d3bd.png

    c38a5bda07ee70eb1dfcbc9600727cef.png

    十. 二叉树(每个节点至多有两个子树)

    1. 完全二叉树:

    566f8233e7e8a8ff4073d0f9d776bd0e.png

    2. 满二叉树:

    74ac4886d10bcab964dab404389070f2.png

    3. 节点及树的创建

    1bcefcf47a669fd209392f88a7db7e3d.png

    树的创建及给树添加元素

    44ef7bd4c6421752af8a89c58293f631.png

    5. 树的遍历:

    • 广度优先遍历:用队列实现
    • 深度优先遍历:用递归实现(一般情况下能用递归实现的算法也能用堆栈实现)

    4. 树的广度优先遍历(层次遍历):

    • 从树的root开始, 从上到下从从左到右遍历整个树的节点

    920dff1e9d1a1c54fd58b8f553779b6e.png

    5. 树的深度优先遍历:

    • 定义:对于一颗二叉树, 深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点, 尽可能深的搜索树的分支。 那么深度遍历有重要的三种方法。 这三种方式常被用于访问树的节点, 它们之间的不同在于访问每个节点的次序不同。 这三种遍历分别叫做先序遍历(preorder) , 中序遍历(inorder) 和后序遍历(postorder)。
    • 先序遍历:在先序遍历中, 我们先访问根节点, 然后递归使用先序遍历访问左子树, 再递归使用先序遍历访问右子树 根节点->左子树->右子树

    45644f973aeed7d5b55b0b3d5aec8e67.png
    • 中序遍历:在中序遍历中, 我们递归使用中序遍历访问左子树, 然后访问根节点, 最后再递归使用中序遍历访问右子树 左子树->根节点->右子树

    332e82a0fc727f0132ed215dc3effbb4.png
    • 后续遍历:在后序遍历中, 我们先递归使用后序遍历访问左子树和右子树, 最后访问根节点 左子树->右子树->根节点

    70840584e100ca46f1d8e07c9e52f8bd.png

    十一. Reference:

    内容大部分都来源于视频,只有部分是自己的理解和总结,觉得我写的不够看的可以看视频~老师讲的很好!

    python算法与数据结构

    展开全文
  • 计算机科学中的在计算机科学中,(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。...

    计算机科学中的树

    在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点都只有有限个子节点或无子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;
    • 树里面没有环路(cycle)

    a6f90daa4b5e3790f85afb4ed4083972.png

    为什么需要树?

    因为它结合了另外两种数据结构的优点: 一种是有序数组,另一种是链表。在树中查找数据项的速度和在有序数组中查找一样快, 并且插入数据项和删除数据项的速度也和链表一样。

    在有序数组中插入数据项太慢

    假设数组中的所有数据项都有序的排列—这就是有序数组,用二分查找法可以在有序数组中快速地查找特定的值。

    二分查找法的过程是先査看数组的正中间的数据项,如果那个数据项值比要找的大,就缩小査找范围,在数组的后半段中找;如果小, 就在前半段找。反复这个过程,查找数据所需的时间是O(logN)。同时也可以迅速地遍历有序数组, 按顺序访问每个数据项。

    然而,想在有序数组中插入一个新数据项,就必须首先査找新数据项插入的位置,然后把所有 比新数据项大的数据项向后移动一位,来给新数据项腾出空间。这样多次的移动很费时,平均来讲 要移动数组中一半的数据项(N/2次移动)。

    删除数据项也需要多次的移动,所以也很慢。 显而易见,如果要做很多的插入和删除操作,就不该选用有序数组。

    在链表中查找太慢

    链表的插入和删除操作都很快。它们只需要改变一些引用的值就行了。这些操作的时间复杂度是0(1)(是大O表示法中最小的时间复杂度)。

    但是在链表中查找数据项可不那么容易。查找必须从头开始,依次访问链表中的每一个数据项,把每个数据项的值和要找的数据项做比较,直到找到该数据项为止,平均需要访问N/2个数据项。这个过程很慢,费时O(N)(注意,对排序来说比较快的,对数据结构操作来说是比较慢的。)。

    我们可以通过有序的链表来加快查找速度,链表中的数据项是有序的,但这样做是没有用的。即使是有序的链表还是必须从头开始依次访问数据项,因为链表中不能直接访问某个数据项,必须通过数据项间的链式引用才可以。(当然有序链表访问节点还是比无序链表快多了,但查找任意的数据项时它也无能为力了。)

    术语

    1. 节点的度:一个节点含有的子树的个数称为该节点的度;
    2. 树的度:一棵树中,最大的节点度称为树的度;
    3. 叶节点或终端节点:度为零的节点;
    4. 非终端节点或分支节点:度不为零的节点;
    5. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
    6. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
    7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
    8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
    9. 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
    10. 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
    11. 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
    12. 节点的祖先:从根到该节点所经分支上的所有节点;
    13. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
    14. 森林:由m(m>=0)棵互不相交的树的集合称为森林;

    树的种类

    • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
    • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;  
    • 二叉树:每个节点最多含有两个子树的树称为二叉树;   
    • 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;    
    • 满二叉树:所有叶节点都在最底层的完全二叉树;   
    • 平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;   
    • 排序二叉树(二叉查找树(英语:Binary Search Tree)):也称二叉搜索树、有序二叉树;  
    • 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;   
    • B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树。

    树的抽象(ADT)

    树作为一种抽象的数据类型,至少要支持以下的基本方法

    方法名描述
    getElement()返回存放于当前节点处的对象
    setElement(e)将对象 e 存入当前节点,并返回其中此前所存的内容
    getParent()返回当前节点的父节点
    getFirstChild()返回当前节点的长子
    getNextSibling()返回当前节点的最大弟弟

    树的实现

    使用数组实现

    树可以使用数组实现,节点在数组中的位置对应于它在树中的位置。下标为0的节点是根,下标为1的节点是根的左子节点,依次类推,按从左到右的顺序存储树的每一层。

    6989058170eeda41bddb99d8fe9b1a2a.png

    树中的每个位置,无论是否存在节点,都对应数组中的一个位置。把节点插入树的一个位置, 意味着要在数组的相应位置插入一个数据项。树中没有节点的位置在数组中的对应位置用0或null来表示。

    基于这种思想,找节点的子节点和父节点可以利用简单的算术计算它们在数组中的索引值。设节点索引值为

    ,则节点的左子节点是:
    ,它的右子节点是
    ,它的父节点是

    大多数情况下用数组表示树不是很有效率。不满的节点和删除掉的节点在数组中留下了洞,浪费存储空间。更坏的是,删除节点时需要移动子树的话,子树中的每个节点都要移到数组中新的位置去,这在比较大的树中是很费时的。

    不过,如果不允许删除操作,数组表示可能会很有用。

    使用链表实现

    /**
    

    对应实现

    /**
    

    树的遍历

    所谓树的遍历(Traversal),就是按照某种次序访问树中的节点,且每个节点恰好访问一次。

    也就是说,按照被访问的次序,可以得到由树中所有节点排成的一个序列。

    前序遍历

    对任一(子)树的前序遍历,将首先访问其根节点,然后再递归地对其下的各棵子树进行前序遍历。对于同一根节点下的各棵子树,遍历的次序通常是任意的;但若换成有序树,则可以按照兄弟间相应的次序对它们实施遍历。由前序遍历生成的节点序列,称作前序遍历序列。

    845f032056cf78ee94cd1d0c637aff9a.png

    后续遍历

    对称地,对任一(子)树的后序遍历将首先递归地对根节点下的各棵子树进行后序遍历,最后才访问根节点。由后序遍历生成的节点序列,称作后序遍历序列。

    e39d71414aafc7b52eed74e8ec93a27d.png

    层次遍历

    除了上述两种最常见的遍历算法,还有其它一些遍历算法,层次遍历(Traversal by level )算法就是其中的一种。在这种遍历中,各节点被访问的次序取决于它们各自的深度,其策略可以总结为“深度小的节点优先访问”。

    对于同一深度的节点,访问的次序可以是随机的,通常取决于它们的存储次序,即首先访问由firstChild指定的长子,然后根据nextSibling确定后续节点的次序。当然,若是有序树,则同深度节点的访问次序将与有序树确定的次序一致。

    299286f74b6c5d1cf4feacf920275de9.png

    下一篇

    克己:Java数据结构:二叉树与二叉搜索树​zhuanlan.zhihu.com
    展开全文
  • 输入样例: 8 4 5 1 2 1 3 1 1 输出样例: 49 题目目的是让花费最少,而这个花费就是每次切的长度之和,而哈夫曼树是带权路径最短的树,而权正好相当于切后两块木板长度和,所以费用就是哈夫曼树中所有权之和,所以用...

    题目如下:
    农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L​i个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L​i 的总和。
    但是农夫自己没有锯子,请人锯木的酬金跟这段木头的长度成正比。为简单起见,不妨就设酬金等于所锯木头的长度。例如,要将长度为20的木头锯成长度为8、7和5的三段,第一次锯木头花费20,将木头锯成12和8;第二次锯木头花费12,将长度为12的木头锯成7和5,总花费为32。如果第一次将木头锯成15和5,则第二次锯木头花费15,总花费为35(大于32)。
    请编写程序帮助农夫计算将木头锯成N块的最少花费。
    输入格式:
    输入首先给出正整数N(≤104),表示要将木头锯成N块。第二行给出N个正整数(≤50),表示每段木块的长度。
    输出格式:
    输出一个整数,即将木头锯成N块的最少花费。
    输入样例:
    8
    4 5 1 2 1 3 1 1
    输出样例:
    49

    题目目的是让花费最少,而这个花费就是每次切的长度之和,而哈夫曼树是带权路径最短的树,而权正好相当于切后两块木板长度和,所以费用就是哈夫曼树中所有权之和,所以用需要的木板长度构建哈夫曼树,再求权和即可。

    用stl中的vector容器代替树:

    #include<bits/stdc++.h>
    using namespace std;
    #define maxlen 10000000
    int main()
    {
    	int n,a;
    	cin >> n;
    	vector<int>v;
    	while (n--)
    	{
    		cin >> a;
    		v.push_back(a);
    	}
    	int sum = 0;
    	for (;;)  //projectA代码
    	{
    		vector<int>::iterator x = min_element(v.begin(), v.end());
    		int temp1 = *x;
    		*x = maxlen;
    		vector<int>::iterator y = min_element(v.begin(), v.end());
    		if (*y == (maxlen))
    			break;
    		int temp2=*y;
    		*y = maxlen;
    		sum += temp1 + temp2;
    		v.push_back(temp1 + temp2);
    		//*y = maxlen;
    	}
    	/*	projectB代码
    	while (v.size() != 1)
    	{
    		vector<int>::iterator x = min_element(v.begin(), v.end());
    		int a = *x;
    		v.erase(x);
    		vector<int>::iterator y = min_element(v.begin(), v.end());
    		int b = *y;
    		v.erase(y);
    		sum += a+b;
    		v.push_back(a+b);
    	}*/
    	cout << sum;
    	return 0;
    }
    

    代码中第27行的*y = maxlen不能写在这个位置,只能写在第24行,因为上一行对vector进行了操作,一旦对容器操作后,之前定义的迭代器就不能再使用了,会出现 vector iterator not dereferencable 的迭代器越界,这个耽误了我很久。
    代码中29行–40行的projectB代码可以替代15行–28行projectA代码,但是vector容器是类似数组的顺序类容器,所以进行在非尾部进行增删操作时实际上会耗时较多,所以projectB中的erase函数会影响时间复杂度,而projectA中采用将使用过的元素(子节点)置为足够大的数,再用条件语句跳出循环,按理说能够更快的完成任务。但是erase函数和remove函数不同,erase函数会减少vector的长度,remove函数则是移开删除元素,不会减少长度,而两个方法中都有min_element函数,这个函数的执行时间也与vector的长度有关,时间复杂度应该O(n),所以在这里projectB又更优了,经过测试,在n即需求木板数较少时,projectA更优,而在较大时,projectB更优,以下分别是两个计划的通过时间projectA
    projectB

    展开全文
  • 举例理解哈夫曼树与哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼树
  • 排序复杂度:占用空间高的,势必会减少最差时间复杂度; 希尔排序:分组,组内直接插入排序,继续分组,组内再直接插入排序,分组依据是下标间隔,下标间隔逐渐减少到1; 哈夫曼树:就是对abcdefg编码成...
  • 本文将提到在牛客网刷题中遇到的各类知识点:线性表的概念、哈夫曼树时间复杂度等多方面知识点并赋实际题目。 目录 阅读提示 1、线性表概念 2、 哈夫曼树 3、前序遍历、中序遍历、后序遍历 4、题: 删除指针节点...
  • 哈夫曼树

    2018-07-12 20:54:00
    为什么会出现哈夫曼树? what 哈夫曼树有什么用? 什么是哈夫曼树哈夫曼树的特点是啥? how 如何创建哈夫曼树? 为什么会出现哈夫曼树? 效率!!! 比如一所高中有1000个同学进行了一次考试(总分100),现在...
  • 首先要了解哈夫曼树的一些概念: ①带权路径:每个叶子结点都有权值,对于某叶子结点来说,它的带权路径就是“结点权值*从根节点到该结点的路径长度”。 ②哈夫曼树的构造方法:两个权值最小的叶子结点作为兄弟去...
  • 哈夫曼树 - 九度教程第30题 题目: 时间限制:1 秒 内存限制:32 兆 特殊判题:否 题目描述: 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有...
  • 哈夫曼树Huff的创建

    2019-08-24 18:58:31
    哈夫曼树哈夫曼树是字符的编码,目的是为了获取最小的WPL,即最小的代价(表达能力有限,不知道咋说),顾名思义来理解吧,就是为了编码!!! 哈夫曼的创建 哈夫曼树的创建是基于堆来实现的,所以事先需要对堆有所...
  • 文章目录哈夫曼树和哈夫曼编码关于编码哈夫曼树哈夫曼编码构造哈夫曼树 哈夫曼树和哈夫曼编码 关于编码 常用编码方式 等长码:每个字符对应码字的码长都一样,例如ASCII码表中的128个字符可以用7位码长的01位串...
  • 要写k叉的哈夫曼树要克服几个条件,首先给出的数目不符合一个哈夫曼树的时候要填充0来凑数,然后一般写哈夫曼树都是使用优先队列,但是这个题卡掉了优先队列,可以根据合并的有序性来优化,使用两个队列,每次比较队...
  • 9. 树--哈夫曼树

    2017-07-12 11:04:01
    哈夫曼树(Huffman Tree)定义 带权路径长度(WPL):设二叉树有n n 个叶子结点,每个叶子结点带有权值wk w_k ,从根结点到每个叶子结点的长度为lk l_k ,则每个叶子结点的带权路径长度之和为:WPL=∑nk=1wklk WPL =...
  • 课程名称实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划、HashTable算法)课程目录01.算计概述与抽象数据类型02.算法设计目标与时间复杂度与空间复杂度03.线性结构与顺序表的实现与应用04.单向...
  • 哈夫曼树及编码

    2021-05-31 09:14:26
    哈夫曼编码:对于一颗具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的路径上,各分支的赋值分别构成一个二进制串,该二进制串就成为哈夫曼编码。 哈夫曼树满足两条性质: 性质1...
  • 九度 1172:哈夫曼树

    2017-08-29 11:47:41
    九度 1172:哈夫曼树
  • 堆和哈夫曼树

    2020-05-06 20:20:34
    最大堆的删除最大堆的建立哈夫曼树与哈夫曼编码哈夫曼树的定义哈夫曼树的构造哈夫曼树的特点哈夫曼编码 什么是堆 优先队列(Priority Queue) 特殊的“队列”,取出元素的顺序依照元素的优先权(关键字)大小,而不是...
  • 哈夫曼树 1

    2016-02-01 21:28:24
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不...
  • 建立一棵二叉链表树,分别输出此先根、中根和后根遍历序列 将上题编程,实现哈夫曼树的构建和哈夫曼编码的设计
  • 基于哈夫曼树的数据压缩算法

    千次阅读 多人点赞 2019-05-13 13:14:40
    综合实验2 基于哈夫曼树的数据压缩算法 实验日期 2019.04.29 综合实验二 基于哈夫曼树的数据压缩算法 一、实验目的 1.掌握哈夫曼树的构造算法 2.掌握哈夫曼编码的构造算法 二、实验内容 输入一串字符串,根据给.....
  • 哈夫曼树的WPL值的计算

    万次阅读 多人点赞 2019-02-22 14:11:18
    在计算WPL值的时候一般是用叶子节点的权值乘上其路径长度,但是实际上在构建哈夫曼树的过程中我们其实已经计算过路径长度了,即 WPL = 哈夫曼树中所有非叶子结点的权值之和 举个例子:构造 1 2 2 5 9的哈夫曼树并...
  • 时间复杂度和空间复杂度

    千次阅读 2016-06-10 17:19:13
    时间复杂度和空间复杂度
  • 构造二叉搜索代码实现:平衡二叉搜索(AVL)什么是平衡二叉搜索?AVL的节点数据结构AVL构造左旋右旋双旋转新增节点(背多分)LL(右旋)RR(左旋)LRRL插入节点 ,什么是是我们计算机中非常重要的...
  • c++ 构建哈夫曼树

    2020-05-08 18:55:09
    哈夫曼树是一种用来对字符进行编码的数据结构,可以根据字符的使用频率来决定字符的二进制表示,使得转化后的二进制序列尽可能短。 哈夫曼树的具体介绍见此博客用漫画介绍哈弗曼树 接下来介绍哈夫曼树的构造方法,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,864
精华内容 1,945
关键字:

哈夫曼树时间复杂度