类别归档：数据结构

让我们通过考虑下面的问题来理解线段树。

给定一个数组arr[0 . . . n-1]，我们要对数组执行这样的操作：

1 计算从下标l到r的元素之和，其中 0 <= l <= r <= n-1
​2 修改数组指定元素的值arr[i] = x，其中 0 <= i <= n-1

一个简单的方案是从l到r执行循环，计算给定区间的元素之和。更新值的时候，简单地令arr[i] = x。第一个操作花费O(n)的时间，第二个操作花费O ...

哈希表支持在Θ(1)时间内完成下列操作：

1) 查找
2) 插入
3) 删除

对于自平衡的二叉搜索树，比如红黑树（Red-Black Tree），平衡二叉树（AVL Tree），伸展树（Splay Tree）等，上述操作的时间复杂度是O(Logn)。

因此对于常用操作哈希表似乎完胜BST。那么我们在什么时候应该选择BST而不是哈希表，BST的优势何在。下面是BST的几项比较重要的优势。

我们只需通过中序遍历BST即可获得排好序的key列表。而这并非哈希表的自然操作，需要额外的工作才可以实现。

使用BST可以很容易地执行顺序统计，找出最接近的最小和最大元素，执行范围查询。像排序一样，这些操作也不是哈希表的自然操作。

BST相较于哈希表更容易实现，我们可以很容易地实现自定义的BST。而要实现哈希表，我们一般需要依赖编程语言提供的库函数。

使用BST，所有的操作都可以确保在O ...

Implement the reversal of a singly linked list iteratively and recursively.

链表逆置既可以用迭代实现也可以使用递归实现。在我看来，迭代法应该比其递归形式的等价实现更加高效，内存开销更小。（试想对一个包含百万个元素的链表执行递归的逆置操作!很快栈空间就会用尽）

递归实现的代码行数更少，但是要想把代码写对会比较困难。另一方面，迭代实现代码行数较多但是比较容易验证。

1) 迭代实现:

void reverse(Node*& head) {
  if (!head) return;
  Node* prev = NULL;
  Node* curr = head;
  while (curr) {
    Node ...

给定一棵二叉树，不使用递归，迭代地后序遍历并输出树中的元素

 二叉树的后序遍历很容易采用递归方式实现：

void postOrderTraversal(BinaryTree *p) {
  if (!p) return;
  postOrderTraversal(p->left);
  postOrderTraversal(p->right);
  cout << p->data;
}

后序遍历是二叉树三种遍历的非递归算法中最难实现的一种，在做这道题目之前可以首先尝试一下这一题，因为它相对简单一些：Binary Search Tree In-Order Traversal Iterative Solution。

三种遍历的非递归实现中最容易的是先序遍历。

后序遍历是一种非常有用的树操作，例如它可以被用于下面的场景：

树的删除。为了释放树结构的内存，某节点在被释放以前，其左右子树的节点首先应当被释放掉。
后缀表示法（逆波兰表示法）

如果在遍历树时维护一个visited标记，问题可以比较直观地解决。在此不详细讨论该方法 ...

由于链表（LinkedList）不支持随机访问（Random Access），只允许顺序访问，因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法，而归并排序可以满足这一需求。

归并排序是分治法（Divide and Conquer）的典型应用，其伪代码如下：

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

下面的Java代码实现了对单链表（singly linked list）的归并排序，代码实现优美 ...