Skip to content

Latest commit

 

History

History
161 lines (99 loc) · 8.61 KB

DataStructure.md

File metadata and controls

161 lines (99 loc) · 8.61 KB
Raw

图

树

树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0 时，称这棵树为空树。在一棵非空树T 中：

  1. 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
  2. 除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm 为这个根结点的子树（subtree）。

树具有以下特点：

  1. 每个节点有零个或多个子节点。
  2. 每个非根节点只有一个父节点。
  3. 没有父节点的节点称为根节点。

相关术语（结点、孩子结点等术语忽略）：

  • 祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
  • 结点层：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1；
  • 结点的度：结点子树的个数。

［二叉树与森林的转换］

参考：数据结构之树

二叉树

二叉树是每个节点最多有两个子树的树结构。二叉树的每个结点至多只有二棵子树，二叉树的子树有左右之分，次序不能颠倒。

图论中二叉树的定义如下：二叉树是一个连通无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。

二叉树的一些不是那么明显的性质：

  1. 对任何一棵二叉树T，度为2的结点数为m，则叶子结点数为：m＋1。
  2. 给定N个节点，能构成h(N)种不同的二叉树，其中h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

几种常用的二叉树：

  • 满二叉树：一棵深度为k，且有2^k - 1个节点的二叉树称为；

  • 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时。

  • 二叉堆：它一棵完全的二叉树，二叉堆一般分为两种：最大堆和最小堆。

    • 最大（小）堆中的最大（小）元素值出现在根结点（堆顶）；
    • 堆中每个父节点的元素值都大（小）于等于其孩子结点（如果存在）。

  • 二叉排序树：是一棵空树，或者是具有下列性质的二叉树：

    • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 左、右子树也分别为二叉排序树；
    • 没有键值相等的节点。

  • 平衡二叉树（AVL树）：它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

参考：
轻松搞定面试中的二叉树题目
卡特兰数

树与二叉树的转换

如果设定一定规则，就可用二叉树结构表示树，这样对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。

树转换为二叉树：将一棵树转换为二叉树的方法是：

  • 树中所有相邻兄弟之间加一条连线。
  • 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。
  • 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。

二叉树转换为树或森林的过程如下：

  • 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来；
  • 删去原二叉树中所有的双亲结点与右孩子结点的连线；
  • 整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。

参考：树、森林与二叉树的转换

红黑树

红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除等操作。

详细内容参见：DataStructure_RB_Tree

Hashtable

哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即 key，即可查找到其对应的值。

哈希查找第一步就是使用哈希函数将键映射成索引，这种映射函数就是哈希函数。如果我们有一个保存0-M数组，那么我们就需要一个能够将任意键转换为该数组范围内的索引（0~M-1）的哈希函数。哈希函数需要易于计算并且能够均匀分布所有键。一个好的哈希函数必须在理论上非常的快、稳定并且是可确定的。

哈希函数通常是由他们产生哈希值的方法来定义的，有两种主要的方法：

  1. 基于加法和乘法的散列：这种方式是通过遍历数据中的元素然后每次对某个初始值进行加操作，其中加的值和这个数据的一个元素相关。通常这对某个元素值的计算要乘以一个素数。
  2. 基于移位的散列：和加法散列类似，基于移位的散列也要利用字符串数据中的每个元素，但是和加法不同的是，后者更多的而是进行位的移位操作。通常是结合了左移和右移，移的位数的也是一个素数。每个移位过程的结果只是增加了一些积累计算，最后移位的结果作为最终结果。

DEK：Knuth在《编程的艺术 第三卷》的第六章排序和搜索中给出一个 Hash 函数如下：

long DEKHash(string str)
{
    long hash = str.length();
    for(int i = 0; i < str.length(); i++)
    {
        hash = ((hash << 5) ^ (hash >> 27)) ^ str[i];
    }
    return hash;
}


对于两个或者多个键具有相同索引值的情况，如何有效避免hash结果值的碰撞？

  • 拉链法：将大小为M的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对。
  • 开放寻址法：使用大小为M的数组来保存N个键值对，其中M>N，使用数组中的空位解决碰撞冲突。其中最简单的是线性探测法，当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1。

为什么一般hashtable的桶数会取一个素数？

首先来说假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。

参考： 浅谈算法和数据结构: 十一 哈希表

bitmap

位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用，能同时使存储空间和速度最优化。例如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合，可以用 01110100100 表示集合 {1,2,4,5,8} ，对应位置数字存在标记为1，否则标记为0。

C 语言位图实现如下：

主要程序如下：

#define SHIFT 5  
#define MASK 0x1F  

//set 设置所在的bit位为1  
//clr 初始化所有的bit位为0  
//test 测试所在的bit为是否为1  

set(int i) {
    a[i>>SHIFT] |=  (1<<(i & MASK)); }  
clr(int i) {
    a[i>>SHIFT] &= ~(1<<(i & MASK)); }  
test(int i){
    return a[i>>SHIFT] & (1<<(i & MASK)); }

字节位置=数据/32 (采用位运算即右移5位)
位位置=数据%32 (采用位运算即跟0X1F进行与操作)。

特定适用场合：

  1. 对10亿个不重复的整数进行排序。
  2. 找出10亿个数字中重复的数字。

如果用普通的排序算法，数据放进内存就需要 ( 10^9 * 4)/( 2^30 ) = 3.7G。改用 Bitmap 的话，一个数字占一位，一共需要 3.7/32 ＝ 0.1 G 内存。

参考：详解bitmap算法