Advertisement
Guest User

Untitled

a guest
Jul 30th, 2015
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.63 KB | None | 0 0
  1. #ifndef AVL_H
  2. #define AVL_H
  3.  
  4. #include <iostream>
  5. #include <stdlib.h>
  6. #include <stack>
  7. #include "../data_structs/queueLL.h"
  8.  
  9. using std::stack;
  10.  
  11. template<typename T>
  12. class AVL{
  13. private:
  14. class Vertex{
  15. public:
  16. int height;
  17. Vertex() :
  18. height(0), right(nullptr), left(nullptr){}
  19.  
  20. Vertex(const T& data) :
  21. height(0), right(nullptr), left(nullptr), data(data){}
  22.  
  23. Vertex(const T& data, Vertex* left, Vertex* right) :
  24. height(0), right(right), left(left), data(data){}
  25.  
  26. Vertex* right;
  27. Vertex* left;
  28. T data;
  29. };
  30.  
  31. enum WeightStatus{BALANCED, LEFT_HEAVY, RIGHT_HEAVY, ERROR};
  32.  
  33. Vertex* root;
  34.  
  35. //keeps track of the vertex when a find operation has been executed
  36. Vertex* finder;
  37.  
  38. int numberOfElements;
  39.  
  40. ///Helper Functions///
  41. void insert(const T& entry, Vertex*& current);
  42. void remove(const T& target, Vertex*& current);
  43.  
  44. void clear(Vertex*& current);
  45. void displayInOrder(const Vertex* current);
  46. void displayPreOrder(const Vertex* current);
  47. void displayPostOrder(const Vertex* current);
  48.  
  49. Vertex* find(Vertex* current, const T& target) const;
  50. const Vertex* getMin(const Vertex* current) const;
  51. const Vertex* getMax(const Vertex* current) const;
  52. int getHeight(const Vertex* current) const;
  53. WeightStatus getWeight(const Vertex* current) const;
  54.  
  55. void balance(Vertex*& current);
  56. void leftRotation(Vertex*& current);
  57. void rightRotation(Vertex*& current);
  58. void updateHeight(Vertex*& current);
  59.  
  60. int max(int a, int b) const;
  61.  
  62. public:
  63. class Iterator{
  64. private:
  65. stack<Vertex*> parents;
  66. Vertex* current = nullptr;
  67. public:
  68. Iterator(){}
  69. Iterator(Vertex* const begin){
  70. current = begin;
  71. }
  72.  
  73. T& getData() const{
  74. return current->data;
  75. }
  76.  
  77. //in order traversal through tree
  78. T& next(){
  79. //go all the way to the left - current is null after the loop
  80. while(current){
  81. parents.push(current);
  82. current = current->left;
  83. }
  84. //get parent
  85. current = parents.top();
  86. parents.pop();
  87.  
  88. //save current
  89. Vertex* temp = current;
  90.  
  91. //go to the right of the tree
  92. current = current->right;
  93. return temp->data;
  94. }
  95. bool hasNext(){
  96. return current != nullptr || !parents.empty();
  97. }
  98. //the stack gets reset - only the current Vertex is copied
  99. Iterator operator=(const Iterator& src){
  100. if(this == &src)
  101. return *this;
  102. this->current = src.current;
  103. return *this;
  104. }
  105.  
  106. bool operator==(const Iterator& i){
  107. return current == i.current;
  108. }
  109. bool operator!=(const Iterator& i){
  110. return current != i.current;
  111. }
  112. };
  113.  
  114. AVL();
  115. AVL(const AVL& src);
  116. ~AVL();
  117.  
  118. void insert(const T& entry);
  119. void remove(const T& target);
  120.  
  121. bool find(const T& target);
  122.  
  123. Iterator get(const T& target);
  124.  
  125. //Should only be called if find() returned true;
  126. const T& getFoundData() const;
  127.  
  128. const T& getMin() const;
  129. const T& getMax() const;
  130. int getHeight() const;
  131.  
  132. void display(); //inOrderDisplay - generic name
  133. void displayInOrder();
  134. void displayPreOrder();
  135. void displayPostOrder();
  136. void displayLevelOrder();
  137. const T& getRootValue();
  138.  
  139. int size();
  140. bool isEmpty();
  141. void clear();
  142.  
  143. const Iterator begin() const;
  144. const Iterator end() const;
  145. };
  146.  
  147. template<typename T>
  148. AVL<T>::AVL() :
  149. root(nullptr), finder(nullptr), numberOfElements(0)
  150. {}
  151.  
  152. template<typename T>
  153. AVL<T>::AVL(const AVL& src){
  154. root = nullptr;
  155. finder = nullptr;
  156.  
  157. Iterator src_itr;
  158. src_itr = src.begin();
  159. while(src_itr.hasNext())
  160. this->insert(src_itr.next());
  161. }
  162.  
  163. template<typename T>
  164. AVL<T>::~AVL(){
  165. clear();
  166. }
  167.  
  168. template<typename T>
  169. void AVL<T>::insert(const T& entry){
  170. insert(entry, root);
  171. }
  172.  
  173. template<typename T>
  174. void AVL<T>::remove(const T& target){
  175. remove(target, root);
  176. }
  177.  
  178. template<typename T>
  179. bool AVL<T>::find(const T& target){
  180. finder = find(root, target);
  181. return (finder);
  182. }
  183.  
  184. template<typename T>
  185. typename AVL<T>::Iterator AVL<T>::get(const T& target){
  186. return Iterator(find(root, target));
  187. }
  188.  
  189. template<typename T>
  190. const T& AVL<T>::getFoundData() const {
  191. return finder->data;
  192. }
  193.  
  194. template<typename T>
  195. const T& AVL<T>::getMin() const{
  196. return getMin(root)->data;
  197. }
  198.  
  199. template<typename T>
  200. const T& AVL<T>::getMax() const{
  201. return getMax(root)->data;
  202. }
  203.  
  204. template<typename T>
  205. int AVL<T>::getHeight() const{
  206. return getHeight(root);
  207. }
  208.  
  209. template<typename T>
  210. void AVL<T>::display(){
  211. displayInOrder(root);
  212. }
  213.  
  214. //left-parent-right
  215. template<typename T>
  216. void AVL<T>::displayInOrder(){
  217. displayInOrder(root);
  218. }
  219.  
  220. //parent-left-right
  221. template<typename T>
  222. void AVL<T>::displayPreOrder(){
  223. displayPreOrder(root);
  224. }
  225.  
  226. //left right parent
  227. template<typename T>
  228. void AVL<T>::displayPostOrder(){
  229. displayPostOrder(root);
  230. }
  231.  
  232. template<typename T>
  233. void AVL<T>::displayLevelOrder(){
  234. QueueLL<Vertex*> container;
  235. container.enqueue(root);
  236. while(!container.empty()){
  237. Vertex* current = container.dequeue();
  238. if(current != nullptr){
  239.  
  240. //display parent
  241. std::cout << current->data << std::endl;
  242.  
  243. //enqueue children for future printing
  244. container.enqueue(current->left);
  245. container.enqueue(current->right);
  246. }
  247. }
  248. }
  249.  
  250. template<typename T>
  251. const T& AVL<T>::getRootValue(){
  252. return root->data;
  253. }
  254.  
  255. template<typename T>
  256. int AVL<T>::size(){
  257. return numberOfElements;
  258. }
  259.  
  260. template<typename T>
  261. bool AVL<T>::isEmpty(){
  262. return root == nullptr;
  263. }
  264.  
  265. template<typename T>
  266. void AVL<T>::clear(){
  267. clear(root);
  268. }
  269.  
  270. template<typename T>
  271. const typename AVL<T>::Iterator AVL<T>::begin() const{
  272. return Iterator(root);
  273. }
  274.  
  275. template<typename T>
  276. const typename AVL<T>::Iterator AVL<T>::end() const{
  277. return Iterator(nullptr);
  278. }
  279.  
  280. ///Helper Functions///
  281. template<typename T>
  282. void AVL<T>::insert(const T& entry, Vertex*& current){
  283. //empty slot found
  284. if(current == nullptr){
  285. current = new Vertex(entry);
  286. ++numberOfElements;
  287. }
  288.  
  289. //larger values go to right of tree
  290. else if(entry > current->data)
  291. insert(entry, current->right);
  292.  
  293. //smaller values go to the left
  294. else
  295. insert(entry, current->left);
  296.  
  297. updateHeight(current);
  298.  
  299. //balance every vertex(if needed) along the traversed path
  300. balance(current);
  301. }
  302.  
  303. template<typename T>
  304. void AVL<T>::remove(const T& target, Vertex*& current){
  305. //search for the target
  306. if(current != nullptr){
  307. //found
  308. if(target == current->data){
  309. --numberOfElements;
  310. //full node case
  311. if(current->left && current->right){
  312. int r = rand() % 2;
  313. //replace data with maximum vertex data in left substree
  314. if(r == 0){
  315. Vertex* max = const_cast<Vertex*>(getMax(current->left));
  316. current->data = max->data;
  317. delete max;
  318. max = nullptr;
  319. }
  320. //replace data with minimum vertex data in right substree
  321. else{
  322. Vertex* min = const_cast<Vertex*>(getMin(current->right));
  323. current->data = min->data;
  324. delete min;
  325. min = nullptr;
  326. }
  327. }
  328. //left child exists - create link from current's parent to current's child
  329. else if(current->left){
  330. Vertex* child = current->left;
  331. delete current;
  332. current = child;
  333. }
  334. //right child exists - create link from current's parent to current's child
  335. else if(current->right){
  336. Vertex* child = current->right;
  337. delete current;
  338. current = child;
  339. }
  340. //leaf
  341. else{
  342. delete current;
  343. current = nullptr;
  344. }
  345. }
  346. //search left
  347. else if(target > current->data)
  348. remove(target, current->right);
  349.  
  350. //search right
  351. else
  352. remove(target, current->left);
  353. }
  354. updateHeight(current);
  355.  
  356. //balance every vertex(if needed) along the traversed path
  357. balance(current);
  358. }
  359.  
  360. template<typename T>
  361. typename AVL<T>::Vertex* AVL<T>::find(Vertex* current, const T& target) const{
  362.  
  363. //return a default T
  364. if(current == nullptr)
  365. return current;
  366.  
  367. //found
  368. if(target == current->data)
  369. return current;
  370.  
  371. //search left
  372. else if(target < current->data)
  373. return find(current->left, target);
  374.  
  375. //search right
  376. else
  377. return find(current->right, target);
  378. }
  379.  
  380. //return the left most vertex
  381. template<typename T>
  382. const typename AVL<T>::Vertex* AVL<T>::getMin(const Vertex* current) const{
  383. if(current == nullptr)
  384. return current;
  385. while(current->left != nullptr)
  386. current = current->left;
  387. return current;
  388. }
  389.  
  390. //return the right most vertex
  391. template<typename T>
  392. const typename AVL<T>::Vertex* AVL<T>::getMax(const Vertex* current) const{
  393. if(current == nullptr)
  394. return current;
  395. while(current->right != nullptr)
  396. current = current->right;
  397. return current;
  398. }
  399.  
  400. template<typename T>
  401. int AVL<T>::getHeight(const Vertex* current) const{
  402. if(current == nullptr)
  403. return -1;
  404. return current->height;
  405. }
  406.  
  407. template<typename T>
  408. typename AVL<T>::WeightStatus AVL<T>::getWeight(const Vertex* current) const{
  409. if(current == nullptr)
  410. return ERROR;
  411.  
  412. int l = getHeight(current->left);
  413. int r = getHeight(current->right);
  414. int diff = l - r;
  415.  
  416. if(diff > 1 ) return LEFT_HEAVY;
  417. if(diff < -1) return RIGHT_HEAVY;
  418. return BALANCED;
  419. }
  420.  
  421. template<typename T>
  422. void AVL<T>::balance(Vertex*& current){
  423. if(current != nullptr){
  424. WeightStatus w = getWeight(current);
  425.  
  426. //left heavy
  427. if(w == LEFT_HEAVY){
  428. w = getWeight(current->left);
  429.  
  430. //left-left heavy
  431. if(w == LEFT_HEAVY || w == BALANCED)
  432. rightRotation(current);
  433.  
  434. //left-right heavy
  435. else{
  436. leftRotation(current->left);
  437. rightRotation(current);
  438. }
  439. }
  440. //right heavy
  441. else if(w == RIGHT_HEAVY){
  442. w = getWeight(current->right);
  443.  
  444. //right-right heavy
  445. if(w == RIGHT_HEAVY || w == BALANCED)
  446. leftRotation(current);
  447.  
  448. //right-left heavy
  449. else{
  450. rightRotation(current->right);
  451. leftRotation(current);
  452. }
  453. }
  454. }
  455. }
  456.  
  457. template<typename T>
  458. void AVL<T>::leftRotation(Vertex*& current){
  459. if(current != nullptr){
  460. Vertex* newLeftChild = current;
  461. Vertex* newCurrent = current->right;
  462. Vertex* newLeftRightChild = current->right->left;
  463.  
  464. current = newCurrent; //height changes
  465. current->left = newLeftChild; //height changes
  466. current->left->right = newLeftRightChild; //height doesn't change
  467.  
  468. //update heights
  469. updateHeight(current->left);
  470. updateHeight(current);
  471. }
  472. }
  473.  
  474. template<typename T>
  475. void AVL<T>::rightRotation(Vertex*& current){
  476. if(current != nullptr){
  477. Vertex* newRightChild = current;
  478. Vertex* newCurrent = current->left;
  479. Vertex* newRightLeftChild = current->left->right;
  480.  
  481. current = newCurrent;
  482. current->right = newRightChild;
  483. current->right->left = newRightLeftChild;
  484.  
  485. //update heights
  486. updateHeight(current->right);
  487. updateHeight(current);
  488. }
  489. }
  490.  
  491. template<typename T>
  492. void AVL<T>::updateHeight(Vertex*& current){
  493. if(current != nullptr){
  494. int l = getHeight(current->left);
  495. int r = getHeight(current->right);
  496. current->height = 1 + max(l, r);
  497. }
  498. }
  499.  
  500. template<typename T>
  501. void AVL<T>::displayInOrder(const Vertex* current){
  502. if(current != nullptr){
  503. //print left subtree
  504. displayInOrder(current->left);
  505. //print parent
  506. std::cout << current->data << std::endl;
  507. //print right subtree
  508. displayInOrder(current->right);
  509. }
  510. }
  511.  
  512. template<typename T>
  513. void AVL<T>::displayPreOrder(const Vertex* current){
  514. if(current != nullptr){
  515. std::cout << current->data << std::endl;
  516. displayInOrder(current->left);
  517. displayInOrder(current->right);
  518. }
  519. }
  520.  
  521. template<typename T>
  522. void AVL<T>::displayPostOrder(const Vertex* current){
  523. if(current != nullptr){
  524. displayInOrder(current->left);
  525. displayInOrder(current->right);
  526. std::cout << current->data << std::endl;
  527. }
  528. }
  529.  
  530. template<typename T>
  531. void AVL<T>::clear(Vertex*& current){
  532. if(current != nullptr){
  533. //go to children
  534. clear(current->right);
  535. clear(current->left);
  536.  
  537. //delete parent
  538. delete current;
  539. current = nullptr;
  540. }
  541. }
  542.  
  543. template<typename T>
  544. int AVL<T>::max(int a, int b) const{
  545. return (a > b) ? a : b;
  546. }
  547.  
  548. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement