Zhu Xinquan's Blog

When I was a college student and took the course Data Structure and Algorithm, the B-Tree section was not included in the exam requirement. At that time the teacher just said little about it and therefore I knew little about it. It is ridiculous that I totally understand B-Tree until last month. So what is the B-Tree? B-Trees are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices. B-Trees are similar to red-black trees. but they are better at minimizing disk I/O operations. Many database systems use B-Trees, or variants of B-Trees, to store information.

Continue reading »

Posted by Zhu Xinquan at 12:38 AM | Permalink | Comments (1)

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
A binary search tree is a red-black tree if it satisfies the following red-black properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

Continue reading »

Posted by Zhu Xinquan at 07:16 PM | Permalink | Comments (1)

Binary search tree is a binary tree in which each internal node x stores an element such that the elements stored in the left subtree of x are less than or equal to x and elements stored in the right subtree are greater than or equal to x. The following code is the class of binary search tree designed by me. I use a function pointer m_visit to construct the tree and visit the nodes of the tree. Most operations are implemented below.

Continue reading »

Posted by Zhu Xinquan at 09:03 PM | Permalink | Comments (0)

The ith order statistic of a set of n elements is the ith smallest element. For example, the minimum of a set of elements is the first order statistic (i = 1), and the maximum is the nth order statistic (i = n). The asymptotic running time of the simple problem of finding a minimum or maximum is Θ(n). Yet select the ith smallest element appears more difficult but it also only need Θ(n) time.

Continue reading »

Posted by Zhu Xinquan at 09:45 PM | Permalink | Comments (2)

Binary Tree is the most often used Data type in the programming world and is also the basis of other complex data structures. So it is very important to understand it, however it is also very easy to implement in C/C++. The follow paragraph is quoted by Standford Univ.'s Website explaining Binary Tree:

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

Continue reading »

Posted by Zhu Xinquan at 09:32 AM | Permalink | Comments (0)

The problem is:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
1.Sort the elements in S using merge sort.
2.Remove the last element from S. Let y be the value of the removed element.
3.If S is nonempty, look for z= x - y in S using binary search.
4.If S contains such an element z, then STOP, since we have found y and z such that x= y+ z. Otherwise, repeat Step 2.
5.If S is empty, then no two elements in S sum to x.
Step 1 takesΘ(n lg n) time. Step 2 takes Θ(1) time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm isΘ(n lg n). The following is my implement code:

Continue reading »

Posted by Zhu Xinquan at 11:32 PM | Permalink | Comments (1)

I often went to the ZOJ(Zhejiang University Online Judge)site to do some exercise before I took part in the Zhejiang Province Programming Contest. Attending this activity gives me much joy and my fellows in the contest and our coach are both very kind.

Continue reading »

Posted by Zhu Xinquan at 02:22 AM | Permalink | Comments (0)

It is not difficult to devise an algorithm that can find both the minimum and the maximum of n elements using Θ(n) comparisons. Simply find the minimum and maximum independently, using n - 1 comparisons for each, for a total of 2n - 2 comparisons.In fact, at most 3(n/2) comparisons are sufficient to find both the minimum and the maximum in the array of size n.We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.

Continue reading »

Posted by Zhu Xinquan at 11:31 AM | Permalink | Comments (0)

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. Seems so fast? The answer is no. It just uses extra space to cut down the runtime. However I have extended the range to -k to k in the following implementation.

Continue reading »

Posted by Zhu Xinquan at 04:24 PM | Permalink | Comments (0)

Recently I am reading the book CLRS Introduction to Algorithms, Second Edition. I find that I really hook on it! It's a great book about the Algorithm and I think I will wirte some notes about reading the book and write some C/C++ code for the pseudo code on this book.

Continue reading »

Posted by Zhu Xinquan at 09:31 PM | Permalink | Comments (5)

Quicksort is a sorting algorithm whose worst-case running time is Θ(n^2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(n lg n). Quicksort, like merge sort, is based on the divide-and-conquer method.

Continue reading »

Posted by Zhu Xinquan at 06:55 PM | Permalink | Comments (0)

Unlike the mergesort and quicksort, heapsort doesn't require massive recursion or multiple arrays to work and the time complexity of heapsort is O(n log(n)) . It utilizes a special data structure called heap. Before we take a look at the Heap sort algorithm, let's explain the the (binary) heap data structure.

Continue reading »

Posted by Zhu Xinquan at 11:12 AM | Permalink | Comments (0)