tree AVL

[nguyenhanh52889]

how to optimize the algorithm?

#include <iostream>
#include <vector>
#include <cstdlib>


using namespace std;

// An AVL tree node // tao cay avl
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height; // do cao cua cay
};

// A utility function to get maximum of two integers
int max(int a, int b);

int max(int a, int b)
{
return (a > b) ? a : b;
}
// A utility function to get height of the tree
int height(Node *N)
{
if (N == 0)
return 0;
return N->height;
}

// A utility function to get maximum of two integers


// creat new node // tao nut moi
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = 0;
node->right = 0;
node->height = 1; // new node is initially added at leaf
return(node);
}



Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;

// Perform rotation // quay
x->right = y;
y->left = T2;

// Update heights // ghi nho chieu cao
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;

// Return new root
return x;
}

Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;

// Return new root
return y;
}

// Get Balance factor of node N // tinh balance
int getBalance(Node *N)
{
if (N == 0)
return 0;
return height(N->left) - height(N->right);
}


Node* insert(Node* node, int key)
{
// like binary search tree common // giong nhu trong cay nhi phan thong thuong
if (node == 0)
return(newNode(key));

//Проходим по пути поиска, пока не убедимся, что ключа в дереве нет.
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;

// Update height of this ancestor node // ghi nho chieu cao
/*"Отступаем" назад от добавленной вершины к корню. Проверяем в
каждой вершине сбалансированность. Если разность высот поддеревьев
равна 2 – выполняем нужное вращение.
*/
node->height = 1 + max(height(node->left),
height(node->right));

// get balance
int balance = getBalance(node);

// if balance >= 2 || <= -2 use necessary command // neu balance >= 2, <= -2 su dung lenh phu hop
if (balance > 1 && key < node->left->key)
return rightRotate(node);

if (balance < -1 && key > node->right->key)
return leftRotate(node);

if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;
}

// find minimum

Node * minValueNode(Node* node)
{
Node* current = node;
while (current->left != 0)
current = current->left;

return current;
}

// delete node with key
Node* deleteNode(Node* root, int key)
{

// like binary search tree common // giong nhu trong cay nhi phan thong thuong
// Ищем вершину D, которую требуется удалить.
if (root == 0)
return root;

if (key < root->key)
root->left = deleteNode(root->left, key);

else if (key > root->key)
root->right = deleteNode(root->right, key);

else
{
// node with only one child or no child
//Если D – лист или D имеет одно поддерево, то удаляем D
if ((root->left == 0) || (root->right == 0))
{
struct Node *temp = root->left ? root->left :
root->right;

// No child case
if (temp == 0)
{
temp = root;
root = 0;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
}
else
{
/*Если D имеет два поддерева, то ищем вершину M, следующую по
значению после D. Как в стандартном алгоритме удаления из
дерева поиска. Переносим значение из M в D. Удаляем M.*/

Node* temp = minValueNode(root->right);

// Copy the inorder successor's data to this node
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
}

// If the tree had only one node then return
if (root == 0)
return root;

// find height
root->height = 1 + max(height(root->left),
height(root->right));

//find balance
int balance = getBalance(root);

// if balance >= 2 || <= -2 use necessary command // neu balance >= 2, <= -2 su dung lenh phu hop

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}




int k(0);
int m(0);
void RNL(Node* node, int key)
{
if (node != 0)
{
RNL(node->right, key);
if (key == node->key)
{
cout << k << " ";
return;
}
k++;
RNL(node->left, key);
}
}

//find node->key, node in key-th
void RNL1(Node* node, int key)
{
if (node != 0)
{
if (m != 0)
return;
RNL1(node->right, key);
if (k == key)
{
m = node->key;
}
k++;

cout << "so k = " << k << endl;
RNL1(node->left, key);
}
}

void RNL0(Node* node)
{
if (node != 0)
{
RNL0(node->right);
cout << node->key << " ";
RNL0(node->left);
}
}


int main()
{
Node *root = 0;
int N(0);
cin >> N;
int command(0);
int key(0);

for (int i = 0; i < N; i++)
{
cin >> command >> key;
switch (command)
{
case 1:
root = insert(root, key);
RNL(root, key);
cout << endl;
RNL0(root);
cout << endl;
k = 0;
break;
case 2:
RNL1(root, key);
cout << endl << m << endl;
root = deleteNode(root, m);
RNL0(root);
k = 0;
m = 0;
break;
default:
break;
}
}

system("pause");
return 0;
}