Introduction

转自http://developer.android.com/training/sync-adapters/creating-authenticator.html。

The sync adapter framework assumes that your sync adapter transfers data between device storage associated with an account and server storage that requires login access. For this reason, the framework expects you to provide a component called an authenticator as part of your sync adapter. This component plugs into the Android accounts and authentication framework and provides a standard interface for handling user credentials such as login information

引言

红黑树（Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(logN)时间内做查找，插入和删除.

有人可能觉得奇怪，已经有了AVL这种查找，插入和删除都严格为O(logN)复杂度的平衡二叉树，为什么还需要红黑树呢？

引言

我们知道AVL树为了保持严格的平衡，所以在数据插入上会呈现过多的旋转，影响了插入和删除的性能。从访问量上，我们知道许多应用场景都有一个“二八原则“，也就是说80%的人只会用到20%的数据，比如说我们的用的输入法，平常打的字也就那么多，或许还没有20%呢。右比如新闻消息，热门消息的访问量是远远大于普通消息的。

所以如果让经常被访问的节点更靠近根，则平均访问速度要快很多。则就是伸展树(Splay Tree)的思想。

引言

前面说过，二叉查找树有可能退化为链表，所以前辈们想尽了各种优化策略，包括AVL，红黑，以及今天要讲的Treap树。Treap树是一种简单的优化策略，从名字也可以猜到(Treap=Tree+Heap)，它是树和堆的合体。实原理很简单，在树中维护一个”优先级“，”优先级“采用随机数的方法生成，但是”优先级“必须满足根堆的性质，当然是“大根堆”或者“小根堆”都无所谓，比如下面的一棵树

引言

前面一篇博客中我们讲到二叉查找树的评价查找效率可达到O(logN)，但是它在最坏情况下的查找效率可能退化为O(N),如下所示

引言

二叉查找树的定义:左孩子比父节点小,右孩子比父节点大的二叉树。
显然,通过中序遍历可得到从小到大的序列,因而二叉查找树常用于快速查找,排序等场合。
下图就是一棵典型的二叉查找树

引言

二叉树的Java实现

之前有两篇博客是利用C++实现了二叉树的各种常用操作，这里提供二叉树常用操作的Java实现。
其实如果不追求空间最小，那么就不必非要采用数组实现，而是直接利用Java中的Stack去实现。只要利用Stack后进先出的特性，就可以很好地实现各种非递归算法

引言

这篇打算在翻译developer上相关文章[http://developer.android.com/training/camera/photobasics.html]的基础上在添加一些东西。
原文如下：

Taking Photos Simply
This lesson explains how to capture photos

引言

由于现在手机像素越来越高，800万像素的手机，拍出来的照片就有2M左右,这么大的图片，如果用来直接显示的话，只要多几张，很容易就会发生OOM,但是用Thumbnail的话又不够清晰，所以需要对图片进行压缩之后在进行上传或显示。

对图片压缩并上传分三个部分:

第一,计算图片的缩放值

阅读全文 »

1.思想

1.1 二叉堆

二叉堆满足两个特性：
1)父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值;
2)每个结点的左子树和右子树都是一个二叉堆

当父结点的键值总是大于或等于任何一个子结点的键值时为最大堆;反之为最小堆。
下图是一个最小堆的示意图