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

All operations can be performed in O(log N) time, except possibly insertion. when we do an insertion, we need to update the balancing information for the nodes on the path back to root, but the reason that insertion is potentially difficult is that inserting a node could voilate the AVL (balanced) tree property. For example inserting 10 in fig2 would voilate the AVL tree property.
So, the inorder to maintain the balancing condition the tree has to be modified, this modification operation is called rotation.

Our algorithms used tail recursion, as the average depth of a binary search tree is O(log N),
the amount of stack space used is expected to be only O(log N).

1. Make Empty

This operation is for mainly intialization and can be used to destroy entire search tree also.

Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
    t = NULL;
  }
 
  return NULL;
}

2. Height

Finds height of the tree

int height(Tree *t)
{
  if (t == NULL)
  {
    return -1;
  }
  else
  {
    return t->height;
  }
}

3. Find

This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
element stored in the tree node

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
 
  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}

4. FindMin

This operation returns the smallest element node in the tree, i.e. left most element of the tree

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

5. FindMax

This operation returns the biggest element node in the tree, i.e. right most element of the tree

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

6. Insert

This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
insert the element at the last spot on the path traversed. After insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition. We need to rebalance the tree to satisfy AVL property. A violation of the AVL property may occur in four cases: (N is a node to be rebalanced)
1) An insertion into the left subtree of the left child of the node N
2) An insertion into the right subtree of the left child of the node N
3) An insertion into the left subtree of the right child of the node N
4) An insertion into the right subtree of the right child of the node N

cases 1 & 4 can be fixed by single rotation
cases 2 & 3 can be fixed by double rotation

single and double rotation will be explained after explaing insert and delete operations.

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
	    return t;
    }
 
    new_node->element = value;
    new_node->height = 0;
    new_node->left = new_node->right = NULL;
    return new_node;
  }
  else if (value < t->element) 
  {
    t->left = insert(value, t->left);
    if (height(t->left) - height(t->right) == 2)
    {
      if (value < t->left->element)
      {
        t = single_rotation_with_left(t);
      }
      else
      {
        t = double_rotation_with_left(t);
      }
    }
  } 
  else if (value > t->element) 
  {
    t->right = insert(value, t->right);
    if (height(t->right) - height(t->left) == 2)
    {
      if (value > t->right->element)
      {
        t = single_rotation_with_right(t);
      }
      else
      {
        t = double_rotation_with_right(t);
      }
    }
   } 
  //else duplicate, ignore it
 
  t->height = MAX(height(t->left), height(t->right)) + 1;
  return t;
}

7. Delete

This is the complicated operation among other tree operations. If the node to be deleted is a leaf, it can be deleted immediately. If the node has one child, the node can deleted after its parents adjusts a pointer to bypass the node. While deleting a node which has two children, the general strategy is to replace the data of this node with the smallest data of the right subtree and recursively delete that node.

After deletion, only nodes that are on the path from the deletion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition.
We need to rebalance the tree to satisfy AVL property using single and double rotation operations in similar way as we did for insertion operation.

Tree * delete(int value, Tree * t) 
{
  //Deletes node from the tree
  // Return a pointer to the resulting tree
 
  Tree * x;
  Tree *tmp_cell;
 
  if (t==NULL) return NULL;
 
  if (value < t->element) 
  {
    t->left = delete(value, t->left);
 
    if (height(t->right) - height(t->left) >= 2)
    {
      if (t->left && (value < t->left->element))
      {
        t = double_rotation_with_right(t);
      }
      else
      {
        t = single_rotation_with_right(t);
      }
    }
  } 
  else if (value > t->element) 
  {
    t->right = delete(value, t->right);
 
    if (height(t->left) - height(t->right) >= 2)
    {
      if (t->right && (value > t->right->element))
      {
        t = double_rotation_with_left(t);
      }
      else
      {
        t = single_rotation_with_left(t);
      }
    }
 
  } 
  else if (t->left && t->right)
  {
    tmp_cell = find_min(t->right);
    t->element = tmp_cell->element;
    t->right = delete(t->element, t->right);
  }
  else
  { 
    tmp_cell = t;
    if (t->left == NULL)
      t = t->right;
    else if (t->right == NULL)
      t = t->left;
    free(tmp_cell);
    tmp_cell = NULL;
  }
 
  return t;
}

