Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
avltree.cpp File Reference

A simple tree implementation using nodes. More...

#include <algorithm>
#include <iostream>
#include <queue>
Include dependency graph for avltree.cpp:

Classes

class  node< Kind >
 

Typedefs

typedef struct node node
 

Functions

nodecreateNode (int data)
 
int height (node *root)
 
int getBalance (node *root)
 
noderightRotate (node *root)
 
nodeleftRotate (node *root)
 
nodeminValue (node *root)
 
nodeinsert (node *root, int item)
 
nodedeleteNode (node *root, int key)
 
void levelOrder (node *root)
 
int main ()
 

Detailed Description

A simple tree implementation using nodes.

Todo:
update code to use C++ STL library features and OO structure
Warning
This program is a poor implementation and does not utilize any of the C++ STL features.

Function Documentation

◆ createNode()

node* createNode ( int  data)

Create and return a new Node

21  {
22  node *nn = new node();
23  nn->data = data;
24  nn->height = 0;
25  nn->left = NULL;
26  nn->right = NULL;
27  return nn;
28 }

◆ deleteNode()

node* deleteNode ( node root,
int  key 
)

Balanced Deletion

88  {
89  if (root == NULL)
90  return root;
91  if (key < root->data)
92  root->left = deleteNode(root->left, key);
93  else if (key > root->data)
94  root->right = deleteNode(root->right, key);
95 
96  else {
97  // Node to be deleted is leaf node or have only one Child
98  if (!root->right) {
99  node *temp = root->left;
100  delete (root);
101  root = NULL;
102  return temp;
103  } else if (!root->left) {
104  node *temp = root->right;
105  delete (root);
106  root = NULL;
107  return temp;
108  }
109  // Node to be deleted have both left and right subtrees
110  node *temp = minValue(root->right);
111  root->data = temp->data;
112  root->right = deleteNode(root->right, temp->data);
113  }
114  // Balancing Tree after deletion
115  return root;
116 }

◆ getBalance()

int getBalance ( node root)

Returns difference between height of left and right subtree

38 { return height(root->left) - height(root->right); }

◆ height()

int height ( node root)

Returns height of tree

31  {
32  if (root == NULL)
33  return 0;
34  return 1 + std::max(height(root->left), height(root->right));
35 }

◆ insert()

node* insert ( node root,
int  item 
)

Balanced Insertion

66  {
67  node *nn = createNode(item);
68  if (root == NULL)
69  return nn;
70  if (item < root->data)
71  root->left = insert(root->left, item);
72  else
73  root->right = insert(root->right, item);
74  int b = getBalance(root);
75  if (b > 1) {
76  if (getBalance(root->left) < 0)
77  root->left = leftRotate(root->left); // Left-Right Case
78  return rightRotate(root); // Left-Left Case
79  } else if (b < -1) {
80  if (getBalance(root->right) > 0)
81  root->right = rightRotate(root->right); // Right-Left Case
82  return leftRotate(root); // Right-Right Case
83  }
84  return root;
85 }

◆ leftRotate()

node* leftRotate ( node root)

Returns Node after Left Rotation

50  {
51  node *t = root->right;
52  node *u = t->left;
53  t->left = root;
54  root->right = u;
55  return t;
56 }

◆ levelOrder()

void levelOrder ( node root)

LevelOrder (Breadth First Search)

119  {
121  q.push(root);
122  while (!q.empty()) {
123  root = q.front();
124  std::cout << root->data << " ";
125  q.pop();
126  if (root->left)
127  q.push(root->left);
128  if (root->right)
129  q.push(root->right);
130  }
131 }

◆ main()

int main ( void  )

Main function

134  {
135  // Testing AVL Tree
136  node *root = NULL;
137  int i;
138  for (i = 1; i <= 7; i++) root = insert(root, i);
139  std::cout << "LevelOrder: ";
140  levelOrder(root);
141  root = deleteNode(root, 1); // Deleting key with value 1
142  std::cout << "\nLevelOrder: ";
143  levelOrder(root);
144  root = deleteNode(root, 4); // Deletin key with value 4
145  std::cout << "\nLevelOrder: ";
146  levelOrder(root);
147  return 0;
148 }

◆ minValue()

node* minValue ( node root)

Returns node with minimum value in the tree

59  {
60  if (root->left == NULL)
61  return root;
62  return minValue(root->left);
63 }

◆ rightRotate()

node* rightRotate ( node root)

Returns Node after Right Rotation

41  {
42  node *t = root->left;
43  node *u = t->right;
44  t->right = root;
45  root->left = u;
46  return t;
47 }
deleteNode
node * deleteNode(node *root, int key)
Definition: avltree.cpp:88
node
Definition: avltree.cpp:13
node
struct list node
levelOrder
void levelOrder(node *root)
Definition: avltree.cpp:119
std::queue
STL class.
createNode
node * createNode(int data)
Definition: avltree.cpp:21
insert
node * insert(node *root, int item)
Definition: avltree.cpp:66
std::cout
height
int height(node *root)
Definition: avltree.cpp:31
rightRotate
node * rightRotate(node *root)
Definition: avltree.cpp:41
data
int data[MAX]
test data
Definition: hash_search.cpp:24
minValue
node * minValue(node *root)
Definition: avltree.cpp:59
std::max
T max(T... args)
leftRotate
node * leftRotate(node *root)
Definition: avltree.cpp:50
std::vector::data
T data(T... args)
getBalance
int getBalance(node *root)
Definition: avltree.cpp:38