/
AVL_Tree.h
52 lines (44 loc) · 1.33 KB
/
AVL_Tree.h
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
//==================================================================
// Code203_Tree.h
// Demonstration of an AVL tree which keeps the tree nodes in as
// near perfect balance as possible.
// Author: Dr. Rick Coleman
//==================================================================
#ifndef AVL_TREE_H
#define AVL_TREE_H
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct AVLTreeNode
{
string key;
vector<int> docs;
AVLTreeNode *left;
AVLTreeNode *right;
AVLTreeNode *parent;
char balanceFactor;
};
class AVL_Tree
{
private:
AVLTreeNode *root;
public:
AVL_Tree(); // Constructor
~AVL_Tree(); // Destructor
void Insert(AVLTreeNode *n);
void restoreAVL(AVLTreeNode *ancestor, AVLTreeNode *newNode);
void adjustBalanceFactors(AVLTreeNode *end, AVLTreeNode *start);
void rotateLeft(AVLTreeNode *n);
void rotateRight(AVLTreeNode *n);
void adjustLeftRight(AVLTreeNode *end, AVLTreeNode *start);
void adjustRightLeft(AVLTreeNode *end, AVLTreeNode *start);
void PrintTree();
vector<int> getDocsForWord(string word);
void addDocToWord(string word, int docIndex);
AVLTreeNode* find(string word);
private:
void ClearTree(AVLTreeNode *n);
void Print(AVLTreeNode *n);
};
#endif