Single Rotation

Single Rotation fixes voilations cause by the below cases (N is a node to be rebalanced)
1) An insertion into the left subtree of the left child of the node N
4) An insertion into the right subtree of the right child of the node N

Single Raotation does as below..

     k2                k1
     / \              /  \
    k1  z     -->    x    k2
   / \                   /  \
  x   y                 y    z              

examples for single rotation:

Before single rotating left at 20

   20
   /
  15
 /
5

After single rotating left

 15
 / \
5  20

Here is the code for single rotation..

//Single rotation left
//     k2                k1
//     / \              /  \
//    k1  z     -->    x    k2
//   / \                   /  \
//  x   y                 y    z              
Tree *single_rotation_with_left(Tree *k2)
{
  Tree *k1;
 
  k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
 
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->left), height(k2->right)) + 1;
 
  //return new root
  return k1;
}
 
//Single rotation right
//     k2                k1
//     / \              /  \
//    x  k1     -->    k2   z
//       / \          /  \
//      y   z        x    y
Tree *single_rotation_with_right(Tree *k2)
{
  Tree *k1;
 
  k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
 
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->right), height(k2->left)) + 1;
 
  //return new root
  return k1;
}

Double Rotation

Single Rotation fixes voilations cause by the below cases (N is a node to be rebalanced)
2) An insertion into the right subtree of the left child of the node N
3) An insertion into the left subtree of the right child of the node N

Double Raotation does as below..

      k3                k2
     / \              /  \
    k1  d     -->    k1    k3
   / \              / \   /  \
  a   k2           a   b c    d
     /  \
    b    c

examples for double rotation:

Before double rotating right at 10

     10
    /  \
   5    15
      /  \
     12  16
      \
      13

After double rotating right

     12
    /  \
   10   15
  /    /  \
 5    13  16

Here is the code for single rotation..

//Double rotation left
//      k3                k2
//     / \              /  \
//    k1  d     -->    k1    k3
//   / \              / \   /  \
//  a   k2           a   b c    d   
//     /  \
//    b    c
Tree *double_rotation_with_left(Tree *k3)
{
  //rotate between k1 & k2
  k3->left = single_rotation_with_right(k3->left);
 
  //rotate between k3 & k2
  return single_rotation_with_left(k3);
}
 
//Double rotation right
//      k3                k2
//     / \               /  \
//    a   k1     -->   k3    k1
//       / \          / \   /  \
//      k2  d        a   b c    d   
//     /  \
//    b    c
Tree *double_rotation_with_right(Tree *k3)
{
  //rotate between k1 & k2
  k3->left = single_rotation_with_left(k3->right);
 
  //rotate between k3 & k2
  return single_rotation_with_right(k3);
}

Here are the operations examples..

After inserting element 20..
20

After inserting element 5..

 20
 /
5

After inserting element 15..

 15
 / \
5  20

After inserting elements 9, 13..

   15
   / \
  9  20
 / \
5  13

After inserting elements 2, 6, 12, 14, ..

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

After inserting elements 15..

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

After inserting elements 16..

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

After inserting elements 17..

      9
     / \
    /   \
   /     \
  5      15
 / \     / \
2   6   /   \
       /     \
      /       \
     13       17
    / \       / \
   /   \     /   \
  12   14   16   20

After inserting elements 18..

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   20
  5      13       /
 / \     / \     18
2   6   /   \
       12   14

After inserting elements 19..

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   19
  5      13       / \
 / \     / \     /   \
2   6   /   \   18   20
       12   14

After deleting a node (14)

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   19
  5      13       / \
 / \     /       /   \
2   6   12      18   20

After deleting a node (13)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  5  12   /   \
 / \     16   19
2   6         / \
             /   \
            18   20

After deleting a node (5)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  6  12   /   \
 /       16   19
2             / \
             /   \
            18   20

After deleting a node (10)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  6  12   /   \
 /       16   19
2             / \
             /   \
            18   20

After deleting a node (14, 15)

       16
       / \
      /   \
     /     \
    9      19
   / \     / \
  6  12   /   \
 /       17   20
2         \
          18

After deleting a node (16)

       17
       / \
      /   \
     /     \
    9      19
   / \     / \
  6  12   /   \
 /       18   20
2

After deleting a node (19)

       17
       / \
      /   \
     /     \
    9      20
   / \     /
  6  12   18
 /
2

After deleting a node (18, 20)

     9
    / \
   /   \
  6    17
 /     /
2     12

Download the AVL (Balanced) Tree Source Code [note: I’ve used some what old compiler(msvc6.0), if you are using a new compiler you may get some compilation errors, fix them yourself otherwise drop a message over here]

Popularity: 21%

Welcome

Welcome to the OpenAsthra QuestionPatterns.
This exam contains 10 questions of which you’ll have to answer at least 7 correct to pass.
Please do not use any back button while doing this test
Please press the button below to continue to the first question.

Popularity: 24%

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; i<proot->height && i < MAX_HEIGHT; i++) 
  {
    lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i < proot->height && i < MAX_HEIGHT; i++) 
  {
    xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i < proot->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; i<(x-print_next-((node->lablen-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; i<(x-print_next-(level)); i++) 
      {
        printf(" ");
      }
      print_next += i;
      printf("/");
      print_next++;
    }
    if (node->right != NULL) 
    {
      for (i=0; i<(x-print_next+(level)); i++) 
      {
        printf(" ");
      }
      print_next += i;
      printf("\\");
      print_next++;
    }
  } 
  else 
  {
    print_level(node->left, 
                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; i<node->left->height && i < MAX_HEIGHT; i++) 
      {
        rprofile[i] = -INFINITY;
      }
      compute_rprofile(node->left, 0, 0);
      hmin = node->left->height;
    } 
    else 
    {
      hmin = 0;
    }
    if (node->right != NULL) 
    {
      for (i=0; i<node->right->height && i < MAX_HEIGHT; i++) 
      {
        lprofile[i] = INFINITY;
      }
      compute_lprofile(node->right, 0, 0);
      hmin = MIN(node->right->height, hmin);
    } 
    else 
    {
      hmin = 0;
    }
    delta = 4;
    for (i=0; i<hmin; i++) 
    {
      delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
    }
 
    //If the node has two children of height 1, then we allow the
    //two leaves to be within 1, instead of 2 
    if (((node->left != 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 <= node->edge_length && y+i < MAX_HEIGHT; i++) 
    {
      lprofile[y+i] = MIN(lprofile[y+i], x-i);
    }
  }
  compute_lprofile(node->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 <= node->edge_length && y+i < MAX_HEIGHT; i++) 
    {
      rprofile[y+i] = MAX(rprofile[y+i], x+i);
    }
  }
  compute_rprofile(node->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];  
};

Download the ascii tree source code [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..]

Your email:  
Subscribe Unsubscribe  

Popularity: 13%

A binary tree is a tree in which no node can have more than two children. The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in its left subtree are smaller than the key value in X, and the values of all the keys in its right subtree are larger than the key value in X.

An important application of binary trees is their use in searching.

Here are the operations which are possible on binary search tree ADT (abstract data type),

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

All operations except MakeEmpty above takes O(log N) time on average case.

Our algorithms used tail recursion, as the average depth of a binary search tree is O(log N),
the amount of stack space used is expected to be only O(log N).

Binary search is represented list of nodes, each node may have left and right nodes,
here is the single tree node represenation

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

1. Make Empty

This operation is for mainly intialization and can be used to destroy entire search tree also.

Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
  }
 
  return NULL;
}

2. Find

This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
element stored in the tree node

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
 
  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}

3. FindMin

This operation returns the smallest element node in the tree, i.e. left most element of the tree

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

4. FindMax

This operation returns the biggest element node in the tree, i.e. right most element of the tree

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

5. Insert

This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
insert the element at the last spot on the path traversed.

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
 
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
      return t;
    }
 
    new_node->element = value;
 
    new_node->left = new_node->right = NULL;
    return new_node;
  }
 
  if (value < t->element) 
  {
    t->left = insert(value, t->left);
  } 
  else if (value > t->element) 
  {
    t->right = insert(value, t->right);
  } 
  else 
  { 
    //duplicate, ignore it
    return t;
  }
  return t;
}

6. Delete

This is the complicated operation among other tree operations. If the node to be deleted is a leaf, it can be deleted immediately. If the node has one child, the node can deleted after its parents adjusts a pointer to bypass the node. While deleting a node which has two children, the general strategy is to replace the data of this node with the smallest data of the right subtree and recursively delete that node.

Tree * delete(int value, Tree * t) 
{
  //Deletes node from the tree
  // Return a pointer to the resulting tree
  Tree * x;
  Tree *tmp_cell;
 
  if (t==NULL) return NULL;
 
  if (value < t->element) 
  {
    t->left = delete(value, t->left);
  } 
  else if (value > t->element) 
  {
    t->right = delete(value, t->right);
  } 
  else if (t->left && t->right)
  {
    tmp_cell = find_min(t->right);
    t->element = tmp_cell->element;
    t->right = delete(t->element, t->right);
  }
  else
  { 
    tmp_cell = t;
    if (t->left == NULL)
      t = t->right;
    else if (t->right == NULL)
      t = t->left;
    free(tmp_cell);
  }
 
  return t;
}

Here are the operations examples..

Download the Binary Search Tree Source Code [note: I’ve used some what old compiler(msvc6.0), if you are using a new compiler you may get some compilation errors, fix them yourself otherwise drop a message over here]

Popularity: 29%

Please refer Lesson 10..

11. SOME INDIVIDUAL TOPICS
11.1 DOS Keyboard Characteristics
11.2 Detach Method for Wrapper Classes

11. SOME INDIVIDUAL TOPICS

11.1 DOS Keyboard Characteristics

When any key on the keyboard is pressed, a parameter in the operating system is set, and this parameter can be checked through method kbhit( ) in . Then we can get this character through method getch in . Method getch returns one char at a time. If the key can be represented in ASCII, the ASCII code of the character is returned. But many keys cannot be represented in ASCII, for example the F1 key and the PageDown key. When they have been pressed, first a zero is returned, then the next value we get will tell us which key it was.

11.2 Detach Method for Wrapper Classes

Some wrapper classes has a pointer to another dynamic object. In its destructor it usually delete that object to free the space. However, if some one calls its “get” method which returns this pointer to the outside world, then the dynamic object is taken care of by another program and should be “detached” from the wrapper class, so that the destructor is no longer responsible to delete that dynamic object.:

class Person 
{
private:
  char * m_strName;
 
public:
  Person(char * name = NULL) : m_strName(name) 
  {}
 
  ~Person() 
  {  
    if(m_strName != 0) 
      delete m_strName; 
  }
 
  char * Detach() 
  {  
    char * temp;
    temp = m_strName;
    m_strName = 0; 
    return temp;
  }
}

Popularity: 41%

Please refer Lesson 9..

10. ANSI/ISO C++ STANDARD LANGUAGE ADDITIONS
10.1 bool
10.2 Four Casts
10.3 Namespace
10.4 Run-Time Type Information (RTTI)
10.5 Operator Keywords
10.6 explicit Constructor
10.7 mutable Class Member

10. ANSI/ISO C++ STANDARD LANGUAGE ADDITIONS

10.1 bool

In C++ zero represents false and non-zero represents true. But bool type true and false is clearer and is preferred.

10.2 Four Casts

The ANSI/ISO C++ draft standard introduces four new cast operators to replace the old-style cast, which do all kinds of casting jobs. The new casts are less powerful and more specific, and each of them has separate purposes, thus give the program more precise control. Old casting is still legal, but new casts are preferable.

=>static_cast and dynamic_cast

static_cast operator and dynamic_cast is mainly used to cast up or dow the inheritance hierarchy - to cast base-class objects or pointers to derived-class objects or pointers, or vice versa. Consider the following example:

