Swapping nodes in a single linked list

Here is algorithm for swapping two nodes in linked list..

//A complete swap algorithm which cares of
//several scenarios while swapping two nodes in
//a linked list which doesn't have any special nodes
//scenarios considered while swapping
//1)two nodes which are far away
//2)two nodes which are far away, one is node is at
//  beginning of the list
//3)two node which are neighbors
//4)two nodes which are neibhors,
//  one node is at beginning of the list
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{
  Node *node1prev, *node2prev, *tmp;

  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);

  tmp = node2->next;

  //check whether node to swapped is in
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node,
    //if the first node and some
    //other node, need to be swapped,
    //then update the list (makes new min node as
    //logical header)
    list = node2;
  }

  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes,
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;

    node1->next = tmp;
    node2prev->next = node1;
  }

  return list;
}

Please refer reference code for collection of posts in data structures

[note:I’d used old complier(msvc 6.0), if you are using a new compiler you may get some compiler warnings, please solve it yourself or post it here with the problems)

if you find any bugs in the above program post them as comments..

Balanced (AVL) Binary Search Trees

An AVL (adelson-velskii-landis) tree also known as balanced tree is a binary search tree with a balance condition.
The balance condition is that for every node in the tree, the height of left and right subtrees can differ by at most 1. The condition ensures that the depth of the tree is O(log N).

      9                           9
     / \                         / \
    /   \                       /   \
   /     \                     /     \
  5      15                   5      15
 / \     /                   / \     / \
2   6   /                   2   6   /   \
       13                          13   20
      /                           /
     /                           /
    12                          12

fig1:BST but               fig2:BST and is balanced(AVL) tree
not balanced tree

as the node 15 in fig1 is out of balance because height of left sub tree is 2 and height of right sub tree is 0.
You might be wondering how to compute height, here it is

height(Tree) = MAX(height(left-sub-tree), height(right-sub-tree)) + 1;

for example, height(9) = MAX(height(5), height(15)) + 1;
height(5) = MAX(height(2), height(6)) + 1 = 1;
height(15) = MAX(height(13), -1) + 1 = 2
so, height(5) = MAX(1, 2) + 1 = 3;

Maintaining height information of each node is necessary to check the balancing condition in AVL (balanced) tree.
So, here is the AVL (balanced) tree node representation

struct Tree
{
  Tree * left,
  Tree * right;
  int element;
  int height;
};

Here are the operations which are possible on Balanced (AVL) tree ADT,

1)Make Empty
2)Height
3)Find
4)FindMin
5)FindMax
6)Insert
7)Delete

 

Please refer http://www.refcode.net/2013/02/balanced-avl-binary-search-trees.html

 

 

Printing Binary Trees in Ascii

Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii.

The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this

struct Tree
{
  Tree * left, * right;
  int element;
};

This pic illustrates what the below routine does on canvas..

Here is the printing routine..

//prints ascii tree for given Tree structure
void print_ascii_tree(Tree * t)
{
  asciinode *proot;
  int xmin, i;
  if (t == NULL) return;
  proot = build_ascii_tree(t);
  compute_edge_lengths(proot);
  for (i=0; iheight && i < MAX_HEIGHT; i++)
  {
    lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i height && i < MAX_HEIGHT; i++)
  {
    xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i height; i++)
  {
    print_next = 0;
    print_level(proot, -xmin, i);
    printf("\n");
  }
  if (proot->height >= MAX_HEIGHT)
  {
    printf("(This tree is taller than %d, and may be drawn incorrectly.)\n",
           MAX_HEIGHT);
  }
  free_ascii_tree(proot);
}

Auxiliary routines..

//This function prints the given level of the given tree, assuming
//that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  if (level == 0)
  {
    for (i=0; ilablen-isleft)/2)); i++)
    {
      printf(" ");
    }
    print_next += i;
    printf("%s", node->label);
    print_next += node->lablen;
  }
  else if (node->edge_length >= level)
  {
    if (node->left != NULL)
    {
      for (i=0; iright != NULL)
    {
      for (i=0; ileft,
                x-node->edge_length-1,
                level-node->edge_length-1);
    print_level(node->right,
                x+node->edge_length+1,
                level-node->edge_length-1);
  }
}

//This function fills in the edge_length and
//height fields of the specified tree
void compute_edge_lengths(asciinode *node)
{
  int h, hmin, i, delta;
  if (node == NULL) return;
  compute_edge_lengths(node->left);
  compute_edge_lengths(node->right);

  /* first fill in the edge_length of node */
  if (node->right == NULL && node->left == NULL)
  {
    node->edge_length = 0;
  }
  else
  {
    if (node->left != NULL)
    {
      for (i=0; ileft->height && i left, 0, 0);
      hmin = node->left->height;
    }
    else
    {
      hmin = 0;
    }
    if (node->right != NULL)
    {
      for (i=0; iright->height && i right, 0, 0);
      hmin = MIN(node->right->height, hmin);
    }
    else
    {
      hmin = 0;
    }
    delta = 4;
    for (i=0; ileft != NULL && node->left->height == 1) ||
	      (node->right != NULL && node->right->height == 1))&&delta>4)
    {
      delta--;
    }

    node->edge_length = ((delta+1)/2) - 1;
  }

  //now fill in the height of node
  h = 1;
  if (node->left != NULL)
  {
    h = MAX(node->left->height + node->edge_length + 1, h);
  }
  if (node->right != NULL)
  {
    h = MAX(node->right->height + node->edge_length + 1, h);
  }
  node->height = h;
}

asciinode * build_ascii_tree_recursive(Tree * t)
{
  asciinode * node;

  if (t == NULL) return NULL;

  node = malloc(sizeof(asciinode));
  node->left = build_ascii_tree_recursive(t->left);
  node->right = build_ascii_tree_recursive(t->right);

  if (node->left != NULL)
  {
    node->left->parent_dir = -1;
  }

  if (node->right != NULL)
  {
    node->right->parent_dir = 1;
  }

  sprintf(node->label, "%d", t->element);
  node->lablen = strlen(node->label);

  return node;
}

//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(Tree * t)
{
  asciinode *node;
  if (t == NULL) return NULL;
  node = build_ascii_tree_recursive(t);
  node->parent_dir = 0;
  return node;
}

//Free all the nodes of the given tree
void free_ascii_tree(asciinode *node)
{
  if (node == NULL) return;
  free_ascii_tree(node->left);
  free_ascii_tree(node->right);
  free(node);
}

//The following function fills in the lprofile array for the given tree.
//It assumes that the center of the label of the root of this tree
//is located at a position (x,y).  It assumes that the edge_length
//fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
  if (node->left != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

void compute_rprofile(asciinode *node, int x, int y)
{
  int i, notleft;
  if (node == NULL) return;
  notleft = (node->parent_dir != -1);
  rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
  if (node->right != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

Here is the asciii tree structure…

struct asciinode_struct
{
  asciinode * left, * right;

  //length of the edge from this node to its children
  int edge_length;

  int height;

  int lablen;

  //-1=I am left, 0=I am root, 1=right
  int parent_dir;

  //max supported unit32 in dec, 10 digits max
  char label[11];
};

Please refer reference code for collection of posts in data structures

[note: I’d used msvc6 (which is a bit old one), so when you use new compilers you may get few compilations errors, fix them yourself or drop a msg over here..]