# 现代编程思想 树 Hongbo Zhang ## 数据结构：树 • 树 · 二叉树 • 二叉搜索树 • 二叉平衡树 ## 生活中的树状图 - 生活中有很多的数据的结构与一颗树相似 - 谱系图（又称，家族树） ☐ 文件结构 ☐ 数学表达式  ## 树的逻辑结构 • 数据结构中，树是由有限个节点构成的具有层次关系的集合 ◦ 节点是存储数据的结构，节点之间存在亲子关系：父节点和子节点 如果树不为空，则它拥有一个根节点：根节点没有父节点 所有非根节点都有唯一的父节点 如果没有子节点的节点可称为叶节点 ☐ 任何节点不能是自己的后代节点：树中不能有环路 ☐ 树的一条边指的是一对节点 $ (u, v) 0/b0908fa36dacc9f916e5bf9d9fe29bf7/p4_2.jpg) ## 树的逻辑结构 • 这不是一颗树  ## 树的逻辑结构 - 计算机中的树根节点在上，子节点在父节点下方 • 相关术语 节点的深度：根节点下到这个节点的路径的长度（边的数量）

## 机器学习-决策树 黄海广 副教授 2023年06月 ## 本章目录 01 决策树原理 02 ID3算法 03 C4.5算法 04 CART算法 ### 1. 决策树原理 01 决策树原理 02 ID3算法 03 C4.5算法 04 CART算法 ### 1. 决策树原理  ● 决策树：从训练数据中学习得出一个树状结构的模型。 ● 决策树属于判别模型。 ● 决策树是一种树状结构，通过做出一系列决策（选择）来对数据进行划分，这类似于针对一系列问题进行选择。 ● 决策树的决策过程就是从根节点开始，测试待分类项中对应的特征属性，并按照其值选择输出分支，直到叶子节点，将叶子节点的存放的类别作为决策结果。 ### 1. 决策树原理  - 决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘出有用的规则，用于对新数据进行预测。 ● 决策树算法属于监督学习方法。 ● 决策树归纳的基本算法是贪心算法，自顶向下来构建决策树。 ● 贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 ● 在决策树的生成过程中，分割方法即属性选择的度量是关键。 ### 1. 决策树原理 ## 决策树的特点 ## 优点：

## 机器学习-KNN算法 黄海广 副教授 2021年04月 ## 本章目录 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 ### 1. 距离度量 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 ## 距离度量 欧氏距离(Euclidean distance) 电影分类 ^{2}}\times\sqrt{\sum_{i=1}^{n}(B_{i})^{2}}} $$ ### 2. KNN算法 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 ### 2. KNN算法 k近邻法（k-Nearest Neighbor, kNN）是一种比较成熟也是最简单的机器学习算法，可以用于基本的分类与回归方法。 算法的主要思路： ### 3 \. K\-D\-Tree划分 01 距离度量 02 KNN算法 03 KD树划分 04 KD树搜索 ## KD树划分 KD树(K-Dimension Tree)，，也可称之为K维树，可以用更高的效率来对空间进行划分，并且其结构非常适合寻找最近邻居和碰撞检测。 假设有 6 个二维数据点，构建KD树的过程： $ D=\left\{(2,3),(5,7),(9,6),(4,5),(6

几乎每一件平凡或令人惊叹的事物背后，都隐藏着精妙的算法思想。 同样，数据结构无处不在：大到社会网络，小到地铁线路，许多系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球简则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-k 问题 8.4 小结 第9章 图 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 n 皇后问题 13.5 小结

給定某節點，獲取它的值、左（右）子節點、父節點。 · 獲取前序走訪、中序走訪、後序走訪、層序走訪序列。 /// == File: array_binary_tree.rs === /* 阵列表示下的二元树類別 */ struct ArrayBinaryTree { tree: Vec>, } impl ArrayBinaryTree { /* 建構子 */ |插入元素|$ O(1) $|$ O(\\log n) $| |刪除元素|$ O(n) $|$ O(\\log n) $| |無序陣列|二元搜尋樹| |---|---| ||| 在理想情况下，二元搜寻树是“平衡”的，这样就可以在 $ \log n $ 輪迴圈內查詢任意節點。 然而，如果我們在二元搜尋樹中不斷地插入和刪除節點，可能導致二元樹退化為圖7-23所示的鏈結串列，這時各種操作的時間複雜度也會退化為 初始化的字串都儲存在字串常數池中，它們指向同一個物件，因此也可以用 a == b 來比較兩個字串的內容。 Q：廣度優先走訪到最底層之前，佇列中的節點數量是 $ 2^{h} $ 嗎？ 是的，例如高度 h = 2 的满二元树，其節點總數 n = 7 ，則底層節點數量 $ 4 = 2^{h} = (n + 1)/2 $ 。 ## 第 8 章 堆積 ## 堆積 ![Image](/uploads/documents/

几乎每一件平凡或令人惊叹的事物背后，都隐藏着精妙的算法思想。 同样，数据结构无处不在：大到社会网络，小到地铁线路，许多系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球简则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-k 问题 8.4 小结 第9章 图 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 n 皇后问题 13.5 小结

## TokuDB索引结构 网易杭州研究院---胡争（博客：openinx.github.io） ## TokuDB简介 - 基于分形树实现的MySQL存储引擎 • Tokutek公司2007年研发，2013年开源 • 2015年Percona公司收购Tokutek公司 • TokuDB内部的K-V存储引擎为ft-index • TokuMx: ft-index + MongoDB Server层代码 TokuDB特点 - 支持事务（ACID）的MySQL存储引擎 • 插入性能大大高于InnoDB（分形树vs B+树） • 查询性能略低于InnoDB - 在线执行DDL操作（不阻塞写操作） • 超高压缩率（TokuDB 4M vs InnoDB 16K） 更高性能，更低成本！ ## 分形树索引结构（一）  ## 分形树结构（二） • msg buffer - 先进先出队列 • BasementNode (OMT) - 弱平衡二叉树 – 增删改查期望复杂度 $ O(\log N) $ • 页大小默认4M。 - 扇出fanout默认 $$ 4,16 $$ 区间。 ## 分形树结构（三） ## • 叶子节点 - 数据量维持在

5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-K问题 8.4 小结 第9章 图 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 N皇后问题 13.5 小结 本书主要内容如图 0-1 所示。 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示例等。 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 · 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、示例题目等。 ![Ima