类别归档：数据结构

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

给定一个数组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)的时间。

第二个方案是创建另外一个数组来存储从下标i开始的元素之和。这样一来，给定区间之和可以用O(1)的时间计算，但是更新需要花费O(n)的时间。这种方法适用于需要大量查询而更新操作较少的场景。

如果查询和更新的次数一样多呢？我们可以在O(log n)的时间内完成上述两种操作吗？

我们可以使用线段树来实现在O(log n)时间内完成上述两种操作。

线段树的表示：

1. ...

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

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

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

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

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

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

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

使用BST，所有的操作都可以确保在O(Logn)时间内完成，而对于哈希表， Θ(1) 是平均时间，对于某些特定的操作代价可能会比较高，尤其是当表的大小需要调整时。

英文原文：

Hash Table supports following operations in Θ(1) time.
1) Search
2) Insert
3) Delete

The time complexity of above operations in a ...

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* next = curr->next;
    curr->next = prev; ...

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

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

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标记，问题可以比较直观地解决。在此不详细讨论该方法，可以参阅Wikipedia的描述：Tree Traversal。

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null ...

由于链表（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）的归并排序，代码实现优美，可读性强，具有较高的参考价值：

// The main function
public Node merge_sort(Node head) {
    if (head == null || head.next == ...