قبل ايام انتهيت من برنامج استخدمت فيه AVL Tree . (العمل معه "سريع" ---> Log n)
لم اضف جميع العمليات, لكن الcode يحوي كل الخطوط العريضه لهذه الشجره...
اليكم الcode :
AVL Tree
مغلق
/*
this file contains the data stucture of the AVL TREE.
Class name: AVL_Tree
Templates: K=the key in each node, T=data type
constructors: takes as parameter a defult value (no defult cons')
*/
#ifndef _AVLTREE_H_
#define _AVLTREE_H_
#include "TreeNode.h"
#include <iostream.h>
/////////////////////////////////////////////////////////////////
template <class K, class T>
class AVL_Tree {
public:
AVL_Tree (const T&);
~AVL_Tree ();
bool isEmpty ();
T& getVal (const K&);
T& getKVal (unsigned long);
bool isExit (const K&);
bool insert (const K&, T&);
bool dispose (const K&);
void disposeAll ();
friend ostream& operator<< (ostream&, AVL_Tree&);
private:
bool isExit_ (const K&, tree_node<K, T>**);
bool isExit_pointer_ (tree_node<K, T>*, tree_node<K, T>**);
void getKVal_ (unsigned long&, tree_node<K, T>**);
bool insert_ (const K&, tree_node<K, T>**, tree_node<K, T>**);
int BF (tree_node<K, T>*);
int get_height (tree_node<K, T>*);
void Rotation (tree_node<K, T>**);
void RotationAll (tree_node<K, T>**);
void Rotation_LL (tree_node<K, T>**);
void Rotation_LR (tree_node<K, T>**);
void Rotation_RR (tree_node<K, T>**);
void Rotation_RL (tree_node<K, T>**);
void disposeAll_ (tree_node<K, T>**);
ostream& print_ (ostream&, tree_node<K, T>*);
private:
tree_node<K, T>* root; // pointer to root
tree_node<K, T>* current; // pointer to current
tree_node<K, T>* prev; // pointer to previous
T defult; // defult value
tree_node<K, T>* first; // JUST FOR DATABASE CLASS
unsigned long elements; // number of elements
};
/////////////////////////////////////////////////////////////////
// IMPLEMENTATION
/////////////////////////////////////////////////////////////////
template <class K, class T>
AVL_Tree<K, T>::AVL_Tree (const T& _d) :
root(NULL),
current(NULL),
prev(NULL),
defult(_d),
first(NULL),
elements(0)
{}
/////////////////////////////////////////////////////////////////
template <class K, class T>
AVL_Tree<K, T>::~AVL_Tree () {
disposeAll();
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::isEmpty () {
return (root == NULL);
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
T& AVL_Tree<K, T>::getVal (const K& _key) {
if (current->key == _key || isExit(_key)) return current->value;
else return defult;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
T& AVL_Tree<K, T>::getKVal (unsigned long _k) {
if (_k > elements) return defult;
current = NULL;
getKVal_ (_k, &root);
if (current != NULL) return current->value;
else return defult;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::isExit (const K& _key) {
return isExit_(_key, &root);
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::insert (const K& _key, T& _val) {
tree_node<K, T>* node = new tree_node<K, T>(_key ,_val);
first = node;
if (node == NULL) return false;
current = node;
if (insert_(_key, &node, &root)) {
elements++;
return true;
}
else return false;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::dispose (const K& _key) {
// NOT FOUND!!
if (!isExit(_key)) return false;
if (current->right == NULL && current->left == NULL) {
if (current == root) {
delete current;
root = NULL;
elements--;
return true;
}
else
if (prev->right == current) {
delete current;
prev->right = NULL;
} else {
delete current;
prev->left = NULL;
}
RotationAll(&root);
elements--;
return true;
}
if (current->right == NULL && current->left != NULL) {
if (current == root) {
root = current->left;
delete current;
elements--;
return true;
}
if (prev->right == current) prev->right = current->left;
else prev->left = current->left;
delete current;
RotationAll(&root);
elements--;
return true;
}
else if (current->right != NULL && current->left == NULL) {
if (current == root) {
root = current->right;
delete current;
elements--;
return true;
}
if (prev->right == current) prev->right = current->right;
else prev->left = current->right;
delete current;
RotationAll(&root);
elements--;
return true;
}
tree_node<K, T>* tracer;
tracer = current->right;
while (tracer->left != NULL) tracer = tracer->left;
*current = *tracer;
prev = current;
current = tracer;
/*
if (prev->right != current) {
prev = prev->right;
while (prev->left != current) prev = prev->left;
}
*/
if (current->right == NULL && current->left == NULL) {
if (current == root) {
delete current;
root = NULL;
elements--;
return true;
}
else
if (prev->right == current) {
delete current;
prev->right = NULL;
} else {
delete current;
prev->left = NULL;
}
RotationAll(&root);
elements--;
return true;
}
if (current->right == NULL && current->left != NULL) {
if (current == root) {
root = current->left;
delete current;
elements--;
return true;
}
if (prev->right == current) prev->right = current->left;
else prev->left = current->left;
delete current;
RotationAll(&root);
elements--;
return true;
}
else if (current->right != NULL && current->left == NULL) {
if (current == root) {
root = current->right;
delete current;
elements--;
return true;
}
if (prev->right == current) prev->right = current->right;
else prev->left = current->right;
delete current;
RotationAll(&root);
elements--;
return true;
}
// SOMETHING WRONG!!
return false;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::disposeAll () {
disposeAll_(&root);
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
ostream& operator<< (ostream& _os, AVL_Tree<K, T>& _root) {
return _root.print_(_os, _root.root);
}
/////////////////////////////////////////////////////////////////
// PRIVATE METHODS
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::isExit_ (const K& _key, tree_node<K, T>** _head) {
if ((*_head) == NULL) return false;
if ((*_head)->key == _key) {
current = *_head;
return true;
}
if (isExit_(_key, &((*_head)->right)) || isExit_(_key, &((*_head)->left))) {
if ((prev == NULL) || !((prev->left == current || prev->right == current))) prev = *_head;
return true;
}
return false;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::getKVal_ (unsigned long& _k, tree_node<K, T>** _head) {
if ((*_head) == NULL) return;
getKVal_(_k, &((*_head)->left));
if (_k-- == 0) {
current = *_head;
return;
}
if (_k < 0) return;
getKVal_(_k, &((*_head)->right));
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::isExit_pointer_ (tree_node<K, T>* _pos, tree_node<K, T>** _head) {
if ((*_head) == NULL) return false;
if (*_head == _pos) {
current = *_head;
return true;
}
if (isExit_pointer_(_pos, &((*_head)->right)) || isExit_pointer_(_pos, &((*_head)->left))) {
if ((prev == NULL) || !((prev->left == current || prev->right == current))) prev = *_head;
return true;
}
return false;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
bool AVL_Tree<K, T>::insert_ (const K& _key, tree_node<K, T>** _node, tree_node<K, T>** _head) {
if ((*_head) == NULL) {
(*_head) = *_node;
return true;
}
//if ((*_head)->key == _key) return false;
if ((*_head)->key == _key) {
insert_(_key, &(*_node), &((*_head)->left));
}
else if ((*_head)->key > _key) {
insert_(_key, &(*_node), &((*_head)->left));
}
else if ((*_head)->key < _key) {
insert_(_key, &(*_node), &((*_head)->right));
}
Rotation(&(*_head));
return true;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
int AVL_Tree<K, T>::BF (tree_node<K, T>* _head) {
if ((_head->left == NULL) && (_head->right == NULL)) return 0;
if (_head->left == NULL) return -(_head->right)->height;
if (_head->right == NULL) return (_head->left)->height;
return ((_head->left)->height - (_head->right)->height);
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
int AVL_Tree<K, T>::get_height (tree_node<K, T>* _node) {
if (_node == NULL) return 0;
return _node->height;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::Rotation (tree_node<K, T>** _head) {
(*_head)->height = (get_height((*_head)->right) > (get_height((*_head)->left))) ? \
((*_head)->right)->height + 1 : ((*_head)->left)->height + 1;
if ((BF(*_head) == 2) && ((*_head)->left != NULL)) {
if (BF((*_head)->left) >= 0) Rotation_LL(&(*_head));
else if (BF((*_head)->left) == -1) Rotation_LR(&(*_head));
}
else if ((BF(*_head) == -2) && ((*_head)->right != NULL)) {
if (BF((*_head)->right) <= 0) Rotation_RR(&(*_head));
else if (BF((*_head)->right) == 1) Rotation_RL(&(*_head));
}
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::RotationAll (tree_node<K, T>** _head) {
if ((*_head)->left == NULL && (*_head)->right == NULL) {
(*_head)->height = 1;
return;
}
if ((*_head)->left != NULL) RotationAll(&((*_head)->left));
if ((*_head)->right != NULL) RotationAll(&((*_head)->right));
Rotation(&(*_head));
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::Rotation_LL (tree_node<K, T>** _head) {
tree_node<K, T>* pos = (*_head)->left;
(*_head)->left = pos->right;
pos->right = *_head;
(*_head)->height -=2;
*_head = pos;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::Rotation_LR (tree_node<K, T>** _head) {
tree_node<K, T>* pos1 = (*_head)->left;
tree_node<K, T>* pos2 = pos1->right;
(*_head)->left = pos2->right;
pos1->right = pos2->left;
pos2->left = pos1;
pos2->right = (*_head);
(*_head)->height -=2;
pos1->height -= 1;
pos2->height += 1;
*_head = pos2;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::Rotation_RR (tree_node<K, T>** _head) {
tree_node<K, T>* pos = (*_head)->right;
(*_head)->right = pos->left;
pos->left = *_head;
(*_head)->height -=2;
*_head = pos;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::Rotation_RL (tree_node<K, T>** _head) {
tree_node<K, T>* pos1 = (*_head)->right;
tree_node<K, T>* pos2 = pos1->left;
(*_head)->right = pos2->left;
pos1->left = pos2->right;
pos2->right = pos1;
pos2->left = (*_head);
(*_head)->height -=2;
pos1->height -= 1;
pos2->height += 1;
*_head = pos2;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
void AVL_Tree<K, T>::disposeAll_ (tree_node<K, T>** _head) {
if ((*_head) == NULL) return;
disposeAll_(&((*_head)->left));
disposeAll_(&((*_head)->right));
if ((*_head)->left == NULL && (*_head)->right == NULL) {
delete *_head;
*_head = NULL;
}
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
ostream& AVL_Tree<K, T>::print_ (ostream& _os, tree_node<K, T>* _root) {
if (_root == NULL) return _os;
print_(_os, _root->left);
_os << "key " << _root->key << " height " << _root->height << " digree " << BF(_root) << endl;
print_(_os, _root->right);
return _os;
}
/////////////////////////////////////////////////////////////////
#endif
/*
this class is special for the AVL tree node, it contains all
the important informations of the tree node, like his value,
key, height, pointers to the sub-treies, and 2 constructors.
the template takes the type of the key and the value.
*/
#ifndef _TREE_NODE_H_
#define _TREE_NODE_H_
#include <iostream.h>
/////////////////////////////////////////////////////////////////
template <class K, class T>
class tree_node {
public:
tree_node (const K&, T&);
tree_node (const tree_node&);
~tree_node ();
public:
T value; // value of the node
K key; // key of the node
int height; // hight from the leaf
tree_node<K, T>* right; // pointer to right sub-tree
tree_node<K, T>* left; // pointer to left sub-tree
};
/////////////////////////////////////////////////////////////////
// IMPLEMENTATION
/////////////////////////////////////////////////////////////////
template <class K, class T>
tree_node<K, T>::tree_node (const K& _k, T& _v) :
value(_v),
key(_k),
height(1),
right(NULL),
left(NULL)
{}
/////////////////////////////////////////////////////////////////
template <class K, class T>
tree_node<K, T>::tree_node (const tree_node& _n) {
value = _n.value;
key = _n.key;
height = _n.height;
}
/////////////////////////////////////////////////////////////////
template <class K, class T>
tree_node<K, T>::~tree_node () {}
/////////////////////////////////////////////////////////////////
#endif
هذا الموضوع مغلق.