Dong | 董的博客

数据结构之后缀数组

后缀数组是一种解决字符串问题的有力工具。相比于后缀树，它更易于实现且占用内存更少。在实际应用中，后缀数组经常用于解决字符串有关的复杂问题。

数据结构之AVL树

AVL树是最早提出的自平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。本文介绍了AVL树的设计思想和基本操作。

数据结构之Treap

同splay tree一样，treap也是一个平衡二叉树，不过Treap会记录一个额外的数据，即优先级。Treap在以关键码构成二叉搜索树的同时，还按优先级来满足堆的性质。因而，Treap=tree+heap。这里需要注意的是，Treap并不是二叉堆，二叉堆必须是完全二叉树，而Treap可以并不一定是。

数据结构之伸展树

本文介绍了二叉查找树的一种改进数据结构–伸展树（Splay Tree）。它的主要特点是不会保证树一直是平衡的，但各种操作的平摊时间复杂度是O(log n)，因而，从平摊复杂度上看，二叉查找树也是一种平衡二叉树。另外，相比于其他树状数据结构（如红黑树，AVL树等），伸展树的空间要求与编程复杂度要小得多。

数据结构之块状链表

本文介绍一种新的数据结构：块状链表，它将数组和链表的优点结合来，各种操作的时间复杂度均为O(sqrt(n))。

数据结构之位图

1. 概述位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用。… 继续阅读数据结构之位图

Hadoop中TeraSort算法分析

1TB排序通常用于衡量分布式数据处理框架的数据处理能力。Terasort是Hadoop中的的一个排序作业，在2008年，Hadoop在1TB排序基准评估中赢得第一名，耗时209秒。那么Terasort在Hadoop中是怎样实现的呢？本文主要从算法设计角度分析Terasort作业。

Hadoop的调度器总结

随着MapReduce的流行，其开源实现Hadoop也变得越来越受推崇。在Hadoop系统中，有一个组件非常重要，那就是调度器，它的作用是将系统中空闲的资源按一定策略分配给作业。在Hadoop中，调度器是一个可插拔的模块，用户可以根据自己的实际应用要求设计调度器。本文介绍了Hadoop中常见的三种调度器。