Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d8/dee/avltree_8cpp.html below:

TheAlgorithms/C++: data_structures/avltree.cpp File Reference

Loading...

Searching...

No Matches

A simple tree implementation using nodes. More...

#include <algorithm>
#include <iostream>
#include <queue>

Go to the source code of this file.

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.

Definition in file avltree.cpp.

struct node {

struct node *left;

struct node *right;

}

for std::queue

for std::max for std::cout

Definition at line 13 of file avltree.cpp.

creates and returns a new node

Parameters

[in] data value stored in the node

Returns

newly created node

Definition at line 25 of file avltree.cpp.

25 {

28 nn->height = 0;

29 nn->left = nullptr;

30 nn->right = nullptr;

31 return nn;

32}

struct node { int data; int height; struct node *left; struct node *right;} node

for std::queue

calls delete on every node

Parameters

Definition at line 151 of file avltree.cpp.

151 {

152 if (root) {

155 delete root;

156 }

157}

void deleteAllNodes(const node *const root)

calls delete on every node

removes a given element from AVL tree

Parameters

root of the tree [in] element the element to be deleted from the tree

Returns

root of the updated tree

Definition at line 122 of file avltree.cpp.

122 {

123 if (root == nullptr) {

124 return root;

125 }

(element < root->

) {

root->left =

(root->left, element);

128 } else if (element > root->data) {

root->right =

(root->right, element);

130

131 } else {

132

133 if (!root->right || !root->left) {

*temp = !root->right ? root->left : root->right;

135 delete root;

136 return temp;

137 }

138

140 root->data = temp->data;

root->right =

(root->right, temp->data);

142 }

143

144 return root;

145}

node * minValue(node *root)

node * deleteNode(node *root, int element)

removes a given element from AVL tree

Parameters

Returns

difference between height of left and right subtree

Definition at line 49 of file avltree.cpp.

Parameters

[in] root the root of the tree

Returns

height of tree

Definition at line 38 of file avltree.cpp.

38 {

39 if (root == nullptr) {

40 return 0;

41 }

1 + std::max(

(root->left),

(root->right));

43}

inserts a new element into AVL tree

Parameters

root of the tree [in] item the element to be insterted into the tree

Returns

root of the updated tree

Definition at line 92 of file avltree.cpp.

92 {

93 if (root == nullptr) {

95 }

(item < root->

) {

root->left =

(root->left, item);

98 } else {

root->right =

(root->right, item);

100 }

102 if (b > 1) {

105 }

107 } else if (b < -1) {

110 }

112 }

113 return root;

114}

node * insert(node *root, int item)

inserts a new element into AVL tree

node * leftRotate(node *root)

node * createNode(int data)

creates and returns a new node

int getBalance(node *root)

node * rightRotate(node *root)

Parameters

root of the tree to be rotated

Returns

node after left rotation

Definition at line 67 of file avltree.cpp.

67 {

*t = root->right;

70 t->left = root;

71 root->right = u;

72 return t;

73}

prints given tree in the LevelOrder

Parameters

Definition at line 163 of file avltree.cpp.

163 {

164 std::queue<node *> q;

165 q.push(root);

166 while (!q.empty()) {

167 root = q.front();

168 std::cout << root->data << " ";

169 q.pop();

170 if (root->left) {

171 q.push(root->left);

172 }

173 if (root->right) {

174 q.push(root->right);

175 }

176 }

177}

Main function.

Returns

0 on exit

Definition at line 183 of file avltree.cpp.

183 {

184

*root =

;

186 int i = 0;

(i = 1; i <= 7; i++) root =

(root, i);

188 std::cout << "LevelOrder: ";

191 std::cout << "\nLevelOrder: ";

194 std::cout << "\nLevelOrder: ";

197 return 0;

198}

void levelOrder(node *root)

prints given tree in the LevelOrder

Parameters

Returns

node with minimum value in the tree

Definition at line 79 of file avltree.cpp.

79 {

80 if (root->left == nullptr) {

81 return root;

82 }

84}

Parameters

root of the tree to be rotated

Returns

node after right rotation

Definition at line 55 of file avltree.cpp.

55 {

58 t->right = root;

59 root->left = u;

60 return t;

61}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4