Вступ до дерев у програмуванні: кисень ефективного кодування

Багато разів ви хочете зберегти інформацію у своїй програмі та отримати до неї доступ багато разів. І ви часто будете зберігати його у дуже простій структурі даних: масиві. І це часто працює дуже добре! Але іноді просто потрібно багато часу, щоб закінчити.

Отже, для оптимізації такого роду програм багато розумних людей розробили деякі дивні речі, які ми називаємо структурами даних . Сьогодні я буду звертатися до деяких основ з цієї теми, і обговорюватиму одну конкретну структуру, про яку часто запитують під час кодування інтерв’ю і зводить усіх з розуму: дерева.

Я не буду занурюватися багато в код, лише в теорію того, як все працює. У мережі є мільйони зразків коду, тож просто погляньте на один, після того, як зрозумієте, як працюють дерева!

То що насправді є структурою даних?

За даними Вікіпедії:

" Структура даних - це формат даних та формат зберігання, що забезпечує ефективний доступ та модифікацію"

Це в основному означає, що це не що інше, як написаний код, щоб створити складний спосіб зберігання даних. Існує багато структур даних, які ви можете реалізувати, і кожна з них має певне завдання. Вони можуть перейти від справді простих - наприклад, пов’язаних списків - до справді складних структур - як графіки.

Дерева досить складні, щоб бути дуже швидкими в тому, що вони роблять, але досить прості, щоб їх можна було зрозуміти. І одна річ, в якій вони справді гарні - це пошук значень із мінімальним використанням пам’яті.

Але як виміряти, наскільки ефективною є структура даних?

Ви коли-небудь бачили якісь дивні позначення, які люди використовують в Інтернеті, наприклад O (n)? Це називається Big O Notation, і це стандартний спосіб оцінки продуктивності структур та алгоритмів. Великим O, який ми використовуємо, є подання найгіршого сценарію: наявність чогось, що є O (n) (при n - кількість елементів всередині), означає, що в гіршому випадку потрібен час n , що насправді добре.

Всередині дужки ми написали n, що є еквівалентом написання виразу y = x →. Це пропорційно масштабується. Але іноді ми маємо різні вирази:

  • O (1)
  • O (журнал (n))
  • O (n)
  • O (n²)
  • O (n³)
  • О (н!)
  • O (e ^ n)

Чим нижчий результат функції, тим ефективнішою є структура.

Існує кілька видів дерев. Ми будемо говорити про BST (Бінарні дерева пошуку) та AVL Дерева (Автоматично збалансовані дерева), які мають різні властивості:

Гаразд, ти говорив про всі ці дивні позначення ... так як працюють дерева?

Дерево імен походить від його реального подання: воно має корінь, листя та гілки, і його часто представляють так:

Ми використовуємо декілька номіналів, а саме батьків та дітей, які мають унікальні стосунки. Якщо x є батьківським для y, тоді y є нащадком x . На цьому зображенні 2 є батьківською з 5, потім 5 є дочірньою для кожного. Кожен вузол - кожна позиція зі значенням - може мати лише 1 батьківського та 2 дочірніх.

Але крім усього цього, не існує шаблону, якого слід дотримуватися, тому це дерево насправді не таке корисне ... Тож ми повинні додати ще кілька правил, щоб створити хорошу структуру даних.

Бінарні дерева пошуку

Ось тоді з’являються дерева бінарного пошуку! Замість того, щоб просто довільно розміщувати дочірні вузли, вони дотримуються певного порядку:

  • Якщо вузлів немає, то перше введене значення стає коренем дерева.
  • Якщо є вузли, тоді вставка робить такі кроки: починаючи з кореня, якщо значення, яке ви вводите, менше поточного вузла, пройдіть через ліву гілку, в іншому - через праву. Якщо ви перебуваєте на порожньому місці, то саме туди належить ваша цінність!

На початку це може здатися трохи заплутаним, але давайте напишемо якийсь псевдокод, щоб спростити його:

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) { if n is NULL: return createNode(v) else if n.value < v: n.right = insert(n.right, v) else: n.left = insert(n.left, v) return n}

Тепер, що тут відбувається? Спочатку перевіряємо, чи не пусте те місце, де ми зараз перебуваємо. Якщо це так, ми створюємо вузол у цьому місці з функцією createNode. Якщо він не порожній, тоді ми повинні побачити, куди слід розмістити наш вузол.

Ця демонстрація показує, як це працює:

Таким чином ми можемо шукати будь-яке значення в дереві, не проходячи всі вузли. Чудово!

Але це не завжди так добре, як у наведеному вище gif. Що, якщо ми отримаємо щось подібне?

У цьому випадку поведінка дерева змушує вас пройти всі вузли. Ось чому найгірша ефективність BST - O (n), що робить його повільним.

Видалити з BST також легко:

  • Якщо у вузла немає дочірніх елементів → видаліть вузол
  • Якщо у вузла є одна дочірня частина → підключіть батьківський вузол до його вузла онука та видаліть вузол
  • Якщо вузол має 2 дочірніх елементи → підставляйте вузол його найбільшому дочірньому (крайньому правому дочірньому дочірньому об'єкту) → див. Зображення нижче

Отже, ви знаєте все, що вам потрібно про BST. Досить круто, так?

Але що, якби ви ЗАВЖДИ хотіли мати ефективне дерево? Що б ти зробив?

Якщо у вас є така необхідність, дерева AVL можуть це зробити для вас досить добре. Натомість вони в мільйони разів складніші, ніж BST, але дотримуються тієї самої організації, що і раніше.

An AVL tree is a self-balancing tree that has specific operations (called rotations) that allow the tree to stay balanced . This means that each node in the tree will have a difference of height between its two child branches of maximum 1.

With this, the tree will always have a height of log(n) (n being the number of elements) and this allows you to search for elements in a really efficient way.

So now you see how good and perfect balanced trees are. But how to make them is the real question. I have mentioned the word depth before, so let’s first understand it.

Height is what allows us to understand if our tree is balanced or not. And with it we’re able to determine where the problem is and apply the balancing functions: rotations. These are really simple functions that consist of exchanging nodes between each other in order to remove the height difference, but they might look really strange at first.

There are 4 operations:

  • Rotation Left
  • Rotation Right
  • Rotation Left-Right
  • Rotation Right-Left

Wow that was strange… how do rotations work?

Rotations are strange at first, and I suggest checking out some animations of them working.

Try with your own trees on this website: //www.cs.usfca.edu/~galles/visualization/AVLtree.html

It allows you to dynamically see the rotations happening and is a great tool!

There are only four cases, so understanding them will be easy.

That’s all for now!

Trees are pretty easy to understand, and with practice you can work with them easily. Applying them in your code is a major key to make your programs a lot more efficient.

If you have any questions about something you didn’t understand, disagree with, or would like to suggest, feel free to contact me through Twitter or by email!

Email: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt