freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/data-structures/create-a-trie-search-tree.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d8259367417b2b2512c84	Створення префіксного дерева пошуку	1	301634	create-a-trie-search-tree

--description--

Далі ми відійдемо від вивчення двійкового дерева пошуку та розглянемо структуру іншого виду дерева пошуку під назвою префіксне. Префіксне дерево пошуку - це впорядкований вид дерева пошуку, який зазвичай містить рядки, досить часто дозволяє зберігати асоціативні масиви або динамічні сукупності даних, ключами яких є рядки. Їхньою перевагою є зберігання наборів даних у тих випадках, коли багато ключів мають однакові префікси, як-от усі слова у словнику. На відміну від двійкового дерева, вузли не пов'язані з реальними значеннями. Натомість шлях до вузла визначає певний ключ. До прикладу, якщо нам потрібно зберегти у префіксному дереві пошуку код у вигляді рядка, ми отримаємо чотири вузли, по одному на кожну букву: c — o — d — e. Застосовуючи цей шлях до всіх вузлів, ми отримаємо код у вигляді рядка, а сам шлях є ключем, який ми зберегли. Далі, якби ми хотіли додати рядкове кодування, він би розділив перші три вузли коду перед тим, як розгалузитись після d. У такому випадку, великий обсяг даних може зберігатися дуже компактно. Окрім цього, пошук може відбуватися дуже швидко, оскільки він практично обмежений довжиною рядка, який ми зберігаємо. А ще, на відміну від двійкових дерев вузол може зберігати будь-яку кількість дочірніх вузлів. Як можна було здогадатися із наведеного вище прикладу, деякі метадані зазвичай зберігаються у вузлах, які містять кінець ключа, тому під час наступних обходів дерева цей ключ все ще можна відновити. Скажімо, якби ми додали коди у зазначений вище приклад, нам потрібно було б якось дізнатися, що е в коді означає кінець введеного раніше ключа. В іншому випадку ця інформація буде втрачена при додаванні кодів.

--instructions--

Створімо префіксне дерево пошуку для зберігання слів. Воно буде отримувати слова за допомогою методу add і зберігати їх у структурі даних префіксного дерева пошуку. А також він допоможе нам дізнатися, чи даний рядок містить слово з методом isWord, і вилучить всі слова, введені у префіксне дерево пошуку за допомогою способу print. Метод isWord повинен повернути логічне значення, а метод print - повернути масив всіх цих слів у вигляді рядкових значень. Аби впевнитись, що ця структура даних реалізована правильно, ми задали структуру Node для кожного вузла у дереві. Кожен вузол буде об'єктом із властивістю keys, яка є об'єктом JavaScript Map. Він міститиме окремі літери, які виступають дійсними ключами кожного вузла. Також ми створили для вузлів властивість end, яка може бути налаштована як true, якщо вузол являє собою закінчення слова.

--hints--

Префіксне дерево пошуку має містити метод add.

assert(
  (function testTrie() {
    var test = false;
    if (typeof Trie !== 'undefined') {
      test = new Trie();
    } else {
      return false;
    }
    return typeof test.add == 'function';
  })()
);

Префіксне дерево пошуку має містити метод print.

assert(
  (function testTrie() {
    var test = false;
    if (typeof Trie !== 'undefined') {
      test = new Trie();
    } else {
      return false;
    }
    return typeof test.print == 'function';
  })()
);

Префіксне дерево пошуку має містити метод isWord.

assert(
  (function testTrie() {
    var test = false;
    if (typeof Trie !== 'undefined') {
      test = new Trie();
    } else {
      return false;
    }
    return typeof test.isWord == 'function';
  })()
);

Метод print має повернути всі елементи, додані до префіксного дерева пошуку у вигляді рядків масиву.

assert(
  (function testTrie() {
    var test = false;
    if (typeof Trie !== 'undefined') {
      test = new Trie();
    } else {
      return false;
    }
    test.add('jump');
    test.add('jumps');
    test.add('jumped');
    test.add('house');
    test.add('mouse');
    var added = test.print();
    return (
      added.indexOf('jump') != -1 &&
      added.indexOf('jumps') != -1 &&
      added.indexOf('jumped') != -1 &&
      added.indexOf('house') != -1 &&
      added.indexOf('mouse') != -1 &&
      added.length == 5
    );
  })()
);

Метод isWord має повернути true лише для слів, доданих до префіксного дерева пошуку, і false - для всіх інших слів.

assert(
  (function testTrie() {
    var test = false;
    if (typeof Trie !== 'undefined') {
      test = new Trie();
    } else {
      return false;
    }
    test.add('hop');
    test.add('hops');
    test.add('hopped');
    test.add('hoppy');
    test.add('hope');
    return (
      test.isWord('hop') &&
      !test.isWord('ho') &&
      test.isWord('hopped') &&
      !test.isWord('hopp') &&
      test.isWord('hoppy') &&
      !test.isWord('hoping')
    );
  })()
);

--seed--

--seed-contents--

var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
var Node = function() {
  this.keys = new Map();
  this.end = false;
  this.setEnd = function() {
    this.end = true;
  };
  this.isEnd = function() {
    return this.end;
  };
};
var Trie = function() {
  // Only change code below this line

  // Only change code above this line
};

--solutions--

// solution required