Вузол (інформатика)
Вузол (англ. node) в інформатиці — це основний елемент або точка, яка є частиною більшої структури. Він може бути пристроєм у мережі, окремим записом даних у базі, точкою з'єднання в графі або іншим важливим компонентом у будь-якій системі. Поняття «вузол» зустрічається в багатьох сферах інформатики, допомагаючи описувати, як елементи взаємодіють і утворюють складніші системи.
У контексті комп'ютерних мереж та Інтернету, вузол — це будь-який пристрій або точка, що має можливість надсилати, отримувати або перенаправляти інформацію. До мережевих вузлів належать:
- Пристрої: персональні комп'ютери, сервери, стільникові телефони, принтери, маршрутизатори, комутатори.
- IP-адреса: У контексті Інтернету вузлом вважається будь-який об'єкт, що має унікальну IP-адресу. Ця система вузлів використовується для визначення місцезнаходження об'єктів у мережі.
У структурах даних, таких як зв'язані списки та дерева, вузол є базовим елементом, що містить дані та може посилатися на інші вузли. Зв'язки між вузлами зазвичай реалізуються за допомогою покажчиків.
Дерево — це ієрархічна структура даних, яка складається з вузлів, пов'язаних між собою ребрами. Вузли в дереві мають певну ієрархічну залежність[1]:
- Кореневий вузол: Це найвищий вузол у дереві. Він не має батьківського вузла, але є батьківським для всіх вузлів, що розташовані нижче в дереві.
- Батьківський вузол: Вузол, від якого походить інший вузол (дочірній).
- Дочірній вузол: Вузол, що походить від іншого вузла. Наприклад, комп'ютер з доступом до Інтернету може розглядатися як дочірній вузол для вузла, що представляє Інтернет-шлюз.
- Вузли-родичі: Це вузли, які підключені до одного батьківського вузла (є «братами/сестрами»).
- Внутрішній вузол: Вузол, який має принаймні одного дочірнього вузла.
- Кінцевий (листовий) вузол: Вузол, що не має дочірніх елементів.
Характеристики вузлів у дереві[2]:
- Ступінь: Кількість дочірніх вузлів.
- Глибина: Довжина шляху (кількість ребер) від кореневого вузла до даного вузла. Кореневий вузол має глибину 0.
- Висота: Довжина найдовшого шляху (кількість ребер) від даного вузла до найвіддаленішого листового вузла, що є його нащадком. Висота дерева дорівнює висоті кореневого вузла.
- Ребро (Edge): Це зв'язок між двома вузлами.
- Ліс: Це набір дерев, що не мають спільних вузлів.
- Розмір дерева: Розмір (англ. size) дерева визначається як загальна кількість вузлів у ньому. Наприклад, дерево, показане на зображенні, має розмір 9, оскільки воно містить дев'ять окремих вузлів.
У теорії графів мережа візуалізується за допомогою графічного зображення, де кожен вузол (вершина) відповідає окремій точці або об'єкту, а ребра (дуги) представляють зв'язки між ними. Це спрощує сприйняття та аналіз складних взаємозв'язків.
Деревоподібні структури широко використовуються у веброзробці, зокрема в об'єктній моделі документа (DOM). DOM є програмним інтерфейсом для HTML та XML документів, що дозволяє програмам отримувати доступ до вмісту документа та маніпулювати ним. Кожен елемент, атрибут або текстовий фрагмент вебсторінки представлений у DOM як вузол.
XML (Extensible Markup Language) слугує для обміну інформацією між програмістами та комп'ютерами, ставши основою для створення спільних комунікаційних протоколів (наприклад, для офісного програмного забезпечення) та розробки сучасних мов розмітки, таких як XHTML. Хоча HTML і CSS зазвичай використовуються для створення текстового контенту та дизайну вебсайтів, XML, HTML та XHTML забезпечують структуру та виразність, тоді як DOM виконує функцію «перекладача», дозволяючи взаємодіяти з цією структурою[3].
Різні типи вузлів у дереві DOM представлені специфічними інтерфейсами. Тип вузла визначається його взаємодією з іншими вузлами та його властивістю nodeType. Наприклад, якщо властивість nodeType має значення ELEMENT_NODE, це свідчить про те, що вузол є елементом об'єкта, і цей об'єкт використовує інтерфейс Element для визначення всіх методів і властивостей, що стосуються даного вузла.
Консорціум Всесвітньої павутини (W3C) визначає такі основні типи вузлів DOM:
| Числове значення | Постійна назва (Named constant) | Опис |
|---|---|---|
| 1 | ELEMENT_NODE | Представляє HTML- або XML-елемент (наприклад, <p>, <div>) |
| 2 | ATTRIBUTE_NODE | Атрибут елемента (наприклад, href в <a href="...">) |
| 3 | TEXT_NODE | Текстовий вміст (наприклад, «Привіт світ!» у <p>Привіт світ!</p>) |
| 4 | CDATA_SECTION_NODE | Секція CDATA (використовується в XML) |
| 5 | ENTITY_REFERENCE_NODE | Посилання на сутність (застаріло в HTML5) |
| 6 | ENTITY_NODE | Сутність |
| 7 | PROCESSING_INSTRUCTION_NODE | Інструкція обробки (наприклад, <?xml-stylesheet …?>) |
| 8 | COMMENT_NODE | Коментар (наприклад, ``Коментар``) |
| 9 | DOCUMENT_NODE | Весь документ (кореневий вузол) |
| 10 | DOCUMENT_TYPE_NODE | Оголошення типу документа (наприклад, <!DOCTYPE html>) |
| 11 | DOCUMENT_FRAGMENT_NODE | Легкий «контейнер» для фрагментів документа |
| 12 | NOTATION_NODE | Нотація (використовується в XML) |
Об'єкт вузла в дереві DOM представлений окремим вузлом, який може бути вузлом елемента, атрибута, текстовим вузлом або будь-яким іншим типом. Усі об'єкти можуть успадковувати властивості та методи для взаємодії з батьківськими та дочірніми вузлами, хоча не всі з них мають такі вузли. Наприклад, текстові вузли не можуть мати дочірніх вузлів, і спроба додати дочірні вузли до них призведе до помилки DOM.
Об'єкти в дереві DOM можна адресувати та маніпулювати ними за допомогою методів, доступних через інтерфейс прикладного програмування (API). Історія об'єктної моделі документа тісно пов'язана з «війнами браузерів» наприкінці 1990-х років між Netscape Navigator та Internet Explorer, а також з JavaScript і JScript — першими мовами сценаріїв, які отримали широке впровадження в системах веббраузерів.
- ↑ Black, Paul E. (15 грудня 2017). tree. Dictionary of Algorithms and Data Structures (from Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999) (англ.). National Institute of Standards and Technology (NIST). Архів оригіналу за 24 листопада 2014. Процитовано 10 червня 2025.
- ↑ Harvey, Brian (1999). Trees. Simply Scheme: Introducing Computer Science, 2/e (Chapter 18) (англ.). EECS, University of California, Berkeley. Процитовано 10 червня 2025.
- ↑ Introduction to the DOM (англ.). MDN Web Docs. Процитовано 10 червня 2025.
- Data Trees as a Means of Presenting Complex Data Analysis (англ.) [Архівовано 19 липня 2018 у Wayback Machine.] авторства Саллі Кніп