class Base 
{
public:
  Method1() {};
};
 
class Derived : public Base 
{
public:
  Method2() {};
};
 
void DoSomething(Base * pBase)
{
  Derived * pDerived1 = static_cast<Derived *>(pBase);
  pDerived1->Method2();
 
  Derived * pDerived2 = dynamic_cast<Derived *>(pBase);
  pDerived2->Method2();
}

static_cast only perform type checking at compile time. So it is safer than casting with “( )”. But it does not perform run-time type checking, so it is the programmer’s responsibility to make sure that pBase is pointing to a Derived object. If not, there will be a run time error.

In contrast, dynamic_cast performs RTTI, and if pBase is only pointing to Base object, dynamic_cast will find out and return 0. Therefore, you can decide the whether the cast is successful by checking this:

if(dynamic_cast(ptr) == 0)

=>const_cast

const_cast casts away const or volatile. It only works on pointers, not objects. You can use it to modify a data member in a const method:

void Test::print() const   // Test is a class
{
   const_cast<Test *>(this)->member1++;    // member1 is a data member of Test
   cout << member1 << endl;
}

Such a capability can solve the problem for an intelligent pointer class:

#ifndef POINTER_H
#define POINTER_H
 
template <class Type>
class Pointer
{
public:
  Pointer() : ptr(0), owner(false) {}
 
  Pointer(Type * p) :ptr(p), owner(true) {}
 
  Pointer(const Pointer & obj)
  {
    ptr = obj. ptr;
 
    if(obj. owner == true)
    {
      owner = true;
      const_cast< Pointer * >(&obj)->owner = false;  
    }
    else
      owner = false;
  }
 
  const Pointer & operator=(const Pointer & obj)
  {
    ptr = obj. ptr;
 
    if(obj. owner == true)
    {
      owner = true;
      const_cast< Pointer * >(&obj)->owner = false;  
    }
    else
      owner = false;
 
    return *this;
  }
 
  ~ Pointer()
  {  if(owner == true) delete ptr; }
 
  int operator==(const Pointer &other) const { return ptr == other. ptr; }
  Type * pointer() const    { return ptr;  }
  Type * operator->() const { return ptr;  }
  Type & operator*() const  { return *ptr; }
 
private:
  Type * ptr;
  bool owner;
};
#endif

Such a pointer object is fully intelligent: it allows shallow copy - multiple pointer objects pointing to the same server object - to avoid the copy of pointed objects which is most probably unnecessary and time consuming. It knows to delete the server object to which it is pointing, and meanwhile avoiding multiple deleting on the same object.

The key point of this class is an extra data member “owner”, representing whether a pointer object is the owner of its server object. There may be multiple pointer objects pointing to the same server object, but among them there is only one owner, and only the owner will delete the server object.

To accomplish this, in its copy constructor and assignment operator, it transfers the ownership from “right” object to “this” object, setting the right object’s owner to be false. Considering that the right object in these two methods must be constant (otherwise it can not be applied on constant objects), we need const_cast to cast away the const of the right object before we modify its data member “owner”.

=>reinterpret_cast

reinterpret_cast is used for cases that yeilds implementation-dependent results, such as casing between function pointer types.
Because it allows you to do nonstandard strange conversions, dangerous manipulations can be done, and the result may be machine-dependent.

10.3 Namespace

Each namespace defines a scope where global identifiers and variables are placed:

namespace Test1 
{
  const double PI = 3.14159;
  const double E = 2.71828
  void print();
 
  namespace Inner {
     enum Day {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday};
  }
}
 
void Test1::print()
{  cout << PI << Inner::Monday; }

Notice that unlike classes, there is no semicolon after the definition.
Namespace can be nested.
The definition of a namespace must either occupy the scope or be nested within other namespace.

Because method “print” is a member of namespace Test1, it can directly access other data members of Test1, and access nested namespace Inner through its name.

To use a namespace member, the member’s name must be qualified with the namespace name and binary scope resolution operator:
double area = Test1::PI * 2.0 * Radius;
if(day == Test1::Inner::Tuesday)

