Basic data structure - binary tree & ADT

1 简介

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二元堆积。

二叉树的每个节点至多只有二棵子树(不存在度大于2的节点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有 2^(i−1)个节点；深度为k的二叉树至多共有 2^(k+1)−1个节点；对任何一棵二叉树T，如果其终端节点数为 n0，度为2的节点数为n2，则 n0=n2+1。

一棵深度为k，且有2^(k+1)−1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

与树不同，树的节点个数至少为1，而二叉树的节点个数可以为0；树中节点的最大度数没有限制，而二叉树节点的最大度数为2；树的节点无左、右之分，而二叉树的节点有左、右之分。

以上来自wiki百科

Classic sort

先上结果

• 插入排序

def insertionSort1(L):
    for i in range(1, len(L)):
        curV = L[i]
        pos = i
        while pos > 0 and curV < L[pos - 1]:
            L[pos] = L[pos - 1]
            pos -= 1
        L[pos] = curV #找到正确的位置插入
    return L

Naive bayesian

1 简介

朴素贝叶斯是一种构建分类器的简单方法。该分类器模型会给问题实例分配用特征值表示的类标签，类标签取自有限集合。它不是训练这种分类器的单一算法，而是一系列基于相同原理的算法：所有朴素贝叶斯分类器都假定样本每个特征与其他特征都不相关。举个例子，如果一种水果其具有红，圆，直径大概3英寸等特征，该水果可以被判定为是苹果。尽管这些特征相互依赖或者有些特征由其他特征决定，然而朴素贝叶斯分类器认为这些属性在判定该水果是否为苹果的概率分布上独立的。

对于某些类型的概率模型，在监督式学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法；换而言之，在不用到贝叶斯概率或者任何贝叶斯模型的情况下，朴素贝叶斯模型也能奏效。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。2004年，一篇分析贝叶斯分类器问题的文章揭示了朴素贝叶斯分类器取得看上去不可思议的分类效果的若干理论上的原因。尽管如此，2006年有一篇文章详细比较了各种分类方法，发现更新的方法（如提升树和随机森林）的性能超过了贝叶斯分类器。

朴素贝叶斯分类器的一个优势在于只需要根据少量的训练数据估计出必要的参数（变量的均值和方差）。由于变量独立假设，只需要估计各个变量的方法，而不需要确定整个协方差矩阵。

以上来自wiki百科。

Hash map

1 简介

字曲是python里最有用的数据集合之一。字典是一对键值-数据的组合，键值是用来查找相应的数据，我们把这种思想称为“映射”。

映射的抽象数据类型定义如下，这是一个无序的键-值对集合，键值总是唯一的以便建立与数据的对应关系。映射的操作方法如下：
***

• Map()创建一个新的空的映射，返回一个空集合。
• put(key,val)在映射中增加一对新的键-值对，如果键值已经存在，用新的数据值代替原来的。
• get(key)根据给定的键值，返回对应的数值，找不到时返回None。
• Del从映射中删除键-值对，形式del map[key]
• len()返回映射中键-值对的数量
• In如果key值在映射中，key in map返回True，否则返回False

字典的好处之一，是给一个键值可以很快返回相关的数据，为了提供这样快速查询的能力，我们需要引入一个高效的查找功能。

可以对列表使用顺序或二分查找，但是最好是用 哈希表，因为它能提供接近O(1)的性能。

Decision tree - ID3

1 简介

ID3算法（Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树的算法。
这个算法是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念：

这个ID3算法可以归纳为以下几点:

• 使用所有没有使用的属性并计算与之相关的样本熵值
• 选取其中熵值最小的属性
• 生成包含该属性的节点

还有其他决策树的构造算法，最流行的是CART和C4.5。关于ID3算法的实现可以参考C4.5算法，它同时也是ID3的升级版。

以上介绍来自维基百科。