Advertisement
Guest User

Untitled

a guest
Apr 25th, 2014
40
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. template<typename T>
  2. class AVLNode
  3. {
  4. public:
  5. AVLNode(T, AVLNode<T>*, AVLNode<T>*, int);
  6. ~AVLNode();
  7. void setLeft(AVLNode<T>*);
  8. AVLNode<T>* getLeft() const;
  9. void setRight(AVLNode<T>*);
  10. AVLNode<T>* getRight() const;
  11. void setHeight(int);
  12. void setKey(const T& );
  13. int getHeight() const;
  14. const T& getKey() const;
  15.  
  16. private:
  17. T key;
  18. AVLNode<T> *left;
  19. AVLNode<T> *right;
  20. int height;
  21. };
  22.  
  23. template<typename T>
  24. AVLNode<T>* AVLTree<T>::rotateRight(AVLNode<T> *node1)
  25. {
  26. AVLNode<T> *node2 = node1->getLeft();
  27. AVLNode<T> *T2 = node2->getRight();
  28.  
  29. // Perform rotation
  30. node2->setRight(node1);
  31. node1->setLeft(T2);
  32.  
  33. // Update heights
  34. node1->setHeight(max(height(node1->getLeft()), height(node1->getRight()))+1);
  35. node2->setHeight(max(height(node2->getLeft()), height(node2->getRight()))+1);
  36.  
  37. // Return new root
  38. return node2;
  39. }
  40.  
  41. template <typename T>
  42. class AVLNode
  43. {
  44. protected:
  45. T key;
  46. AVLNode<T>* left;
  47. AVLNode<T>* right;
  48. int height;
  49.  
  50. public:
  51. AVLNode<T>* getRight() const { return right: }
  52. AVLNode<T>* getLeft() const { return left; }
  53. };
  54.  
  55. template <typename T>
  56. class WritableAVLNode : public AVLNode<T>
  57. {
  58. public:
  59. void setRight(AVLNode<T>* right) { AVLNode<T>::right = right; }
  60. void setLeft(AVLNode<T>* left) { AVLNode<T>::left = left; }
  61. };
  62.  
  63. template <typename T>
  64. class AVLNode
  65. {
  66. friend class AVLTree<T>;
  67. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement