CS130A-AVL-Trees/Node.h at master · ashleyswang/CS130A-AVL-Trees · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#ifndef NODE_H
#define NODE_H

#include <algorithm>

class Node{

	public:

		// Constructors
		Node(int key){
			this->key = key;
			parent = nullptr;
			leftChild = nullptr;
			rightChild = nullptr;
			height = 0;
		};

		~Node(){
			delete leftChild;
			delete rightChild;
		};

		// Accessors
		int getKey(){ return key; };
		Node* getParent(){ return parent; };
		Node* getLeft(){ return leftChild; };
		Node* getRight(){ return rightChild; };
		int getHeight(){ return height; };
		int balance(){
			int leftHeight;
			int rightHeight;

			if(leftChild == nullptr)
				leftHeight = -1;
			if(leftChild != nullptr)
				leftHeight = leftChild->getHeight();
			if(rightChild == nullptr)
				rightHeight = -1;
			if(rightChild != nullptr)
				rightHeight = rightChild->getHeight();

			return rightHeight - leftHeight;
		};

		// for avl.cpp print functions
		bool isLeft(){
			if(key < parent->getKey()){
				return true;
			} else {
				return false;
			}
		}

		bool isTall(){

			if (parent == nullptr){
				return false;
			}

			int parentKey = parent->getKey();
			Node* sibling;

			// if only child of parent
			if(parent->getLeft()==nullptr || parent->getRight()==nullptr){
				return true;
			}

			// set sibling node
			if(key < parentKey){
				sibling = parent->getRight();
			} else {
				sibling = parent->getLeft();
			}

			// compare height with sibling
			if (height > sibling->getHeight()){
				return true;
			} else if (height < sibling->getHeight()){
				return false;
			} else {
				return parent->isTall();
			}

		}


		// Modifier
		void setKey(int key){ this->key = key; };
		void setParent(Node* parent){ this->parent = parent; };
		void setLeft(Node* leftChild){ this->leftChild = leftChild; };
		void setRight(Node* rightChild){ this-> rightChild = rightChild; };
		void increaseHeight(){ height++; };
		void setHeight(){
			int leftHeight;
			int rightHeight;

			if(leftChild == nullptr)
				leftHeight = -1;
			if(leftChild != nullptr)
				leftHeight = leftChild->getHeight();
			if(rightChild == nullptr)
				rightHeight = -1;
			if(rightChild != nullptr)
				rightHeight = rightChild->getHeight();

			this->height = std::max(leftHeight+1, rightHeight+1);
		};
		void setHeight(int height){ this->height = height; };


	private:
		int key;
		Node* parent;
		Node* leftChild;
		Node* rightChild;
		int height;

};

#endif