草庐IT

树的概念

jamesnulliu 2023-03-28 原文

0. 注意事项与声明

本文摘录整理自 Data Structures, Algorithms, and Applications in C++.

作者: JamesNULLiu
邮箱: jamesnulliu@outlook.com
博客: www.cnblogs.com/jamesnulliu/

学习笔记 请注明出处 欢迎留言

1. 中英词汇对应表

  1. 树 tree
    • 二叉树 binary tree
      • 完全二叉树 complete binary tree
      • 满二叉树 full binary tree
    • 堆 heap
      • 配对堆 pairing heap
      • 区间堆 interval heap
    • 左高树 leftist tree
    • 竞赛树 tournament tree
    • AVL树 AVL tree
    • 红黑树 red-black tree
    • 伸展树 splay tree
    • 字典树/前缀树/单词查找树/键树 tries
    • 后缀树 suffix tree
  2. 结构
    • 根 root
    • 子树 subtree
    • 孩子 children
    • 双亲 parent
    • 兄弟 sibling
    • 祖先 ancestor
    • 后代 descendent
    • 叶子 leaf

2. Binary Tree

2.1. 定义

  1. [binary tree] 是一个有限个元素的集合(可以为空). 当二叉树非空, 其中一元素被称为 root, 余下元素(如果有)被划分为两棵二叉树, 分别被称为该元素的 left child 和 right child.
  2. [full binary tree] 是一棵恰好有 \(2^h-1\) 个元素的二叉树.
  3. [complete binary tree] 是除底层外为 full binary tree, 且底层结点集中于左边的树.

2.2. 性质

  1. 一棵 binary tree 有 \(n\) 个元素, 则有 \(n-1\) 条边.
  2. 一棵 binary tree 高度为 \(h\), \( h \geq 0 \), 则它最少有 \(h\) 个元素, 最多有 \(2^h-1\) 个元素.
  3. 一颗 binary tree 有 \(n\) 个元素, \(n>0\), 那么它的高度最大为 \(n\), 最小为 \(\lceil \log_2 (n+1) \rceil\).
  4. 一颗 complete binary tree 有 \(n\) 个元素, 那么它的高度为 \(\log_2 (n+1)\).
  5. 设一颗 complete binary tree 中一元素的编号为 \(i\), \(1 \leq i \leq n\), 则有以下关系:
    • 若 \(i = 1\), 则该元素为二叉树的 root; 若 \(i>1\), 则其 parent 的编号为 \(\lceil i/2 \rceil\).
    • 若 \(2i>n\), 则该元素无 left child; 否则, 其 left child 的编号为 \(2i\).
    • 若 \(2i+1>n\), 则该元素无 right child; 否则, 其 right child 的编号为 \(2i+1\).

3. Heap

3.1. 定义

  1. [max(min) tree] 一棵树, 其中每个结点的值都大于(小于)或等于其 children (如果有)的值.
  2. [max(min) heap] max(min) tree + complete binary tree.
树的的stronglitree算法与数据结构

