Monthly Archives: August 2011

AVL Tree (Adelson-Velskii-Landis) – Implementation in C

An AVL tree is a self balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree-rotations.

   The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup intensive applications. However, it looks like red-black trees could be faster for insertion and element removal.

Basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications are preceded or followed by one or more operations called tree rotations, which help to restore the height balance of the subtree.

Lookup

Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree. Because of the height-balancing of the tree, a lookup takes O(log n) time. No special actions need to be taken, and the tree’s structure is not modified by lookups. If each node additionally records the size of its subtree (including itself and its descendants), then the nodes can be retrieved by index in O(log n) time as well. 

Insertion

After inserting a node, it is necessary to check each of the node’s ancestors for consistency with the rules of AVL. For each node checked, if the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes ±2 then the subtree rooted at this node is unbalanced. If insertions are performed serially, after each insertion, at most one of the following cases needs to be resolved to restore the entire tree to the rules of AVL.

There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree, with R and L denoting the right and left children of P respectively.

Right-Right case and Right-Left case:

  • If the balance factor of P is -2 then the right subtree outweights the left subtree of the given node, and the balance factor of the right child (R) must be checked. The left rotation with P as the root is necessary.
  • If the balance factor of R is -1, a double left rotation(with respect to P and then R) is needed (Right-Right case).
  • If the balance factor of R is +1, two different rotations are needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root (Right-Left case).

Left-Left case and Left-Right case:

  • If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. The right rotation with P as the root is necessary.
  • If the balance factor of L is +1, a double right rotation (with respect to P and then L) is needed (Left-Left case).
  • If the balance factor of L is -1, two different rotations are needed. The first rotation is a left rotation with L as the root. The second is a right rotation with P as the root (Left-Right case). The pictorial representation is given below:

                                                                                                                         

I have done the implementation of AVL tree in C.

The program for rotation is shown below: 

For left-right,  

      

For left-left,

For right-left,

For right-right,

The complete code of implementation of AVL tree in C is available here: https://bitbucket.org/vidyakv/avl-tree/changeset/a112ab2dd2f4 

Deletion

If the node is a leaf or has only one child, remove it. Otherwise, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node. The node that was found as a replacement has at most one subtree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed.

Note: The image of tree used in this post is taken from wikipedia.

Version Control Systems

Version control or source control is the management of changes to documents, programs, and other information stored as computer files. It is most commonly used in software develoment, where a team of people may change the same files. Changes are usually identified by a number or letter code, termed the “revision number”, “revision level”, or simply “revision”. So it is also known as revision control.

Version control systems (VCSs – singular VCS) most commonly run as stand-alone applications, but revision control is also embedded in various types of software such as word processor (e.g., Microsoft Word, Openoffice.org Writer, K Word, Pages, etc.), spreadsheets (e.g., Microsoft Excel, Openoffice.org Calc, K Spread, Numbers, etc.), and in various content management systems (e.g.,joomla, WordPress).

Distributed revision control

Distributed revision control (DRCS) takes a peer-to-peer approach, as opposed to the client-server approach of centralized systems. Rather than a single, central repository on which clients synchronize, each peer’s working copy of the codebase is a bona-fide repository. Distributed revision control conducts synchronization by exchanging patches (change-sets) from peer to peer. This results in some important differences from a centralized system:

  • No canonical, reference copy of the codebase exists by default; only working copies.
  • Common operations (such as commits, viewing history, and reverting changes) are fast, because there is no need to communicate with a central server.

Rather, communication is only necessary when pushing or pulling changes to or from other peers.

    • Each working copy effectively functions as a remote backup of the codebase and of its change-history, providing natural protection against data loss.

Mercurial

Mercurial is a modern, open source, distributed version control system, and a compelling upgrade from older systems like Subversion. Developers use it to manage source code.

In Mercurial every developer has a copy of the entire repository on their hard drive. It’s actually safer. And anyway, almost every Mercurial team uses a central repository, too, which you can back up compulsively, and you can build a three-ringed security zone complete with layers of Cylons, Stormtroopers, and adorable labradoodles.

Branching causes problems in Subversion because Subversion doesn’t store enough information to make merging work. In Mercurial, merging is painless and easy, and so branching is commonplace and harmlessn Mercurial, every developer has their own repository.So you can commit your code to your private repository, and get all the benefit of version control, whenever you like. Every time you reach a logical point where your code is a little bit better, you can commit it.Once it’s solid, and you’re willing to let other people use your new code, you push your changes from your repository to a central repository that everyone else pulls from, and they finally see your code. When it’s ready.

Mercurial separates the act of committing new code from the act of inflicting it on everybody else.

And that means that you can commit (hg com) without anyone else getting your changes. When you’ve got a bunch of changes that you like that are stable and all is well, you push them (hg push) to the main repository.

Subversion likes to think about revisions. A revision is what the entire file system looked like at some particular point in time.In Mercurial, you think about changesets. A changeset is a concise list of the changes between one revision and the next revision.

Mercurial thinks in terms of “changesets” instead of “revisions” it can merge code much better than Subversion.”

Subversion is basically revision control for files, but in Mercurial, revision control always applies to an entire directory—including all subdirectories.

Actually Mercurial serves two important purposes:

  1. It keeps track of every old version of every file
  2. It can merge different versions of your code, so that teammates can work independently on the code and then merge their changes

The command for Mercurial is hg:

basic commands:
use "hg help" for the full list of commands or "hg -v" for details

hg init         –    creates a repository
hg add         – schedules files to be added to the repository. They won’t actually be added until you commit
hg commit   –  saves the current state of all files to the repository
hg log         –   shows the history of changes committed to the repository
hg revert     –   revert changed files back to committed version
hg status   –   shows a list of changed files
hg diff      –    shows what changed in a file
hg remove – schedules files to be removed from the repository. They won’t actually be removed until you commit.
hg cat        –  shows any revision of any file.
hg update  – update the working directory to a particular revision
hg serve    – runs a web server to make the current repository accessible over the Internet
hg clone   –  make a complete copy of an entire repository
hg push   –   push new changes from this repository into another
hg outgoing – list changes in current repository waiting to be pushed
hg merge   –   merge two heads
hg parent   –   show the changeset that’s in the working directory

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.