AVL트리를 이용한 영어사전 만들기

https://sol248.tistory.com/61

AVL Tree

이전에 AVL트리의 특징과 구현하는 방법에 대해 알아보았습니다.

 

이번에는 AVL트리를 활용하여 간단한 영어사전을 만들어보겠습니다.

 

AVL트리는 알아서 균형을 맞춰주는 트리 형태이기에 

 

삽입, 삭제, 탐색의 시간 복잡도가 최악의 경우에도 O(log N) 이라는 장점이 있었죠.

 

마침 영어사전은 빠른 삽입, 빠른 삭제, 빠른 탐색이 요구되므로 한번 구현해보겠습니다.

 

앞에서 구현한 AVL트리는 탐색 기능이 없으므로 탐색 기능만 추가해주고,

 

영어사전 클래스를 하나 만들어서 AVL트리를 상속받으면 될 것 같습니다.

 

 

 

탐색 기능을 추가한 AVL)

class AVL {
 public:
  struct Word {
    std::string w;
    std::string m;
  };
  struct Node {
    Word word;
    Node* left = nullptr;
    Node* right = nullptr;
  };

  int height() { return height(root_); }
  int height(Node* node) {
    if (!node) return 0;
    return 1 + std::max(height(node->left), height(node->right));
  }

  int Balance(Node* node) {
    if (node)
      return height(node->left) - height(node->right);
    else
      return 0;
  }

  Node* RotateRight(Node* parent) {
    Node* cld = parent->left;
    parent->left = cld->right;
    cld->right = parent;
    return cld;
  }

  Node* RotateLeft(Node* parent) {
    Node* cld = parent->right;
    parent->right = cld->left;
    cld->left = parent;
    return cld;
  }

  void Insert(Word& word) { root_ = Insert(root_, word); }
  Node* Insert(Node* node, Word& word) {
    if (!node) return new Node{word, nullptr, nullptr};

    if (word.w < node->word.w) {
      node->left = Insert(node->left, word);
    } else if (word.w > node->word.w) {
      node->right = Insert(node->right, word);
    } else {
      node->word = word;
      return node;
    }

    int balance = Balance(node);

    if (balance == 0 || balance == 1 || balance == -1) return node;

    if (balance > 1 && Balance(node->left) >= 0) {
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) <= 0) {
      return RotateLeft(node);
    } else if (balance > 1 && Balance(node->left) <= -1) {
      node->left = RotateLeft(node->left);
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) >= 1) {
      node->right = RotateRight(node->right);
      return RotateLeft(node);
    }

    return node;
  }

  Node* MinKeyNode(Node* node) {
    while (node->left) node = node->left;
    return node;
  }

  void Remove(std::string& word) { root_ = Remove(root_, word); }
  Node* Remove(Node* node, std::string& word) {
    if (!node) return node;

    if (word < node->word.w) {
      node->left = Remove(node->left, word);
    } else if (word > node->word.w) {
      node->right = Remove(node->right, word);
    } else {
      if (!node->right) {
        Node* temp = node->left;
        delete node;
        return temp;
      } else if (!node->left) {
        Node* temp = node->right;
        delete node;
        return temp;
      }

      Node* temp = MinKeyNode(node->right);
      node->word = temp->word;
      node->right = Remove(node->right, temp->word.w);
    }

    int balance = Balance(node);

    if (balance == 0 || balance == 1 || balance == -1) return node;

    if (balance > 1 && Balance(node->left) >= 0) {
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) <= 0) {
      return RotateLeft(node);
    } else if (balance > 1 && Balance(node->left) <= -1) {
      node->left = RotateLeft(node->left);
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) >= 1) {
      node->right = RotateRight(node->right);
      return RotateLeft(node);
    }
    return node;
  }

  Node* search(Node* node, const std::string& word) const {
    if (!node || node->word.w == word) return node;

    if (word < node->word.w)
      return search(node->left, word);
    else
      return search(node->right, word);

    return nullptr;
  }

  void clear(Node* node) {}

 protected:
  Node* root_ = nullptr;
};

 

문자열도 대소관계가 있기에 비교하며 탐색할 수 있습니다.

 

다음은 영어사전 클래스입니다.

 

AVL클래스를 상속받아 영단어의 삽입과 탐색 기능을 하는 클래스입니다.

 

Dictionary Class)

class Dictionary : public AVL {
 public:
  using Node = AVL::Node;
  using Word = AVL::Word;

  Dictionary() = default;
  ~Dictionary() = default;

  std::string search(const std::string& word) const {
    Node* node = AVL::search(AVL::root_, word);

    if (node) {
      return node->word.m;
    } else {
      return "No result";
    }
  }

  void Insert(const std::string& w, const std::string& m) {
    Word word{w, m};
    AVL::Insert(word);
  }
};

 

AVL클래스를 상속받았기에 쉽게 구현할 수 있습니다.

 

다음은 이 클래스들을 작동시키는  main함수입니다.

 

편의를 위해 작업 디렉토리 안에 txt파일로 영단어와 그 뜻이 있는 파일을 생성하고

 

파일 입출력을 이용해 이를 불러와 트리를 구현하는 방식으로 진행하였습니다.

 

 

 

CPP파일)

 

txt파일을 불러와 한줄씩 읽어오며 트리를 만든 뒤,

 

사용자가 exit을 입력하기 전까지 단어를 입력받고,

 

입력받은 단어를 트리에서 찾아주는 구조입니다.

#include "Dic.h"

#include <fstream>
#include <iostream>

int main(void) {
  Dictionary dict;
  std::fstream file("eng_dic.txt");
  if (!file) {
    std::cerr << "Unable to open" << '\n';
    return 1;
  }

  std::string word, mean;
  while (getline(file, word)) {
    if (getline(file, mean)) {
      dict.Insert(word, mean);
    }
  }
  file.close();

  std::string input;
  while (true) {
    std::cout << "Input a word : ";
    std::getline(std::cin, input);

    if (input == "exit") break;

    std::string result = dict.search(input);
    std::cout << result << '\n';
  }

  return 0;
}

 

AVL을 이해하셨다면 이번 영단어 사전 만들기는 쉽게 느껴지셨을 수도 있습니다.

 

상속을 받아 탐색 기능만 추가하면 바로 만들 수 있으니까요.

 

 

 

 

 

저는 이 사이트에서 자료구조/알고리즘을 공부중인데 스스로 생각하면서 구현할 기회를 제공하고

 

다양한 예제로 연습도 할 수 있어 정말 좋다고 느끼고 있습니다.

 

그리고 만약 c++을 잘 모르시더라도 c++을 짧은 시간안에 습득할 수 있도록 하는 강의도 무료로 열려있으니 

 

c++에 관심이 있으시다면 한번 보시는 것을 추천드립니다.

 

짧은 시간안에 새로운 언어 학습을 하는 것에 매우 큰 장점입니다.

https://honglab.co.kr/

honglab