有关树的概念的更多相关文章

  1. ruby-on-rails - 在 Rails 中需要整个目录树的好方法是什么？ - 2

    我正在使用Rails3.2.2并希望递归加载某个目录中的所有代码。例如:[Railsroot]/lib/my_lib/my_lib.rb[Railsroot]/lib/my_lib/subdir/support_file_00.rb[Railsroot]/lib/my_lib/subdir/support_file_01.rb...基于谷歌搜索，我试过:config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**"]config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**/"

  2. WebSocket的那些事（1-概念篇） - 2

    目录一、什么是Websocket二、WebSocket部分header介绍三、HTTPVSWebSocket四、什么时候使用WebSockets五、关于SockJS和STOMP一、什么是Websocket根据RFC6455标准，Websocket协议提供了一种标准化的方式在客户端和服务端之间通过TCP连接建立全双工、双向通信渠道。它是一种不同于HTTP的TCP协议，但是被设计为在HTTP基础上运行。Websocket交互始于HTTP请求，该请求会通过HTTPUpgrade请求头去升级请求，进而切换到Websocket协议。请求报文如下：GET/spring-websocket-portfoli

  3. 半个月狂飙1000亿，ChatGPT概念股凭什么？ - 2

    ChatGPT掀起了AI股历史上最疯狂的一轮市值狂飙。自春节后至今，ChatGPT概念股开始了暴走模式，短短半月时间，海天瑞声、开普云等ChatGPT概念股市值累计增加了近1400亿。如此的爆炸效应，得益于ChatGPT所展现出商业化落地的巨大潜力。要知道，在此之前，无论是十年AI投入超千亿的百度，还是困在硬件化里的AI四小龙，都在重复着AI商业化难落地的故事。ChatGPT的出现，让AI从生产力的赋能者直接成为一种创造生产力的工具。随着订阅模式的推出，ChatGPT已经成为第一个以AI技术为核心直接变现的消费者应用。本文持有以下核心观点：1、ChatGPT是AI技术迭代的受益者。过去受限技术

  4. ruby - 在 Ruby 的正则表达式中，前瞻和后视概念如何支持这种零宽度断言概念？ - 2

    我刚刚经历了这个概念Zero-WidthAssertions从文档中。我想到了一些快速的问题-为什么这样的名字Zero-WidthAssertions?Look-ahead怎么了和look-behind概念支持这样的Zero-WidthAssertions概念？什么这样的?,,=s,-4个符号在模式内指示？你能帮我集中精力了解实际发生的事情我还尝试了一些小代码来理解逻辑，但对它们的输出没有那么自信:irb(main):001:0>"foresight".sub(/(?!s)ight/,'ee')=>"foresee"irb(main):002:0>"foresight".sub(/(?

  5. 涡旋光束基本概念介绍 - 2

    涡旋光束及其MATLAB实现前言涡旋光束的基本概念常见的涡旋涡旋光束涡旋光束的产生方法前言笔者新开一块专栏，专门用于讨论整理总结涡旋光束的相关内容，从基本的概念出发，推导相关的公式，并结合MATLAB进行相关的仿真，不清楚这个专栏会更新多少期，我会分享部分的代码，全部的代码有需要的话可以私聊我。当然大家对这个专栏感兴趣的话，欢迎积极交流。涡旋光束的基本概念​涡旋光束(vortexbeam)是指携带光学涡旋，具有exp(imϕ)exp(im\phi)exp(imϕ)相位分布的光束，其中mmm表示相位拓扑电荷数，ϕ\phiϕ是柱坐标下的方位角。之前的分享中笔者已经说明了部分的激光光束的表达式，想要

  6. javascript - 针对不同浏览器的 JavaScript 中的一般单元测试概念/实践？ - 2

    我一直在用强类型语言编写单元测试，对此我有很好的理解。当用JavaScript编写单元测试以验证某些功能在某些浏览器中是否正常工作时，我又回到了手动测试。我不了解它是如何工作的。因为JavaScript旨在缩小数据和表示之间的差距，并使其更具交互性。一切都在浏览器中发生，而且更多地与UI有关。所以我假设如果我要编写单元测试，我会编写类似(伪代码)的内容:runfunctionAcheckDOMifcertainelementhasbeencreatedifnotthenfailcheckifelementisvisibleifnotthenfailcheckforthecontento

  7. 2023火爆共享购商业模式概念、框架、基础制度 - 2

    各位企业家及创业者朋友们，你们好。我是微三云（陈志坤），在你打开这个文章的时候，先不要急，因为任何一个能够长久、安稳、盈利的平台，背后肯定有一位看准宏观方向且耐心的人。这是一个极具颠覆性的模式。你慢慢的往下看，我会从框架到核心一一给你介绍，不要错过任何一个字共享购商业模式，致力于社交电商，以社交网络为核心，将自营产品和商家商品让利为切入点，带动用户的消费热情，自主创造消费，从而释放出持续不断的新消费动力，打造商业新生态的商业模式。通过可以整合各个商家入驻平台，助力线上线下新经济发展，更是还运用了新的“消费商”的概念！以下首部分为共享购模式概念、框架、和基础制度：共享购有两个概念：分别是（1）卖

  8. javascript - 有人可以向我解释这个 JavaScript 函数的流程吗？ (关闭概念) - 2

    我正在阅读“EloquentJavaScript”。第3章介绍了“Closure”的概念并给出了几个例子。其中之一是下一个:functionmultiplier(factor){returnfunction(number){returnnumber*factor;};}vartwice=multiplier(2);console.log(twice(5));//→10我想我理解了这个概念。如果我首先执行console.log(twice)，由于变量number未定义，我得到的是[Function]。我不明白的是twice(5)是如何工作的。为什么局部变量number被初始化为值5？此外

  9. Cesium 核心概念 核心接口 - 2

    Cesimum可以做什么Cesium是一个开源的3D地球可视化引擎，它可以在Web浏览器中以高性能和高质量呈现全球范围内的地球表面数据。Cesium可以用于以下领域：地理信息系统：Cesium可以呈现地球表面上的各种地理信息数据，包括卫星影像、数字高程模型、地形数据、矢量数据等。用户可以使用Cesium创建交互式的地图应用程序，从而更好地了解地球上的各种地理信息。智能城市：Cesium可以用于可视化城市规划、交通流量、气象预报、环境监测等数据。通过Cesium，用户可以更好地了解城市的运转情况，并对城市的规划、管理等方面进行决策。航空航天：Cesium可以呈现卫星轨道、星座分布、航空交通等数据

  10. Salesforce低代码平台底层架构设计原理一：多租户与元数据驱动的概念 - 2

    先自我介绍一下哈，本人拥有17年的IT服务经验。从2011年开始从事Salesforce项目咨询与实施工作。最近几年呢，我一直都在研发一些自己的产品，同时也给一些大厂提供一些咨询服务。所以我自认为对Salesforce平台的产品与功能，以及其底层的架构与设计思想还是研究得比较深的。我打算分几期的篇幅，来具体探讨一下这个平台底层架构的设计原理，其中我也会加入自己的一些思考。因为Salesforce的架构是十几年之前做的，现在的环境以及各种新技术与框架已经发生了比较大的变化。为了方便理解，我简化了一些比较复杂的概念，只保留了最核心的概念与原理。说起低代码平台，我觉得首先要讲两个原理：一个是多租户，

随机推荐