In case a namespace’s members are frequently used in a file, to simplify the invoking process, place statement
using namespace Test1;

then in the following part of the file the namespace members do not need to be proceeded with “Test::”. It can also be used to directly access only one member of the namespace:

using namespace Test1::PI;
using namespace std;
informs the compiler that namespace std is being used. The contents of header file are all defined as part of namespace std.
Unnamed namespace members occupy the global namespace, are directly accessible and do not have to be qualified with a namespace name. Global variables are actually part of global namespace.

Ideally, in large programs, every entity should be declared in a class, method, block, or namespace. This helps clarify every entity’s role.
Classes do provide us with named scopes, but namespaces allow us to manage things more precisely. Before namespaces were introduced we had to create classes just for the purpose of defining a named scope, and we had to use typedef to get some of the control namespaces give us.

10.4 Run-Time Type Information (RTTI)

Because of polymorphism, when you write your program, you may not be able to know the exact type you are dealing with. But there are cases in which you do need to find out the exact type of the polymorphic object and deal with it differently according to its type. Run-time type information (RTTI) is used to find out the type of a polymorphic object.

Header file defines operator typeid. It returns a const reference of class type_info, which is a class description of the operand. Class type_info has a method name, which returns a char * which is the type name of the operand.

 
class Base { ... }
class Derived : public Base { ... }
int main()
{
  Base1 * pBase1 = new Derived;
  const type_info & t1 = typeid(pBase1);
  const type_info & t2 = typeid(*pBase1);
  cout << "typeid(pBase1) = " << t1.name() << endl;
  cout << "typeid(*pBase1) = " << t2.name() << endl;
}

If class Base and Derived are polymorphic types i.e. they have virtual functions, the output will be:

typeid(pBase1) = class Base1 *
typeid(*pBase1) = class Derived

If class Base and Derived do not have virtual functions, the output will be:

typeid(pBase1) = class Base1 *
typeid(*pBase1) = class Base

10.5 Operator Keywords

The ANSI/ISO standard provides operator keywords that can be used in place of some operators, in case that the keyboard you are using does not have these keys. For example, “and” can be used for “&&”, “bitand” for “&”, etc.

10.6 explicit Constructor

When a method is expecting an object which has a one-argument constructor but you pass the argument, compiler will implicitly call that one-argument constructor and convert that passed argument to the object:

class Base 
{
public:
  Base(int a) : member(a) 
  { cout << "Base constructor called with " << a << endl; }
 
  int member;
};
 
void test(Base obj1)
{  cout << "Base object's member = " << obj1.member; }
 
int main()
{    test(333);  }

The output will be:

Base constructor called with 333
Base object’s member = 333
In same cases such an automatic implicit conversion may cause trouble. You can use keyword explicit in front of the constructor to suppress the implicit conversion. If you want to convert, you have to use explicit conversion such as static_cast, without which compiler will reject the conversion and prompt error message.

 
class Base {
public:
   explicit Base(int a) : member(a) 
   { cout << "Base constructor called with " << a << endl; }
 
   int member;
};
 
void test(Base obj1)
{  cout << "Base object's member = " << obj1.member; }
 
int main()
{
   test( static_cast<Base>(333) );
}

10.7 mutable Class Member

C++ provides mutable class member as an alternative to const_cast. A mutable data member is always modifiable even in a const method of a const object. The difference between const_cast and mutable is: for a non-mutable data member in a const method, every time you modify it, you have to use const_cast. This actually reduces the chance of accidental modification.

Popularity: 18%

Please refer Lesson 8..

9. STANDARD TEMPLATE LIBRARY (STL)
9.1 Introduction to Container
9.2 Iterator
9.3 Iterator Types
9.4 Iterator Capabilities
9.5 Iterator Capabilities Supported by Different Containers
9.6 IO Iterators
9.7 Operations Supported by Different Iterators
9.8 Sequence Containers
9.9 vector
9.10 Binary Predicate Function
9.11 List
9.12 Deque
9.13 Comparison of vector, list and deque
9.14