anastaskosstow/algorithms

data structures & algorithms

𝚁𝚎𝚜𝚘𝚞𝚛𝚌𝚎𝚜

ᴠɪꜱᴜᴀʟɢᴏ.ɴᴇᴛ	ᴄᴏᴏᴇʀᴠᴏ.ɢɪᴛʜᴜʙ.ɪᴏ	ᴀʟɢᴏʀɪᴛʜᴍꜱ.ᴅɪꜱᴄʀᴇᴛᴇ.ᴍᴀ.ᴛᴜᴍ.ᴅᴇ

---

𝙰𝚕𝚐𝚘𝚛𝚒𝚝𝚑𝚖𝚜 & 𝙳𝚊𝚝𝚊 𝚂𝚝𝚛𝚞𝚌𝚝𝚞𝚛𝚎𝚜

𝚃𝚑𝚒𝚜 𝚛𝚎𝚙𝚘𝚜𝚒𝚝𝚘𝚛𝚢 𝚌𝚘𝚗𝚝𝚊𝚒𝚗𝚜 𝚒𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜 𝚘𝚏 𝚖𝚊𝚗𝚢 𝚙𝚘𝚙𝚞𝚕𝚊𝚛 𝚊𝚕𝚐𝚘𝚛𝚒𝚝𝚑𝚖𝚜 𝚊𝚗𝚍 𝚍𝚊𝚝𝚊 𝚜𝚝𝚛𝚞𝚌𝚝𝚞𝚛𝚎𝚜．

• Sorting
  • Bubble sort
  • Selection sort
  • Insertions sort
  • Shell sort
  • Heap sort
  • Merge sort
  • Quicksort
• Primes
  • Trial Division
  • Sieve of Eratosthenes
  • Dijkstra`s primes
• Data Structures
  • Trees
    • Tree Theory
    • Binary Heap
    • Binary Search Tree
    • Red-Black Tree
    • AVL Tree
  • LinkedList
  • Disjoint-set
• Graph Theory
• Graph Implementation
• Graph Algorithms
  • Traversal
    • Depth-First Search
    • Breadth-First Search
  • Shortest path
    • Dijkstra
    • Bellman-Ford
    • Floyd-Warshall
  • Spanning tree
    • Kruskal
    • Prim
  • Connected components
    • Kosaraju
    • Tarjan

Important

Note that this project is meant to be used for learning and researching purposes only. Most optimal implementation for each algorithm or data structure depends on the use case.

𝙻𝚊𝚗𝚐𝚞𝚊𝚐𝚎𝚜 𝚞𝚜𝚎𝚍 𝚏𝚘𝚛 𝚒𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

For visual representation of the flow of each algorithm or data structure use 𝚅𝚒𝚜𝚞𝙰𝚕𝚐𝚘.𝚗𝚎𝚝 & ᴀʟɢᴏʀɪᴛʜᴍꜱ.ᴅɪꜱᴄʀᴇᴛᴇ.ᴍᴀ.ᴛᴜᴍ.ᴅᴇ

Sorting

Big O Notation

In a nutshell, we use Big O to describe the efficiency of algorithms.
It represents an upper bound on the time complexity of an algorithm, indicating how the runtime increases with the size of the input.
For example, O(N) suggests a linear increase in time with the size of the input, while O(1) indicates constant time regardless of input size

Key points:

There are three main mathematical notations used to describe the upper, tight, and lower bounds of algorithm complexity

• Bɪɢ O (O-ɴᴏᴛᴀᴛɪᴏɴ): It describes the upper bound of the time complexity of an algorithm. (worst-case)
• Bɪɢ Tʜᴇᴛᴀ (Θ-ɴᴏᴛᴀᴛɪᴏɴ): Big Theta provides a tight bound on the time complexity. (average-case)
• Bɪɢ Oᴍᴇɢᴀ (Ω-ɴᴏᴛᴀᴛɪᴏɴ): Big Omega describes the lower bound of the time complexity of an algorithm. (best-case)

Note

Fᴏʀ ᴍᴏʀᴇ ɪɴꜰᴏʀᴍᴀᴛɪᴏɴ ᴀʙᴏᴜᴛ 'Bɪɢ O ɴᴏᴛᴀᴛɪᴏɴ' - cooervo.github.io

Sorting Algorithms:

	wᴏʀꜱᴛ ᴄᴀꜱᴇ	aᴠᴇʀᴀɢᴇ ᴄᴀꜱᴇ	bᴇꜱᴛ ᴄᴀꜱᴇ	Iᴍᴘʟᴇᴍᴇɴᴛᴀᴛɪᴏɴꜱ
Bᴜʙʙʟᴇ ꜱᴏʀᴛ	O(n2)	Θ(n2)	Ω(n)	Rust - C#
Sᴇʟᴇᴄᴛɪᴏɴ ꜱᴏʀᴛ	O(n2)	Θ(n2)	Ω(n2)	Rust - C#
Iɴꜱᴇʀᴛɪᴏɴ ꜱᴏʀᴛ	O(n2)	Θ(n2)	Ω(n)	Rust - C#
Sʜᴇʟʟ ꜱᴏʀᴛ	O(n(3/2))	Θ(n2)	Ω(n log(n))	Rust - C#
Hᴇᴀᴘ ꜱᴏʀᴛ	O(n log(n))	Θ(n log(n))	Ω(n log(n))	Rust - C#
Mᴇʀɢᴇ ꜱᴏʀᴛ	O(n log(n))	Θ(n log(n))	Ω(n log(n))	Rust - C#
Qᴜɪᴄᴋꜱᴏʀᴛ	O(n log(n))	Θ(n log(n))	Ω(n log(n))	Rust - C#

Primes

What Are Prime Numbers?

𝖨𝗇 𝗍𝗁𝖾 𝗐𝗈𝗋𝗅𝖽 𝗈𝖿 𝗆𝖺𝗍𝗁𝖾𝗆𝖺𝗍𝗂𝖼𝗌, 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗁𝗈𝗅𝖽 𝖺 𝗌𝗉𝖾𝖼𝗂𝖺𝗅 𝗉𝗅𝖺𝖼𝖾. 𝖳𝗁𝖾𝗒 𝖺𝗋𝖾 𝗍𝗁𝖾 𝖻𝗎𝗂𝗅𝖽𝗂𝗇𝗀 𝖻𝗅𝗈𝖼𝗄𝗌 𝗈𝖿 𝗍𝗁𝖾 𝗇𝖺𝗍𝗎𝗋𝖺𝗅 𝗇𝗎𝗆𝖻𝖾𝗋𝗌, 𝗍𝗁𝖺𝗇𝗄𝗌 𝗍𝗈 𝖺 𝗄𝖾𝗒 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒: 𝖽𝗂𝗏𝗂𝗌𝗂𝖻𝗂𝗅𝗂𝗍𝗒.
𝖠 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗌 𝖽𝖾𝖿𝗂𝗇𝖾𝖽 𝖺𝗌 𝖺𝗇𝗒 𝗇𝖺𝗍𝗎𝗋𝖺𝗅 𝗇𝗎𝗆𝖻𝖾𝗋 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝟣 𝗍𝗁𝖺𝗍 𝗁𝖺𝗌 𝗇𝗈 𝗉𝗈𝗌𝗂𝗍𝗂𝗏𝖾 𝖽𝗂𝗏𝗂𝗌𝗈𝗋𝗌 𝗈𝗍𝗁𝖾𝗋 𝗍𝗁𝖺𝗇 𝟣 𝖺𝗇𝖽 𝗂𝗍𝗌𝖾𝗅𝖿. 𝖳𝗁𝗂𝗌 𝗆𝖾𝖺𝗇𝗌 𝗍𝗁𝖺𝗍 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝖼𝖺𝗇𝗇𝗈𝗍 𝖻𝖾 𝖽𝗂𝗏𝗂𝖽𝖾𝖽 𝖾𝗏𝖾𝗇𝗅𝗒 𝖻𝗒 𝖺𝗇𝗒 𝗈𝗍𝗁𝖾𝗋 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝖾𝗑𝖼𝖾𝗉𝗍 𝖿𝗈𝗋 𝟣 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗍𝗌𝖾𝗅𝖿 𝗐𝗂𝗍𝗁𝗈𝗎𝗍 𝗅𝖾𝖺𝗏𝗂𝗇𝗀 𝖺 𝗋𝖾𝗆𝖺𝗂𝗇𝖽𝖾𝗋.

𝖢𝗁𝖺𝗋𝖺𝖼𝗍𝖾𝗋𝗂𝗌𝗍𝗂𝖼𝗌 𝗈𝖿 𝖯𝗋𝗂𝗆𝖾 𝖭𝗎𝗆𝖻𝖾𝗋𝗌:

• 𝖴𝗇𝗂𝗊𝗎𝖾𝗇𝖾𝗌𝗌: 𝖤𝗏𝖾𝗋𝗒 𝗇𝗎𝗆𝖻𝖾𝗋 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝟣 𝗂𝗌 𝖾𝗂𝗍𝗁𝖾𝗋 𝗉𝗋𝗂𝗆𝖾 𝗈𝗋 𝖼𝖺𝗇 𝖻𝖾 𝖿𝖺𝖼𝗍𝗈𝗋𝖾𝖽 𝗂𝗇𝗍𝗈 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗉𝗋𝗂𝗆𝖾𝗌 𝗍𝗁𝖾 "𝖺𝗍𝗈𝗆𝗌" 𝗈𝖿 𝗍𝗁𝖾 𝗆𝖺𝗍𝗁𝖾𝗆𝖺𝗍𝗂𝖼𝖺𝗅 𝗐𝗈𝗋𝗅𝖽.
• 𝖨𝗇𝖽𝗂𝗏𝗂𝗌𝗂𝖻𝗂𝗅𝗂𝗍𝗒: 𝖳𝗁𝖾 𝖽𝖾𝖿𝗂𝗇𝗂𝗇𝗀 𝖼𝗁𝖺𝗋𝖺𝖼𝗍𝖾𝗋𝗂𝗌𝗍𝗂𝖼 𝗈𝖿 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗂𝗌 𝗍𝗁𝖾𝗂𝗋 𝗋𝖾𝗌𝗂𝗌𝗍𝖺𝗇𝖼𝖾 𝗍𝗈 𝖻𝖾𝗂𝗇𝗀 𝖽𝗂𝗏𝗂𝖽𝖾𝖽 𝖾𝗏𝖾𝗇𝗅𝗒 𝖻𝗒 𝖺𝗇𝗒 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝗍𝗁𝖾𝗋 𝗍𝗁𝖺𝗇 𝟣 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗍𝗌𝖾𝗅𝖿.
• 𝖳𝗁𝖾 𝖥𝗂𝗋𝗌𝗍 𝖯𝗋𝗂𝗆𝖾: 𝖳𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗌 𝟤, 𝗐𝗁𝗂𝖼𝗁 𝗂𝗌 𝖺𝗅𝗌𝗈 𝗍𝗁𝖾 𝗈𝗇𝗅𝗒 𝖾𝗏𝖾𝗇 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋. 𝖤𝗏𝖾𝗋𝗒 𝗈𝗍𝗁𝖾𝗋 𝖾𝗏𝖾𝗇 𝗇𝗎𝗆𝖻𝖾𝗋 𝖼𝖺𝗇 𝖻𝖾 𝖽𝗂𝗏𝗂𝖽𝖾𝖽 𝖻𝗒 𝟤, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗍𝗁𝖾𝗆 𝖼𝗈𝗆𝗉𝗈𝗌𝗂𝗍𝖾 𝗋𝖺𝗍𝗁𝖾𝗋 𝗍𝗁𝖺𝗇 𝗉𝗋𝗂𝗆𝖾.

---

Trial Division

𝖳𝗋𝗂𝖺𝗅 𝖽𝗂𝗏𝗂𝗌𝗂𝗈𝗇 𝗂𝗌 𝗈𝗇𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗂𝗆𝗉𝗅𝖾𝗌𝗍 𝖺𝗇𝖽 𝗆𝗈𝗌𝗍 𝗌𝗍𝗋𝖺𝗂𝗀𝗁𝗍𝖿𝗈𝗋𝗐𝖺𝗋𝖽 𝗆𝖾𝗍𝗁𝗈𝖽𝗌 𝖿𝗈𝗋 𝗍𝖾𝗌𝗍𝗂𝗇𝗀 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖺𝗅𝗂𝗍𝗒 𝗈𝖿 𝖺 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝗋 𝖿𝗈𝗋 𝖿𝗂𝗇𝖽𝗂𝗇𝗀 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾 𝖿𝖺𝖼𝗍𝗈𝗋𝗌 𝗈𝖿 𝖺 𝗇𝗎𝗆𝖻𝖾𝗋.
Here's how it works:

𝖶𝖾 𝗐𝗂𝗅𝗅 𝗍𝗋𝗒 𝗍𝗈 𝖿𝗂𝗇𝖽 𝖺𝗅𝗅 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗎𝗉 𝗍𝗈 an integer. <𝖻𝗋> 𝖳𝗁𝖾 𝗍𝗋𝗂𝖼𝗄 𝖿𝗈𝗋 𝗍𝗁𝗂𝗌 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝗂𝗌, 𝖿𝗈𝗋 𝖾𝖺𝖼𝗁 𝗇𝗎𝗆𝖻𝖾𝗋 𝗐𝖾 𝗐𝖺𝗇𝗇𝖺 𝖼𝗁𝖾𝖼𝗄 𝗂𝖿 𝗂𝗍'𝗌 𝖺 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝖺𝗇𝗒 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝖿𝗂𝗇𝖽 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌.

• 𝖥𝗂𝗋𝗌𝗍 𝗐𝖾 𝗇𝖾𝖾𝖽 𝖺𝗇 𝖾𝗆𝗉𝗍𝗒 𝗅𝗂𝗌𝗍 𝗐𝗁𝖾𝗋𝖾 𝗐𝖾 𝗄𝖾𝖾𝗉 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌.
• 𝖲𝗍𝖺𝗋𝗍𝗂𝗇𝗀 𝗐𝗂𝗍𝗁 𝟤 (𝟣 𝗂𝗌 𝗇𝗈𝗍 𝖼𝗈𝗇𝗌𝗂𝖽𝖾𝗋𝖾𝖽 𝗍𝗈 𝖻𝖾 𝖺 𝗉𝗋𝗂𝗆𝖾)
  • 𝖢𝗁𝖾𝖼𝗄 𝗂𝖿 𝟤 𝗂𝗌 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝖺𝗇𝗒 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝖿𝗈𝗎𝗇𝖽 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌. 𝖡𝖾𝖼𝖺𝗎𝗌𝖾 𝗐𝖾 𝗁𝖺𝗏𝖾𝗇𝗍 𝖿𝗂𝗇𝖽 𝖺𝗇𝗒 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗅𝗂𝗌𝗍 𝗂𝗌 𝖾𝗆𝗉𝗍𝗒, 𝗐𝖾 𝖺𝖽𝖽 𝟤 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾𝗌 𝗅𝗂𝗌𝗍
• 𝖭𝖾𝗑𝗍 𝗐𝖾 𝗆𝗈𝗏𝖾 𝗈𝗇 𝗍𝗈 𝟥
  • 𝖢𝗁𝖾𝖼𝗄 𝗂𝖿 𝟥 𝗂𝗌 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝖺𝗇𝗒 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝖿𝗈𝗎𝗇𝖽 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌. 𝖳𝗁𝖾 𝗈𝗇𝗅𝗒 𝗈𝗍𝗁𝖾𝗋 𝗉𝗋𝗂𝗆𝖾 𝗂𝗌 𝟤 𝖺𝗇𝖽 𝟥 𝗂𝗌 𝗇𝗈𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝟤 𝗌𝗈 𝗐𝖾 𝖺𝖽𝖽 𝟥 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾𝗌 𝗅𝗂𝗌𝗍
• 𝖭𝖾𝗑𝗍 𝗐𝖾 𝗆𝗈𝗏𝖾 𝗈𝗇 𝗍𝗈 𝟦
  • 𝖢𝗁𝖾𝖼𝗄 𝗂𝖿 𝟦 𝗂𝗌 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝖺𝗇𝗒 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝖿𝗈𝗎𝗇𝖽 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌. 𝖶𝖾 𝖿𝗈𝗎𝗇𝖽 𝗍𝗁𝖺𝗍 𝟤 𝗂𝗌 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝟦 𝗌𝗈 𝗐𝖾 𝗌𝗄𝗂𝗉 𝗍𝗁𝗂𝗌 𝗇𝗎𝗆𝖻𝖾𝗋
• 𝖳𝗁𝗂𝗌 𝗉𝗋𝗈𝖼𝖾𝗌𝗌 𝗂𝗌 𝗋𝖾𝗉𝖾𝖺𝗍𝖾𝖽 𝗎𝗇𝗍𝗂𝗅 𝗐𝖾 𝗋𝖾𝖺𝖼𝗁 𝗍𝗁𝖾 𝗌𝖾𝗍 𝗅𝗂𝗆𝗂𝗍. (𝗂𝗇 𝗈𝗐𝗋 𝖼𝖺𝗌𝖾: 𝟥𝟢)

About the 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍:

Important

𝖠𝖼𝗍𝗎𝖺𝗅𝗅𝗒 𝗐𝖾 𝖽𝗈𝗇'𝗍 𝗁𝖺𝗏𝖾 𝗍𝗈 𝖼𝗁𝖾𝖼𝗄 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗐𝗂𝗍𝗁 𝖾𝗏𝖾𝗋𝗒 𝗉𝗋𝗂𝗆𝖾 𝗍𝗁𝖺𝗍 𝗐𝖾 𝖿𝗈𝗎𝗇𝖽. 𝖮𝗇𝗅𝗒 𝗎𝗉 𝗍𝗈 𝗍𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗎𝗆𝖻𝖾𝗋
𝖶𝗁𝗒?
𝖫𝖾𝗍 𝖼𝗈𝗇𝗌𝗂𝖽𝖾𝗋 𝖿𝗈𝗋 𝖾𝗑𝖺𝗆𝗉𝗅𝖾 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝟤𝟦
𝖳𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝟤𝟦 𝗂𝗌 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝟦 𝖺𝗇𝖽 𝟧
𝖶𝗁𝖺𝗍 𝖺𝗋𝖾 𝗍𝗁𝖾 𝖿𝖺𝖼𝗍𝗈𝗋𝗌 𝗈𝖿 𝟤𝟦:

• 𝟣 - 𝟣𝗑𝟤𝟦
• 𝟤 - 𝟤𝗑𝟣𝟤
• 𝟥 - 𝟥𝗑𝟪
• 𝟦 - 𝟦𝗑𝟨
• 𝟨 - 𝟨𝗑𝟦
• 𝟪 - 𝟪𝗑𝟥
• 𝟣𝟤 - 𝟣𝟤𝗑𝟤
• 𝟤𝟦 - 𝟤𝟦𝗑𝟣

𝖨𝗍 𝗂𝗌 𝗇𝗈𝗍𝗂𝖼𝖾𝖺𝖻𝗅𝖾 𝗍𝗁𝖺𝗍 𝗐𝗁𝖾𝗇 𝗐𝖾 𝗋𝖾𝖺𝖼𝗁 𝗍𝗈 𝗍𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍 (𝟦), 𝖺𝖿𝗍𝖾𝗋 𝗍𝗁a𝗍 𝖺𝗅𝗅 𝖻𝖾𝖼𝗈𝗆𝖾 𝗆𝗂𝗋𝗋𝗈𝗋𝖾𝖽 𝖺𝗇𝖽 𝖺𝗅𝗅 𝗋𝖾𝗆𝖺𝗂𝗇𝗂𝗇𝗀 𝖿𝖺𝖼𝗍𝗈𝗋𝗌 𝖺𝗋𝖾 𝗍𝖾𝖼𝗁𝗇𝗂𝖼𝖺𝗅𝗅𝗒 𝖺𝗅𝗋𝖾𝖺𝖽𝗒 𝗂𝖽𝖾𝗇𝗍𝗂𝖿𝗂𝖾𝖽.

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Sieve of Eratosthenes

𝖳𝗁𝖾 𝖲𝗂𝖾𝗏𝖾 𝗈𝖿 𝖤𝗋𝖺𝗍𝗈𝗌𝗍𝗁𝖾𝗇𝖾𝗌 𝗂𝗌 𝖺𝗇 𝖺𝗇𝖼𝗂𝖾𝗇𝗍 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝗎𝗌𝖾𝖽 𝗍𝗈 𝖿𝗂𝗇𝖽 𝖺𝗅𝗅 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗎𝗉 𝗍𝗈 𝖺 𝗌𝗉𝖾𝖼𝗂𝖿𝗂𝖾𝖽 𝗂𝗇𝗍𝖾𝗀𝖾𝗋. 𝖨𝗍 𝗂𝗌 𝖺𝗇 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍 𝖺𝗇𝖽 𝗌𝗍𝗋𝖺𝗂𝗀𝗁𝗍𝖿𝗈𝗋𝗐𝖺𝗋𝖽 𝗆𝖾𝗍𝗁𝗈𝖽, 𝖾𝗌𝗉𝖾𝖼𝗂𝖺𝗅𝗅𝗒 𝗎𝗌𝖾𝖿𝗎𝗅 𝖿𝗈𝗋 𝖽𝖾𝖺𝗅𝗂𝗇𝗀 𝗐𝗂𝗍𝗁 𝗅𝖺𝗋𝗀𝖾 𝗊𝗎𝖺𝗇𝗍𝗂𝗍𝗂𝖾𝗌 𝗈𝖿 𝗇𝗎𝗆𝖻𝖾𝗋𝗌.
Here's how it works:

𝖶𝖾 𝗐𝗂𝗅𝗅 𝗍𝗋𝗒 𝗍𝗈 𝖿𝗂𝗇𝖽 𝖺𝗅𝗅 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗎𝗉 𝗍𝗈 𝖺𝗇 𝗂𝗇𝗍𝖾𝗀𝖾𝗋 𝖭.
𝖳𝗁𝖾 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝗐𝗈𝗋𝗄𝗌 𝖻𝗒 𝗂𝗍𝖾𝗋𝖺𝗍𝗂𝗏𝖾𝗅𝗒 𝗆𝖺𝗋𝗄𝗂𝗇𝗀 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗈𝖿 𝖾𝖺𝖼𝗁 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗌𝗍𝖺𝗋𝗍𝗂𝗇𝗀 𝖿𝗋𝗈𝗆 𝗍𝗁𝖾 𝖿𝗂𝗋𝗌𝗍 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋, 𝟤.

• 𝖳𝗈 𝗌𝗍𝖺𝗋𝗍, 𝗍𝗁𝗂𝗌 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝖼𝗋𝖾𝖺𝗍𝖾𝗌 𝖻𝗈𝗈𝗅𝖾𝖺𝗇 𝖺𝗋𝗋𝖺𝗒 𝗍𝗁𝖺𝗍 𝗂𝗌 𝗍𝗁𝖾 𝗌𝗂𝗓𝖾 𝗈𝖿 𝗆𝖺𝗑 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗁𝖺𝗍 𝗐𝖾 𝖺𝗋𝖾 𝖼𝗁𝖾𝖼𝗄𝗂𝗇𝗀. 𝖲𝗈 𝗂𝖿 𝗐𝖾 𝖼𝗁𝖾𝖼𝗄 𝖺𝗅𝗅 𝗉𝗋𝗂𝗆𝖾𝗌 𝗎𝗉 𝗍𝗈 𝟥𝟢, 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒 𝗁𝖺𝗌 𝗅𝖾𝗇𝗀𝗍𝗁 𝟥𝟢 𝖺𝗇𝖽 𝗂𝗇𝗂𝗍𝗂𝖺𝗅𝗅𝗒 𝖺𝗅𝗅 𝗏𝖺𝗅𝗎𝖾𝗌 𝖺𝗋𝖾 𝗍𝗋𝗎𝖾
• 𝖶𝖾 𝗌𝖾𝗍 𝟢 𝖺𝗇𝖽 𝟣 𝗍𝗈 𝖿𝖺𝗅𝗌𝖾 (𝗇𝗈𝗍 𝗉𝗋𝗂𝗆𝖾𝗌)
• 𝖭𝖾𝗑𝗍 𝗐𝖾 𝗌𝗍𝖺𝗋𝗍 𝗂𝗍𝖾𝗋𝖺𝗍𝗂𝗇𝗀 𝗈𝗏𝖾𝗋 𝖺𝗅𝗅 𝗂𝗇𝖽𝖾𝗑𝖾𝗌 𝗈𝖿 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒 𝗎𝗉 𝗍𝗈 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝖭, 𝗌𝗍𝖺𝗋𝗍𝗂𝗇𝗀 𝖿𝗋𝗈𝗆 𝟤
• 𝖨𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝖼𝖾𝗅𝗅 𝗂𝗌 𝗍𝗋𝗎𝖾, 𝗐𝖾 𝖿𝗈𝗎𝗇𝖽 𝖺 𝗉𝗋𝗂𝗆𝖾
  • 𝗐𝖾 𝗆𝖺𝗋𝗄 𝖺𝗅𝗅 𝗇𝗎𝗆𝖻𝖾𝗋𝗌(𝖼𝖾𝗅𝗅𝗌 𝖻𝗒 𝗂𝗇𝖽𝖾𝗑) 𝗍𝗁𝖺𝗍 𝖺𝗋𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗏𝖺𝗅𝗎𝖾 𝗍𝗈 𝖿𝖺𝗅𝗌𝖾
• 𝖳𝗁𝖾𝗇 𝗆𝗈𝗏𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗂𝗇𝖽𝖾𝗑

𝖥𝗈𝗋 𝖾𝗑𝖺𝗆𝗉𝗅𝖾:
𝖨𝖿 𝗐𝖾 𝗐𝖺𝗇𝗍 𝗍𝗈 𝖿𝗂𝗇𝖽 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌 𝗎𝗉 𝗍𝗈 𝟣𝟢:

• 𝖲𝗍𝖺𝗋𝗍 𝗐𝗂𝗍𝗁 𝟤. 𝖬𝖺𝗋𝗄 𝖺𝗅𝗅 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗈𝖿 𝟤 𝗍𝗈 𝖿𝖺𝗅𝗌𝖾 (𝟦, 𝟨, 𝟪, 𝟣𝟢), 𝗅𝖾𝖺𝗏𝗂𝗇𝗀 𝗂𝗇𝖽𝖾𝗑𝖾𝗌 𝟤, 𝟥, 𝟧, 𝟩, 𝟫 𝖺𝗌 𝗍𝗋𝗎𝖾.
• 𝖭𝖾𝗑𝗍 𝗂𝗇𝖽𝖾𝗑 𝗂𝗌 𝟥. 𝖳𝗁𝖾 𝖼𝖾𝗅𝗅 𝗏𝖺𝗅𝗎𝖾 𝗂𝗌 𝗍𝗋𝗎𝖾, 𝟥 𝗂𝗌 𝖺 𝗉𝗋𝗂𝗆𝖾. 𝖬𝖺𝗋𝗄 𝖺𝗅𝗅 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗈𝖿 𝟥 (𝟫), 𝗅𝖾𝖺𝗏𝗂𝗇𝗀 𝟤, 𝟥, 𝟧, 𝟩 𝖺𝗌 𝗍𝗋𝗎𝖾.
• 𝖭𝖾𝗑𝗍 𝗂𝗇𝖽𝖾𝗑 𝗂𝗌 𝟦. 𝖳𝗁𝖾 𝖼𝖾𝗅𝗅 𝗏𝖺𝗅𝗎𝖾 𝗈𝖿 𝟦 𝗂𝗌 𝖿𝖺𝗅𝗌𝖾. 𝖬𝗈𝗏𝖾 𝗈𝗇.
• 𝖭𝖾𝗑𝗍 𝗂𝗇𝖽𝖾𝗑 𝗂𝗌 𝟧, 𝗐𝗁𝗂𝖼𝗁 𝗂𝗌 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝗌𝗊𝗋𝗍_𝟣𝟢. 𝖳𝗁𝖾 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝗌𝗍𝗈𝗉𝗌.
• 𝖳𝗁𝖾 𝗉𝗋𝗂𝗆𝖾𝗌 𝗎𝗉 𝗍𝗈 𝟣𝟢 𝖺𝗋𝖾: 𝟤, 𝟥, 𝟧, 𝟩.

Important

𝖶𝗁𝗒 𝗐𝖾 𝖼𝗁𝖾𝖼𝗄 𝗈𝗇𝗅𝗒 𝗍𝗈 𝗌𝗊𝗎𝖺𝗋𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗎𝗆𝖻𝖾𝗋?
Learn here!

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Dijkstra Primes

𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺'𝗌 𝖯𝗋𝗂𝗆𝖾𝗌 𝗂𝗌 𝗈𝗇𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗆𝗈𝗌𝗍 𝗎𝗇𝗄𝗇𝗈𝗐𝗇 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆𝗌. 𝖡𝗎𝗂𝗅𝖽𝗂𝗇𝗀 𝗈𝖿 𝗍𝗁𝖾 𝖿𝗈𝗎𝗇𝖽𝖺𝗍𝗂𝗈𝗇 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖺𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅 𝗉𝗋𝗂𝗆𝖾 𝖿𝗂𝗇𝖽𝗂𝗇𝗀 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆𝗌, 𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺 𝖽𝖾𝖼𝗂𝖽𝖾𝖽 𝗍𝗈 𝗏𝖾𝗇𝗍𝗎𝗋𝖾 𝖻𝖾𝗒𝗈𝗇𝖽 𝗍𝗁𝖾𝗌𝖾 𝖼𝗈𝗇𝗏𝖾𝗇𝗍𝗂𝗈𝗇𝖺𝗅 𝗉𝖺𝗍𝗁𝗌. Here's how it works:

𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺'𝗌 𝖺𝗉𝗉𝗋𝗈𝖺𝖼𝗁 𝗂𝗇𝖼𝗅𝗎𝖽𝖾 𝗍𝗐𝗈 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾𝗌. 𝖠 𝗉𝗈𝗈𝗅 𝖺𝗇𝖽 𝖺 𝗅𝗂𝗌𝗍 𝗈𝖿 𝗉𝗋𝗂𝗆𝖾𝗌.

• 𝖶𝖾 𝗌𝗄𝗂𝗉 𝟣 𝖺𝗇𝖽 𝗀𝗈 𝗍𝗈 𝟤. 𝖶𝖾 𝖺𝗌𝗌𝗎𝗆𝖾 𝗍𝗁𝖺𝗍 𝟤 𝗂𝗌 𝗉𝗋𝗂𝗆𝖾 𝖺𝗇𝖽 𝖺𝖽𝖽 𝗂𝗍 𝗍𝗈 𝗍𝗁𝖾 𝗅𝗂𝗌𝗍 𝗈𝖿 𝗉𝗋𝗂𝗆𝖾𝗌.
  𝖭𝗈𝗐, 𝗈𝗇𝖼𝖾 𝗐𝖾 𝖺𝖽𝖽𝖾𝖽 𝖺 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗈 𝗍𝗁𝖾 𝗅𝗂𝗌𝗍 𝗐𝖾 𝖺𝗅𝗌𝗈 𝗐𝖾𝖾𝖽 𝗍𝗈 𝖺𝖽𝖽 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅 𝖺𝗅𝗈𝗇𝗀 𝗐𝗂𝗍𝗁 𝗍𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝖺𝗌 𝖺 𝗍𝗎𝗉𝗅𝖾.

  

  𝖨𝗇 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅, 𝗍𝗁𝖾 𝖿𝗂𝗋𝗌𝗍 𝗋𝗈𝗐 𝗂𝗌 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗌𝖾𝖼𝗈𝗇𝖽 𝗋𝗈𝗐 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝖺𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖽 𝗐𝗂𝗍𝗁 𝗍𝗁𝖺𝗍 𝗉𝗋𝗂𝗆𝖾.
  𝖲𝗈 𝗂𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾, 𝗂𝗇 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅 𝗐𝖾 𝗁𝖺𝗏𝖾 2 𝖺𝗇𝖽 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾: 𝟦.

• 𝖭𝖾𝗑𝗍 𝗐𝖾 𝗀𝗈 𝗍𝗈 𝟥 𝖺𝗇𝖽 𝗐𝗁𝖺𝗍 𝗐𝖾 𝗐𝖺𝗇𝗍 𝗍𝗈 𝖿𝗂𝗇𝖽 𝗂𝗌 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅. 𝖨𝗇 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗉𝗈𝗈𝗅 𝗍𝗁𝗂𝗌 𝗂𝗌 𝟦.
  𝖨𝖿 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗁𝖺𝗍 𝗐𝖾 𝖺𝗋𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝗈𝗇 𝗂𝗌 𝗌𝗆𝖺𝗅𝗅𝖾𝗋 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗉𝗈𝗈𝗅 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 (𝗂𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾 𝗂𝗍 𝗂𝗌 -> 𝟥 < 𝟦), 𝗍𝗁𝖾𝗇 𝗐𝖾 𝖺𝖽𝖽 𝗍𝗁𝗂𝗌 𝗇𝗎𝗆𝖻𝖾𝗋 𝖺𝗌 𝖺 𝗉𝗋𝗂𝗆𝖾 𝖺𝗇𝖽 𝖺𝗀𝖺𝗂𝗇 𝖺𝖽𝖽 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅 𝖺𝗅𝗈𝗇𝗀 𝗐𝗂𝗍𝗁 𝗍𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝖺𝗌 𝖺 𝗍𝗎𝗉𝗅𝖾.

  

  𝖭𝖾𝗑𝗍 𝗐𝖾 𝗀𝗈 𝗍𝗈 𝟦. 𝖠𝗀𝖺𝗂𝗇 𝗐𝖾 𝖿𝗂𝗇𝖽 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅 𝗐𝗁𝗂𝖼𝗁 𝗂𝗌 𝟦 and 𝗐𝖾 𝖼𝗁𝖾𝖼𝗄 𝗂𝖿 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗍𝗁𝖺𝗍 𝗐𝖾 𝖺𝗋𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍𝗅𝗒 𝗈𝗇 𝗂𝗌 𝗅𝖾𝗌𝗌 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾.
  𝖨𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾 𝗍𝗁𝖾𝗒 𝖺𝗋𝖾 𝖾𝗊𝗎𝖺𝗅 (𝟦 == 𝟦) 𝗐𝗁𝗂𝖼𝗁 𝗆𝖾𝖺𝗇𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗌 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝖺 𝗉𝗋𝗂𝗆𝖾.
  𝖲𝗈 𝗂𝗇𝗌𝗍𝖾𝖺𝖽 𝗐𝖾 𝗇𝖾𝖾𝖽 𝗍𝗈 𝗂𝗇𝖼𝗋𝖾𝗆𝖾𝗇𝗍 𝗈𝗎𝗋 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝖻𝗒 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗂𝗌 𝖺𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖽 𝗐𝗂𝗍𝗁 - 𝟤/𝟦 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝟤/𝟨.

  

• 𝖭𝖾𝗑𝗍 𝗐𝖾 𝗀𝗈 𝗍𝗈 𝟧 𝖺𝗇𝖽 𝖺𝗀𝖺𝗂𝗇 𝖿𝗂𝗇𝖽 𝗂𝗌 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗉𝗈𝗈𝗅. 𝖨𝗇 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗉𝗈𝗈𝗅 𝗍𝗁𝗂𝗌 𝗂𝗌 𝟨.
  𝟧 𝗂𝗌 𝗅𝖾𝗌𝗌 𝗍𝗁𝖺𝗇 𝟨 𝗌𝗈 𝗐𝖾 𝖺𝖽𝖽𝖾𝖽 𝗂𝗍 𝖺𝗌 𝖺 𝗉𝗋𝗂𝗆𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗋𝗂𝗆𝖾𝗌 𝗅𝗂𝗌𝗍 𝖺𝗅𝗈𝗇𝗀 𝗐𝗂𝗍𝗁 𝗍𝗁𝖾 𝗌𝗊𝗎𝖺𝗋𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝖺𝗌 𝖺 𝗍𝗎𝗉𝗅𝖾 (𝟧/𝟤𝟧).

  

• 𝖠𝗇 𝗂𝗇𝗍𝖾𝗋𝖾𝗌𝗍𝗂𝗇𝗀 𝖼𝖺𝗌𝖾 𝗈𝖼𝖼𝗎𝗋𝗌 𝗐𝗁𝖾𝗇 𝗐𝖾 𝗀𝖾𝗍 𝗍𝗈 𝟣𝟤.
  𝖥𝗈𝗅𝗅𝗈𝗐𝗂𝗇𝗀 𝗍𝗁𝗂𝗌 𝗉𝖺𝗍𝗍𝖾𝗋𝗇, 𝖾𝗏𝖾𝗋𝗒 𝗍𝗂𝗆𝖾 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗈𝖿 𝟤 𝖺𝗇𝖽 𝟥 𝖺𝗋𝖾 𝗂𝗇𝖼𝗋𝖾𝗆𝖾𝗇𝗍𝖾𝖽, 𝖺𝖿𝗍𝖾𝗋 𝟣𝟣, 𝖻𝗈𝗍𝗁 𝟤 𝖺𝗇𝖽 𝟥 𝖺𝗋𝖾 𝗐𝗂𝗍𝗁 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝟣𝟤:

  

  𝖨𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾, we 𝗂𝗇𝖼𝗋𝖾𝗆𝖾𝗇𝗍 𝗈𝗎𝗋 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾 𝖻𝗒 𝗍𝗁𝖾 both 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋s (𝟤/12 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝟤/14 and 3/12 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 3/15)

  

• 𝖳𝗁𝗂𝗌 𝗉𝖺𝗍𝗍𝖾𝗋𝗇 𝗐𝗂𝗅𝗅 𝗃𝗎𝗌𝗍 𝖼𝗈𝗇𝗍𝗂𝗇𝗎𝖾 𝗈𝗇𝗐𝖺𝗋𝖽.

Comparing the Dijkstra's Primes algorithm to Trial Division and Sieve of Eratosthenes

𝖶𝗁𝗂𝗅𝖾 𝖳𝗋𝗂𝖺𝗅 𝖣𝗂𝗏𝗂𝗌𝗂𝗈𝗇 𝗂𝗌 𝗏𝖾𝗋𝗒 𝗌𝗉𝖺𝖼𝖾 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍, 𝗂𝗍'𝗌 𝗇𝗈𝗍 𝗏𝖾𝗋𝗒 𝗍𝗂𝗆𝖾 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍. 𝖠𝖼𝗍𝗎𝖺𝗅𝗅𝗒 𝗂𝗍'𝗌 𝗍𝗁𝖾 𝗌𝗅𝗈𝗐𝖾𝗌𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗁𝗋𝖾𝖾.
𝖲𝗂𝖾𝗏𝖾 𝗈𝖿 𝖤𝗋𝖺𝗍𝗈𝗌𝗍𝗁𝖾𝗇𝖾𝗌 𝗂𝗌 𝗍𝗁𝖾 𝗈𝗉𝗉𝗈𝗌𝗂𝗍𝖾. 𝖨𝗍'𝗌 𝗏𝖾𝗋𝗒 𝗍𝗂𝗆𝖾 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍, 𝖻𝗎𝗍 𝗏𝖾𝗋𝗒 𝗌𝗉𝖺𝖼𝖾 𝗂𝗇𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍.
𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺'𝗌 𝖯𝗋𝗂𝗆𝖾𝗌 𝗂𝗌 𝗌𝗈𝗆𝖾𝗐𝗁𝖾𝗋𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗆𝗂𝖽𝖽𝗅𝖾 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾 𝗍𝗐𝗈.
𝖨𝗇 𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆 𝗐𝖾 𝗃𝗎𝗌𝗍 𝗎𝗌𝗂𝗇𝗀 𝖺 𝗌𝗂𝗆𝗉𝗅𝖾 𝖺𝖽𝖽𝗂𝗍𝗂𝗈𝗇 𝗍𝗈 𝗄𝖾𝖾𝗉 𝗍𝗋𝖺𝖼𝗄 𝗈𝖿 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗈𝖿 𝗉𝗋𝗂𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋𝗌, 𝗇𝗈𝗍 𝖽𝗂𝗏𝗂𝗌𝗂𝗈𝗇 𝗅𝗂𝗄𝖾 𝗐𝖾 𝖽𝗂𝖽 𝗂𝗇 𝖳𝗋𝗂𝖺𝗅 𝖣𝗂𝗏𝗂𝗌𝗂𝗈𝗇.
𝖠𝗅𝗌𝗈 𝗐𝖾 𝗎𝗌𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗋 𝖽𝖺𝗍𝖺 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗍𝗈 𝗄𝖾𝖾𝗉 𝗍𝗋𝖺𝖼𝗄 𝗈𝖿 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝖼𝗈𝗆𝗉𝖺𝗋𝖾 𝗐𝗁𝖺𝗍 𝗐𝖾 𝗎𝗌𝖾𝖽 𝗂𝗇 𝗍𝗁𝖾 𝖲𝗂𝖾𝗏𝖾 𝗈𝖿 𝖤𝗋𝖺𝗍𝗈𝗌𝗍𝗁𝖾𝗇𝖾𝗌. 𝖨𝗇𝗌𝗍𝖾𝖺𝖽 𝗈𝖿 𝗄𝖾𝖾𝗉𝗂𝗇𝗀 𝗍𝗋𝖺𝖼𝗄 𝗈𝖿 𝖺𝗅𝗅 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝖺𝗍 𝗈𝗇𝖼𝖾, 𝖣𝗂𝗃𝗄𝗌𝗍𝗋𝖺'𝗌 𝗆𝖾𝗍𝗁𝗈𝖽 𝗈𝗇𝗅𝗒 𝗄𝖾𝖾𝗉𝗌 𝗍𝗋𝖺𝖼𝗄 𝗈𝖿 𝗍𝗁𝖾 𝗆𝗎𝗅𝗍𝗂𝗉𝗅𝖾𝗌 𝗂𝗍 𝗇𝖾𝖾𝖽𝗌.

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Data Structures

Tree Theory

𝖠 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝖽𝖺𝗍𝖺 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝖼𝗈𝗆𝗉𝗈𝗌𝖾𝖽 𝗈𝖿 𝗇𝗈𝖽𝖾𝗌.

• 𝖤𝖺𝖼𝗁 𝗍𝗋𝖾𝖾 𝗁𝖺𝗌 𝖺 𝗋𝗈𝗈𝗍 𝗇𝗈𝖽𝖾.
• 𝖳𝗁𝖾 𝗋𝗈𝗈𝗍 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝗓𝖾𝗋𝗈 𝗈𝗋 𝗆𝗈𝗋𝖾 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾𝗌.
• 𝖤𝖺𝖼𝗁 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝗓𝖾𝗋𝗈 𝗈𝗋 𝗆𝗈𝗋𝖾 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾𝗌, 𝖺𝗇𝖽 𝗌𝗈 𝗈𝗇.

𝖳𝗁𝖾 𝗍𝗋𝖾𝖾 𝖼𝖺𝗇𝗇𝗈𝗍 𝖼𝗈𝗇𝗍𝖺𝗂𝗇 𝖼𝗒𝖼𝗅𝖾𝗌. 𝖳𝗁𝖾 𝗇𝗈𝖽𝖾𝗌 𝗆𝖺𝗒 𝗈𝗋 𝗆𝖺𝗒 𝗇𝗈𝗍 𝖻𝖾 𝗂𝗇 𝖺 𝗉𝖺𝗋𝗍𝗂𝖼𝗎𝗅𝖺𝗋 𝗈𝗋𝖽𝖾𝗋 𝖺𝗇𝖽 𝗍𝗁𝖾𝗒 𝖼𝗈𝗎𝗅𝖽 𝗁𝖺𝗏𝖾 𝖺𝗇𝗒 𝖽𝖺𝗍𝖺 𝗍𝗒𝗉𝖾 𝖺𝗌 𝗏𝖺𝗅𝗎𝖾𝗌.

Binary Tree vs. Binary Search Tree

𝖠 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗂𝗇 𝗐𝗁𝗂𝖼𝗁 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾 𝖿𝗂𝗍𝗌 𝖺 𝗌𝗉𝖾𝖼𝗂𝖿𝗂𝖼 𝗈𝗋𝖽𝖾𝗋𝗂𝗇𝗀 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒. 𝖳𝗁𝗂𝗌 𝗆𝗎𝗌𝗍 𝖻𝖾 𝗍𝗋𝗎𝖾 𝖿𝗈𝗋 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗇.

𝖡𝗂𝗇𝖺𝗋𝗒 𝖲𝖾𝖺𝗋𝖼𝗁 𝖯𝗋𝗈𝗉𝖾𝗋𝗍𝗒:

• 𝖥𝗈𝗋 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾, 𝖺𝗅𝗅 𝖾𝗅𝖾𝗆𝖾𝗇𝗍𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖺𝗋𝖾 𝗅𝖾𝗌𝗌 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾'𝗌 𝗏𝖺𝗅𝗎𝖾, 𝖺𝗇𝖽 𝖺𝗅𝗅 𝖾𝗅𝖾𝗆𝖾𝗇𝗍𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖺𝗋𝖾 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾'𝗌 𝗏𝖺𝗅𝗎𝖾.

𝖳𝗁𝗂𝗌 𝗂𝗇𝖾𝗊𝗎𝖺𝗅𝗂𝗍𝗒 𝗆𝗎𝗌𝗍 𝖻𝖾 𝗍𝗋𝗎𝖾 𝖿𝗈𝗋 𝖺𝗅𝗅 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾'𝗌 𝖽𝖾𝗌𝖼𝖾𝗇𝖽𝖾𝗇𝗍𝗌, 𝗇𝗈𝗍 𝗃𝗎𝗌𝗍 𝗂𝗍𝗌 𝗂𝗆𝗆𝖾𝖽𝗂𝖺𝗍𝖾 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇. 𝖳𝗁𝖾 𝖿𝗈𝗅𝗅𝗈𝗐𝗂𝗇𝗀 𝗍𝗋𝖾𝖾 𝗈𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖻𝖾𝗅𝗈𝗐 𝗂𝗌 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾. 𝖳𝗁𝖾 𝗍𝗋𝖾𝖾 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗂𝗌 𝗇𝗈𝗍, 𝗌𝗂𝗇𝖼𝖾 𝟣𝟤 𝗂𝗌 𝗍𝗈 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗈𝖿 𝟪.

𝖡𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾	𝖭𝗈𝗍 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾

Balanced vs. Unbalanced

𝖮𝗇𝖾 𝗐𝖺𝗒 𝗍𝗈 𝗍𝗁𝗂𝗇𝗄 𝖺𝖻𝗈𝗎𝗍 𝗂𝗍 𝗂𝗌 𝗍𝗁𝖺𝗍 𝖺 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾 𝗋𝖾𝖺𝗅𝗅𝗒 𝗆𝖾𝖺𝗇𝗌 𝗌𝗈𝗆𝖾𝗍𝗁𝗂𝗇𝗀 𝗆𝗈𝗋𝖾 𝗅𝗂𝗄𝖾 "𝗇𝗈𝗍 𝗍𝖾𝗋𝗋𝗂𝖻𝗅𝗒 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽". 𝖨𝗍'𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖾𝗇𝗈𝗎𝗀𝗁 𝗍𝗈 𝖾𝗇𝗌𝗎𝗋𝖾 Θ(<i>n</i> log(<i>n</i>)) 𝖿𝗈𝗋 𝗂𝗇𝗌𝖾𝗋𝗍 𝖺𝗇𝖽 𝖿𝗂𝗇𝖽, 𝖻𝗎𝗍 𝗂𝗍'𝗌 𝗇𝗈𝗍 𝗇𝖾𝖼𝖾𝗌𝗌𝖺𝗋𝗂𝗅𝗒 𝖺𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖺𝗌 𝗂𝗍 𝖼𝗈𝗎𝗅𝖽 𝖻𝖾.

𝖳𝗐𝗈 𝖼𝗈𝗆𝗆𝗈𝗇 𝗍𝗒𝗉𝖾𝗌 𝗈𝖿 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾𝗌 𝖺𝗋𝖾 𝖱𝖾𝖽-𝖻𝗅𝖺𝖼𝗄 𝗍𝗋𝖾𝖾 𝖺𝗇𝖽 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾.

𝖳𝗁𝖾 𝗀𝗈𝖺𝗅 𝗂𝗌 𝗍𝗈 𝗄𝖾𝖾𝗉 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝖺𝗌 𝖿𝗅𝖺𝗍 𝖺𝗌 𝗉𝗈𝗌𝗌𝗂𝖻𝗅𝖾 𝖻𝗒 𝖾𝗏𝖾𝗇𝗅𝗒 𝖽𝗂𝗌𝗍𝗋𝗂𝖻𝗎𝗍𝗂𝗇𝗀 𝗇𝗈𝖽𝖾𝗌 𝗈𝗇 𝖻𝗈𝗍𝗁 𝗌𝗂𝖽𝖾𝗌, 𝗉𝗋𝖾𝗏𝖾𝗇𝗍𝗂𝗇𝗀 𝗉𝖾𝗋𝖿𝗈𝗋𝗆𝖺𝗇𝖼𝖾 𝖽𝖾𝗀𝗋𝖺𝖽𝖺𝗍𝗂𝗈𝗇

• 𝖱𝖾𝖽-𝖻𝗅𝖺𝖼𝗄 𝗍𝗋𝖾𝖾𝗌 𝖺𝗋𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾𝗌 𝗍𝗁𝖺𝗍 𝗎𝗌𝖾𝗌 𝖼𝗈𝗅𝗈𝗋𝗌 (𝗋𝖾𝖽 𝖺𝗇𝖽 𝖻𝗅𝖺𝖼𝗄) 𝗍𝗈 𝗁𝖾𝗅𝗉 𝗄𝖾𝖾𝗉 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽.
  • 𝖤𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗂𝗌 𝖾𝗂𝗍𝗁𝖾𝗋 𝗋𝖾𝖽 𝗈𝗋 𝖻𝗅𝖺𝖼𝗄.
  • 𝖳𝗁𝖾 𝗋𝗈𝗈𝗍 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝖻𝗅𝖺𝖼𝗄.
  • 𝖱𝖾𝖽 𝗇𝗈𝖽𝖾𝗌 𝖼𝖺𝗇𝗇𝗈𝗍 𝗁𝖺𝗏𝖾 𝗋𝖾𝖽 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇.
  • 𝖤𝗏𝖾𝗋𝗒 𝗉𝖺𝗍𝗁 𝖿𝗋𝗈𝗆 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗂𝗍𝗌 𝗇𝗎𝗅𝗅 𝖽𝖾𝗌𝖼𝖾𝗇𝖽𝖺𝗇𝗍𝗌 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗌 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝖿 𝖻𝗅𝖺𝖼𝗄 𝗇𝗈𝖽𝖾𝗌.
• 𝖠𝖵𝖫 𝖳𝗋𝖾𝖾𝗌 𝖺𝗋𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾𝗌 𝗍𝗁𝖺𝗍 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖻𝗒 𝗌𝗍𝗈𝗋𝗂𝗇𝗀 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖺𝗍 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝖺𝗇𝖽 𝖾𝗇𝗌𝗎𝗋𝗂𝗇𝗀 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾 (𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋) 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝗂𝗌 𝗇𝗈 𝗆𝗈𝗋𝖾 𝗍𝗁𝖺𝗇 𝗈𝗇𝖾. <𝖻𝗋> 𝖨𝖿 𝗍𝗁𝗂𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗂𝗌 𝗏𝗂𝗈𝗅𝖺𝗍𝖾𝖽 𝖺𝖿𝗍𝖾𝗋 𝖺𝗇 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝗈𝗋 𝖽𝖾𝗅𝖾𝗍𝗂𝗈𝗇, 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝗉𝖾𝗋𝖿𝗈𝗋𝗆𝖾𝖽 𝗍𝗈 𝗋𝖾𝗌𝗍𝗈𝗋𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾.
  • 𝖡𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗂𝗌 𝗍𝗁𝖾 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾 𝗂𝗇 𝗁𝖾𝗂𝗀𝗁𝗍 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝗌𝗂𝖽𝖾𝗌 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾.
    • 𝖨𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗂𝖽𝖾 𝗂𝗌 𝗍𝖺𝗅𝗅𝖾𝗋, 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗂𝗌 +𝟣
    • 𝖨𝖿 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗂𝖽𝖾 𝗂𝗌 𝗍𝖺𝗅𝗅𝖾𝗋, 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗂𝗌 -𝟣
    • 𝖨𝖿 𝖻𝗈𝗍𝗁 𝗌𝗂𝖽𝖾𝗌 𝖺𝗋𝖾 𝖾𝗊𝗎𝖺𝗅, 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗂𝗌 𝟢

Complete Binary Trees

𝖠 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗂𝗇 𝗐𝗁𝗂𝖼𝗁 𝖾𝗏𝖾𝗋𝗒 𝗅𝖾𝗏𝖾𝗅 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖿𝗎𝗅𝗅𝗒 𝖿𝗂𝗅𝗅𝖾𝖽, 𝖾𝗑𝖼𝖾𝗉𝗍 𝖿𝗈𝗋 𝗉𝖾𝗋𝗁𝖺𝗉𝗌 𝗍𝗁𝖾 𝗅𝖺𝗌𝗍 𝗅𝖾𝗏𝖾𝗅. <𝖻𝗋> 𝖳𝗈 𝗍𝗁𝖾 𝖾𝗑𝗍𝖾𝗇𝗍 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗅𝖺𝗌𝗍 𝗅𝖾𝗏𝖾𝗅 𝗂𝗌 𝖿𝗂𝗅𝗅𝖾𝖽, 𝗂𝗍 𝗂𝗌 𝖿𝗂𝗅𝗅𝖾𝖽 𝗅𝖾𝖿𝗍 𝗍𝗈 𝗋𝗂𝗀𝗁𝗍.

𝖢𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾	𝖭𝗈𝗍 𝖺 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾

Full Binary Trees

𝖠 𝖿𝗎𝗅𝗅 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗂𝗇 𝗐𝗁𝗂𝖼𝗁 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝖾𝗂𝗍𝗁𝖾𝗋 𝗓𝖾𝗋𝗈 𝗈𝗋 𝗍𝗐𝗈 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇. 𝖳𝗁𝖺𝗍 𝗂𝗌, 𝗇𝗈 𝗇𝗈𝖽𝖾𝗌 𝗁𝖺𝗏𝖾 𝗈𝗇𝗅𝗒 𝗈𝗇𝖾 𝖼𝗁𝗂𝗅𝖽.

𝖥𝗎𝗅𝗅 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾	𝖭𝗈𝗍 𝖺 𝖿𝗎𝗅𝗅 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾

Binary Tree Traversal

𝖳𝗁𝖾𝗋𝖾 𝖺𝗋𝖾 𝗍𝗁𝗋𝖾𝖾 𝗆𝖺𝗂𝗇 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅 𝗆𝖾𝗍𝗁𝗈𝖽𝗌:

• 𝖨𝗇-𝗈𝗋𝖽𝖾𝗋
• 𝖯𝗋𝖾-𝗈𝗋𝖽𝖾𝗋
• 𝖯𝗈𝗌𝗍-𝗈𝗋𝖽𝖾𝗋

𝖨𝗇-𝖮𝗋𝖽𝖾𝗋: 𝖨𝗇-𝗈𝗋𝖽𝖾𝗋 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅 𝗆𝖾𝖺𝗇𝗌 𝗍𝗈 "𝗏𝗂𝗌𝗂𝗍" (𝗈𝖿𝗍𝖾𝗇, 𝗉𝗋𝗂𝗇𝗍) 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖻𝗋𝖺𝗇𝖼𝗁, 𝗍𝗁𝖾𝗇 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾, 𝖺𝗇𝖽 𝖿𝗂𝗇𝖺𝗅𝗅𝗒, 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖻𝗋𝖺𝗇𝖼𝗁.

fn in_order_traversal(node: TreeNode) {
    if let Some(value) = node.value {
        in_order_traversal(node.left);
        print(value);
        in_order_traversal(node.right);
    }
}

𝖯𝗋𝖾-𝖮𝗋𝖽𝖾𝗋: 𝖯𝗋𝖾-𝗈𝗋𝖽𝖾𝗋 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅 𝗏𝗂𝗌𝗂𝗍𝗌 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝖻𝖾𝖿𝗈𝗋𝖾 𝗂𝗍𝗌 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾𝗌.

fn pre_order_traversal(node: TreeNode) {
    if let Some(value) = node.value {
        print(value);
        pre_order_traversal(node.left);
        pre_order_traversal(node.right);
    }
}

𝖯𝗈𝗌𝗍-𝖮𝗋𝖽𝖾𝗋: 𝖯𝗈𝗌𝗍-𝗈𝗋𝖽𝖾𝗋 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅 𝗏𝗂𝗌𝗂𝗍𝗌 𝗍𝗁𝖾 𝖼𝗎𝗋𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝖺𝖿𝗍𝖾𝗋 𝗂𝗍𝗌 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾𝗌.

fn post_order_traversal(node: TreeNode) {
    if let Some(value) = node.value {
        post_order_traversal(node.left);
        post_order_traversal(node.right);
        print(value);
    }
}

𝖲𝗈 𝖿𝗈𝗋 𝗍𝗁𝖾 𝖿𝗈𝗅𝗅𝗈𝗐𝗂𝗇𝗀 𝗍𝗋𝖾𝖾:

𝖳𝗁𝖾 𝗋𝖾𝗌𝗎𝗅𝗍 𝗐𝗂𝗅𝗅 be:

• 𝖨𝗇-𝗈𝗋𝖽𝖾𝗋 - [𝟣, 𝟧, 𝟩, 𝟣𝟢, 𝟤𝟢]
• 𝖯𝗋𝖾-𝗈𝗋𝖽𝖾𝗋 - [𝟣𝟢, 𝟧, 𝟣, 𝟩, 𝟤𝟢]
• 𝖯𝗈𝗌𝗍-𝗈𝗋𝖽𝖾𝗋 - [𝟣, 𝟩, 𝟧, 𝟤𝟢, 𝟣𝟢]

Balanced vs. Unbalanced Trees

• Balanced Trees
  𝖠 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝗍𝗒𝗉𝖾 𝗈𝖿 𝖻𝗂𝗇𝖺𝗋𝗒 𝗍𝗋𝖾𝖾 𝗐𝗁𝖾𝗋𝖾 𝗍𝗁𝖾 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾 𝗂𝗇 𝗁𝖾𝗂𝗀𝗁𝗍 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝗈𝖿 𝖺𝗇𝗒 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗆𝗂𝗇𝗂𝗆𝖺𝗅 — 𝗎𝗌𝗎𝖺𝗅𝗅𝗒 𝗇𝗈 𝗆𝗈𝗋𝖾 𝗍𝗁𝖺𝗇 𝗈𝗇𝖾. 𝖳𝗁𝗂𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖾𝗇𝗌𝗎𝗋𝖾𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗋𝖾𝗆𝖺𝗂𝗇𝗌 𝗋𝖾𝗅𝖺𝗍𝗂𝗏𝖾𝗅𝗒 𝗅𝗈𝗐 𝗂𝗇 𝗁𝖾𝗂𝗀𝗁𝗍, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝗅𝗂𝗄𝖾 𝗌𝖾𝖺𝗋𝖼𝗁, 𝗂𝗇𝗌𝖾𝗋𝗍, 𝖺𝗇𝖽 𝖽𝖾𝗅𝖾𝗍𝖾 𝗆𝗈𝗋𝖾 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍, 𝗍𝗒𝗉𝗂𝖼𝖺𝗅𝗅𝗒 𝗂𝗇 𝗅𝗈𝗀𝖺𝗋𝗂𝗍𝗁𝗆𝗂𝖼 𝗍𝗂𝗆𝖾 𝖼𝗈𝗆𝗉𝗅𝖾𝗑𝗂𝗍𝗒 (𝖮(𝗅𝗈𝗀 𝗇)), 𝗐𝗁𝖾𝗋𝖾 𝗇 𝗂𝗌 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝖿 𝗇𝗈𝖽𝖾𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾. 𝖤𝗑𝖺𝗆𝗉𝗅𝖾𝗌 𝗈𝖿 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾𝗌 𝗂𝗇𝖼𝗅𝗎𝖽𝖾 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾𝗌 𝖺𝗇𝖽 𝖱𝖾𝖽-𝖡𝗅𝖺𝖼𝗄 𝗍𝗋𝖾𝖾𝗌, 𝗐𝗁𝗂𝖼𝗁 𝗂𝗆𝗉𝗅𝖾𝗆𝖾𝗇𝗍 𝗌𝖾𝗅𝖿-𝖻𝖺𝗅𝖺𝗇𝖼𝗂𝗇𝗀 𝗆𝖾𝖼𝗁𝖺𝗇𝗂𝗌𝗆𝗌 𝗍𝗈 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇 𝗍𝗁𝗂𝗌 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒 𝖺𝖿𝗍𝖾𝗋 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝗍𝗁𝖺𝗍 𝗆𝗈𝖽𝗂𝖿𝗒 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾.
• Unbalanced Trees
  𝖠𝗇 𝗎𝗇𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾, 𝗈𝗇 𝗍𝗁𝖾 𝗈𝗍𝗁𝖾𝗋 𝗁𝖺𝗇𝖽, 𝖽𝗈𝖾𝗌 𝗇𝗈𝗍 𝗁𝖺𝗏𝖾 𝗋𝖾𝗌𝗍𝗋𝗂𝖼𝗍𝗂𝗈𝗇𝗌 𝗈𝗇 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾𝗌 𝗈𝖿 𝗂𝗍𝗌 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌. 𝖨𝗇 𝖺𝗇 𝖾𝗑𝗍𝗋𝖾𝗆𝖾 𝖼𝖺𝗌𝖾, 𝗍𝗁𝗂𝗌 𝖼𝖺𝗇 𝗅𝖾𝖺𝖽 𝗍𝗈 𝖺 𝗌𝗂𝗍𝗎𝖺𝗍𝗂𝗈𝗇 𝗐𝗁𝖾𝗋𝖾 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝖺 "𝗅𝗂𝗇𝖾𝖺𝗋 𝖼𝗁𝖺𝗂𝗇" 𝗈𝖿 𝗇𝗈𝖽𝖾𝗌, 𝗋𝖾𝗌𝖾𝗆𝖻𝗅𝗂𝗇𝗀 𝖺 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍, 𝖾𝗌𝗉𝖾𝖼𝗂𝖺𝗅𝗅𝗒 𝗂𝖿 𝗇𝗈𝖽𝖾𝗌 𝖺𝗋𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗂𝗇 𝖺 𝗌𝗈𝗋𝗍𝖾𝖽 𝗈𝗋𝖽𝖾𝗋. 𝖨𝗇 𝗌𝗎𝖼𝗁 𝖼𝖺𝗌𝖾𝗌, 𝗍𝗁𝖾 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝗅𝗂𝗄𝖾 𝗌𝖾𝖺𝗋𝖼𝗁, 𝗂𝗇𝗌𝖾𝗋𝗍, 𝖺𝗇𝖽 𝖽𝖾𝗅𝖾𝗍𝖾 𝖼𝖺𝗇 𝖽𝖾𝗀𝗋𝖺𝖽𝖾 𝗍𝗈 𝗅𝗂𝗇𝖾𝖺𝗋 𝗍𝗂𝗆𝖾 𝖼𝗈𝗆𝗉𝗅𝖾𝗑𝗂𝗍𝗒 (𝖮(𝗇)), 𝗆𝖺𝗄𝗂𝗇𝗀 𝗍𝗁𝖾𝗆 𝗂𝗇𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍 𝖺𝗌 𝗍𝗁𝖾 𝗌𝗂𝗓𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗀𝗋𝗈𝗐𝗌. 𝖴𝗇𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾𝗌 𝖽𝗈 𝗇𝗈𝗍 𝖺𝗎𝗍𝗈𝗆𝖺𝗍𝗂𝖼𝖺𝗅𝗅𝗒 𝖺𝖽𝗃𝗎𝗌𝗍 𝗈𝗋 𝗋𝖾𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝗍𝗁𝖾𝗆𝗌𝖾𝗅𝗏𝖾𝗌, 𝗐𝗁𝗂𝖼𝗁 𝖼𝖺𝗇 𝗅𝖾𝖺𝖽 𝗍𝗈 𝗌𝗎𝖻𝗈𝗉𝗍𝗂𝗆𝖺𝗅 𝗉𝖾𝗋𝖿𝗈𝗋𝗆𝖺𝗇𝖼𝖾 𝖿𝗈𝗋 𝖼𝖾𝗋𝗍𝖺𝗂𝗇 𝗌𝖾𝗊𝗎𝖾𝗇𝖼𝖾𝗌 𝗈𝖿 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌.

𝖪𝖾𝖾𝗉𝗂𝗇𝗀 𝖺 𝗍𝗋𝖾𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗂𝗇𝗏𝗈𝗅𝗏𝖾𝗌 𝖺𝖽𝗃𝗎𝗌𝗍𝗂𝗇𝗀 𝗍𝗁𝖾 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗎𝗌𝗂𝗇𝗀 rotations.

Rotations

• Left-Left Rotation:

  • 𝖭𝗈𝖽𝖾 𝖸 𝖻𝖾𝖼𝗈𝗆𝖾 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗍𝗁𝖺𝗍 𝗈𝗋𝗂𝗀𝗂𝗇𝖺𝗅𝗅𝗒 𝗁𝖺𝖽 𝖹 𝖺𝗌 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍
  • 𝖳𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖸 (𝗐𝗁𝗂𝖼𝗁 𝗂𝗌 𝖳𝟥) 𝖻𝖾𝖼𝗈𝗆𝖾 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖹
  • 𝖭𝗈𝖽𝖾 𝖹 𝖻𝖾𝖼𝗈𝗆𝖾 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝖸
  
  𝖳𝗁𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝗉𝖾𝗋𝖿𝗈𝗋𝗆𝖾𝖽 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗇𝗈𝖽𝖾 𝖸 𝗂𝗌 𝗅𝖾𝖿𝗍-𝗁𝖾𝖺𝗏𝗒, 𝖺𝗇𝖽 𝖺 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝗇𝖾𝖾𝖽𝖾𝖽 𝗍𝗈 𝗋𝖾𝗌𝗍𝗈𝗋𝖾 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾.

• Left-Right Rotation:

  • 𝖥𝗂𝗋𝗌𝗍 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇
    • 𝖷 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗍𝗁𝖺𝗍 𝗈𝗋𝗂𝗀𝗂𝗇𝖺𝗅𝗅𝗒 𝗁𝖺𝖽 𝖸 𝖺𝗌 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍
    • 𝖸 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝖷
    • 𝖳𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖷 (𝖳𝟤) 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝖸
  • 𝖲𝖾𝖼𝗈𝗇𝖽 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇
    • 𝖷 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗍𝗁𝖺𝗍 𝗈𝗋𝗂𝗀𝗂𝗇𝖺𝗅𝗅𝗒 𝗁𝖺𝖽 𝖹 𝖺𝗌 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍
    • 𝖹 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝖷
    • 𝖳𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖷 (𝖳𝟥) 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝖹
  𝖳𝗁𝗂𝗌 𝗂𝗌 𝖺 𝖼𝗈𝗆𝖻𝗂𝗇𝖺𝗍𝗂𝗈𝗇 𝗈𝖿 𝖺 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝖿𝗈𝗅𝗅𝗈𝗐𝖾𝖽 𝖻𝗒 𝖺 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇, 𝗎𝗌𝖾𝖽 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗇𝗈𝖽𝖾 𝖹 𝗂𝗌 𝗋𝗂𝗀𝗁𝗍-𝗁𝖾𝖺𝗏𝗒.

• Right-Right Rotation:

  
  𝖳𝗁𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝗉𝖾𝗋𝖿𝗈𝗋𝗆𝖾𝖽 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗇𝗈𝖽𝖾 𝖸 𝗂𝗌 𝗋𝗂𝗀𝗁𝗍-𝗁𝖾𝖺𝗏𝗒, 𝖺𝗇𝖽 𝖺 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝗇𝖾𝖾𝖽𝖾𝖽 𝗍𝗈 𝗋𝖾𝗌𝗍𝗈𝗋𝖾 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾.

• Right-Left Rotation:

  
  𝖳𝗁𝗂𝗌 𝗂𝗌 𝖺 𝖼𝗈𝗆𝖻𝗂𝗇𝖺𝗍𝗂𝗈𝗇 𝗈𝖿 𝖺 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝖿𝗈𝗅𝗅𝗈𝗐𝖾𝖽 𝖻𝗒 𝖺 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇, 𝗎𝗌𝖾𝖽 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗇𝗈𝖽𝖾 `𝖹` 𝗂𝗌 𝗅𝖾𝖿𝗍-𝗁𝖾𝖺𝗏𝗒.

---

Heap

Note

𝖠 𝗁𝖾𝖺𝗉 𝗂𝗌 𝖺 𝗌𝗉𝖾𝖼𝗂𝖺𝗅 𝖳𝗋𝖾𝖾-𝖻𝖺𝗌𝖾𝖽 𝖽𝖺𝗍𝖺 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗂𝗇 𝗐𝗁𝗂𝖼𝗁 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖡𝗂𝗇𝖺𝗋𝗒 𝖳𝗋𝖾𝖾 𝗂𝗇 𝗐𝗁𝗂𝖼𝗁 𝖾𝖺𝖼𝗁 𝗅𝖾𝗏𝖾𝗅 𝗁𝖺𝗌 𝖺𝗅𝗅 𝗈𝖿 𝗂𝗍𝗌 𝗇𝗈𝖽𝖾𝗌.
𝖳𝗁𝖾 𝖾𝗑𝖼𝖾𝗉𝗍𝗂𝗈𝗇 𝗍𝗈 𝗍𝗁𝗂𝗌 𝗂𝗌 𝗍𝗁𝖾 𝖻𝗈𝗍𝗍𝗈𝗆 𝗅𝖾𝗏𝖾𝗅 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾, 𝗐𝗁𝗂𝖼𝗁 𝗐𝖾 𝖿𝗂𝗅𝗅 𝗂𝗇 𝖿𝗋𝗈𝗆 𝗅𝖾𝖿𝗍 𝗍𝗈 𝗋𝗂𝗀𝗁𝗍.

Heap type

• 𝖬𝗂𝗇 𝖧𝖾𝖺𝗉 - 𝗂𝖿 𝖾𝖺𝖼𝗁 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗅𝖾𝗌𝗌 𝗍𝗁𝖺𝗇 𝗈𝗋 𝖾𝗊𝗎𝖺𝗅 𝗍𝗈 𝗂𝗍𝗌 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 (𝗋𝗈𝗈𝗍 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍 𝗂𝗍𝖾𝗆)
• 𝖬𝖺𝗑 𝖧𝖾𝖺𝗉 - 𝗂𝖿 𝖾𝖺𝖼𝗁 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝗈𝗋 𝖾𝗊𝗎𝖺𝗅 𝗍𝗈 𝗂𝗍𝗌 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 (𝗋𝗈𝗈𝗍 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝗍𝗁𝖾 𝗅𝖺𝗋𝗀𝖾𝗌𝗍 𝗂𝗍𝖾𝗆)

Representation

𝖣𝖾𝗌𝗉𝗂𝗍𝖾 𝖻𝖾𝗂𝗇𝗀 𝖼𝗈𝗇𝖼𝖾𝗉𝗍𝗎𝖺𝗅𝗅𝗒 𝖺 𝗍𝗋𝖾𝖾, 𝖺 𝗁𝖾𝖺𝗉 𝗂𝗌 𝗂𝗆𝗉𝗅𝖾𝗆𝖾𝗇𝗍𝖾𝖽 𝗎𝗌𝗂𝗇𝗀 𝖺𝗇 𝖺𝗋𝗋𝖺𝗒. 𝖳𝗁𝗂𝗌 𝗂𝗌 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍 𝗂𝗇 𝗍𝖾𝗋𝗆𝗌 𝗈𝖿 𝖻𝗈𝗍𝗁 𝗌𝗉𝖺𝖼𝖾 𝖺𝗇𝖽 𝗍𝗂𝗆𝖾.
𝖴𝗌𝗂𝗇𝗀 𝖺𝗇 𝖺𝗋𝗋𝖺𝗒 𝖾𝗅𝗂𝗆𝗂𝗇𝖺𝗍𝖾𝗌 𝗍𝗁𝖾 𝗇𝖾𝖾𝖽 𝖿𝗈𝗋 𝗉𝗈𝗂𝗇𝗍𝖾𝗋𝗌 𝗋𝖾𝗊𝗎𝗂𝗋𝖾𝖽 𝗂𝗇 𝖺 𝗍𝗋𝖾𝖾 𝗋𝖾𝗉𝗋𝖾𝗌𝖾𝗇𝗍𝖺𝗍𝗂𝗈𝗇, 𝗍𝗁𝗎𝗌 𝗌𝖺𝗏𝗂𝗇𝗀 𝗌𝗉𝖺𝖼𝖾.

• S𝗈 𝗁𝖾𝖺𝗉 𝗍𝗁𝖺𝗍 𝗅𝗈𝗈𝗄𝗌 𝗅𝗂𝗄𝖾 𝗍𝗁𝗂𝗌:

• I𝗌 𝗋𝖾𝗉𝗋𝖾𝗌𝖾𝗇𝗍𝖾𝖽 𝗅𝗂𝗄𝖾 𝗍𝗁𝗂𝗌:

𝖧𝖾𝖺𝗉 𝗋𝗈𝗈𝗍 𝗂𝗌 𝗂𝗇𝖽𝖾𝗑=𝟢 - 𝖿𝗂𝗋𝗌𝗍 𝗂𝗍𝖾𝗆 𝗈𝖿 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒. 𝖣𝖾𝗉𝖾𝗇𝖽𝗂𝗇𝗀 𝗈𝗇 𝗍𝗁𝖾 𝗂𝗆𝗉𝗅𝖾𝗆𝖾𝗇𝗍𝖺𝗍𝗂𝗈𝗇 𝖬𝗂𝗇/𝖬𝖺𝗑, 𝗋𝗈𝗈𝗍 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝗍𝗁𝖾 𝗌𝗆𝖺𝗅𝗅𝖾𝗌𝗍/𝗅𝖺𝗋𝗀𝖾𝗌𝗍 𝗂𝗍𝖾𝗆 𝗈𝖿 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒

𝖶𝗁𝖾𝗇 𝗎𝗌𝗂𝗇𝗀 𝖺𝗇 𝖺𝗋𝗋𝖺𝗒 𝗍𝗈 𝗋𝖾𝗉𝗋𝖾𝗌𝖾𝗇𝗍 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗁𝖾𝖺𝗉, 𝗐𝖾 𝖺𝗋𝖾 𝖾𝗌𝗌𝖾𝗇𝗍𝗂𝖺𝗅𝗅𝗒 "𝖿𝗅𝖺𝗍𝗍𝖾𝗇𝗂𝗇𝗀" 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗂𝗇𝗍𝗈 𝖺 𝗅𝗂𝗌𝗍, 𝗐𝗁𝗂𝗅𝖾 𝗌𝗍𝗂𝗅𝗅 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇𝗂𝗇𝗀 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍-𝖼𝗁𝗂𝗅𝖽 𝗋𝖾𝗅𝖺𝗍𝗂𝗈𝗇𝗌𝗁𝗂𝗉𝗌.

𝖳𝗁𝖾 𝖺𝗋𝗋𝖺𝗒 𝗂𝗌 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾𝖽 𝗌𝗎𝖼𝗁 𝗍𝗁𝖺𝗍 𝖿𝗈𝗋 𝖺𝗇𝗒 𝗀𝗂𝗏𝖾𝗇 𝗂𝗇𝖽𝖾𝗑 i (𝗌𝗍𝖺𝗋𝗍𝗂𝗇𝗀 𝖺𝗍 𝟢), 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗂𝗌 𝖺𝗍 𝟤*𝗂 + 𝟣 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗂𝗌 𝖺𝗍 𝟤*𝗂 + 2.
𝖢𝗈𝗇𝗏𝖾𝗋𝗌𝖾𝗅𝗒, 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗈𝖿 𝖺𝗇𝗒 𝗇𝗈𝗇-𝗋𝗈𝗈𝗍 𝗇𝗈𝖽𝖾 𝖺𝗍 𝗂𝗇𝖽𝖾𝗑 i 𝗂𝗌 𝖺𝗍 (𝗂-𝟣)/𝟤.

• 𝖠𝖽𝖽𝗂𝗇𝗀 𝖺𝗇 𝖨𝗍𝖾𝗆 (𝗉𝗎𝗌𝗁):
  • 𝖶𝗁𝖾𝗇 𝗐𝖾 𝖺𝖽𝖽 𝖺 𝗇𝖾𝗐 𝗂𝗍𝖾𝗆 𝗍𝗈 𝖺 𝗁𝖾𝖺𝗉, 𝗐𝖾 𝖺𝗅𝗐𝖺𝗒𝗌 𝖺𝖽𝖽 𝗂𝗍 𝖺𝗍 𝗍𝗁𝖾 𝗏𝖾𝗋𝗒 𝖾𝗇𝖽 𝗈𝖿 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒. 𝖳𝗁𝗂𝗌 𝖾𝗇𝗌𝗎𝗋𝖾𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗋𝖾𝗆𝖺𝗂𝗇𝗌 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖺𝗇𝖽 𝖾𝗏𝖾𝗋𝗒 𝗅𝖾𝗏𝖾𝗅 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖿𝗂𝗅𝗅𝖾𝖽 𝖿𝗋𝗈𝗆 𝗅𝖾𝖿𝗍 𝗍𝗈 𝗋𝗂𝗀𝗁𝗍 𝗐𝗂𝗍𝗁𝗈𝗎𝗍 𝗀𝖺𝗉𝗌.
  • 𝖠𝖿𝗍𝖾𝗋 𝖺𝖽𝖽𝗂𝗇𝗀 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗂𝗍𝖾𝗆, 𝗐𝖾 "𝗁𝖾𝖺𝗉𝗂𝖿𝗒" 𝗂𝗍 𝖻𝗒 𝖼𝗈𝗆𝗉𝖺𝗋𝗂𝗇𝗀 𝗂𝗍 𝗐𝗂𝗍𝗁 𝗂𝗍𝗌 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝖺𝗇𝖽 𝗌𝗐𝖺𝗉𝗉𝗂𝗇𝗀 𝗂𝖿 𝗇𝖾𝖼𝖾𝗌𝗌𝖺𝗋𝗒 (𝗂𝗇 𝖺 𝗆𝖺𝗑-𝗁𝖾𝖺𝗉, 𝗂𝖿 𝗂𝗍'𝗌 𝗅𝖺𝗋𝗀𝖾𝗋 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍). 𝖳𝗁𝗂𝗌 𝗉𝗋𝗈𝖼𝖾𝗌𝗌 𝗂𝗌 𝗋𝖾𝗉𝖾𝖺𝗍𝖾𝖽 𝗎𝗇𝗍𝗂𝗅 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗂𝗍𝖾𝗆 𝗂𝗌 𝗂𝗇 𝗍𝗁𝖾 𝖼𝗈𝗋𝗋𝖾𝖼𝗍 𝗉𝗈𝗌𝗂𝗍𝗂𝗈𝗇 𝗐𝗁𝖾𝗋𝖾 𝗂𝗍'𝗌 𝗇𝗈 𝗅𝗈𝗇𝗀𝖾𝗋 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝗂𝗍𝗌 𝗉𝖺𝗋𝖾𝗇𝗍.
• 𝖱𝖾𝗆𝗈𝗏𝗂𝗇𝗀 𝖺𝗇 𝖨𝗍𝖾𝗆 (𝗉𝗈𝗉):
  • 𝖶𝗁𝖾𝗇 𝗋𝖾𝗆𝗈𝗏𝖾𝗂𝗇𝗀 𝖺𝗇 𝗂𝗍𝖾𝗆, 𝗎𝗌𝗎𝖺𝗅𝗅𝗒 𝗐𝖾 𝗋𝖾𝗆𝗈𝗏𝖾 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍, 𝖻𝖾𝖼𝖺𝗎𝗌𝖾 𝗍𝗁𝖺𝗍'𝗌 𝗍𝗁𝖾 𝗆𝖺𝗑𝗂𝗆𝗎𝗆 𝗂𝗍𝖾𝗆 𝗂𝗇 𝖺 𝗆𝖺𝗑-𝗁𝖾𝖺𝗉.
  • 𝖳𝗈 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇 𝗍𝗁𝖾 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝗍𝗋𝖾𝖾 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒, 𝗐𝖾 𝗍𝖺𝗄𝖾 𝗍𝗁𝖾 𝗅𝖺𝗌𝗍 𝗂𝗍𝖾𝗆 𝗂𝗇 𝗍𝗁𝖾 𝖺𝗋𝗋𝖺𝗒 𝖺𝗇𝖽 𝗆𝗈𝗏𝖾 𝗂𝗍 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍 𝗉𝗈𝗌𝗂𝗍𝗂𝗈𝗇. 𝖥𝗋𝗈𝗆 𝗍𝗁𝖾𝗋𝖾, 𝗐𝖾 "𝗁𝖾𝖺𝗉𝗂𝖿𝗒" 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝖻𝗒 𝗋𝖾𝗉𝖾𝖺𝗍𝖾𝖽𝗅𝗒 𝗌𝗐𝖺𝗉𝗉𝗂𝗇𝗀 𝗍𝗁𝗂𝗌 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗐𝗂𝗍𝗁 𝗂𝗍𝗌 𝗅𝖺𝗋𝗀𝖾𝗌𝗍 𝖼𝗁𝗂𝗅𝖽 (𝗂𝖿 𝗂𝗍'𝗌 𝗌𝗆𝖺𝗅𝗅𝖾𝗋 𝗍𝗁𝖺𝗇 𝗂𝗍𝗌 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇) 𝗎𝗇𝗍𝗂𝗅 𝗍𝗁𝖾 𝗁𝖾𝖺𝗉 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒 𝗂𝗌 𝗋𝖾𝗌𝗍𝗈𝗋𝖾𝖽.

F𝗈r𝗆𝗎𝗅𝖺𝗌 𝖿𝗈𝗋 𝖿𝗂𝗇𝖽𝗂𝗇𝗀 parent and child nodes 𝖿𝗋𝗈𝗆 𝗁𝖾𝖺𝗉 𝗐𝗁𝗂𝖼𝗁 𝗂𝗌 𝗋𝖾𝗉𝗋𝖾𝗌𝖾𝗇𝗍𝖾𝖽 𝖺𝗌 𝖺𝗇 𝖺𝗋𝗋𝖺𝗒:

• 𝖥𝗂𝗇𝖽 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 - 𝗉𝖺𝗋𝖾𝗇𝗍(𝗂𝗇𝖽𝖾𝗑) = (𝗂𝗇𝖽𝖾𝗑 - 𝟣) / 𝟤
• 𝖥𝗂𝗇𝖽 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 - 𝗅𝖾𝖿𝗍(𝗂𝗇𝖽𝖾𝗑) = 𝟤 * 𝗂𝗇𝖽𝖾𝗑 + 𝟣
• 𝖥𝗂𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 - 𝗋𝗂𝗀𝗁𝗍(𝗂𝗇𝖽𝖾𝗑) = 𝟤 * 𝗂𝗇𝖽𝖾𝗑 + 𝟤

𝖥𝗈𝗋 𝖾𝗑𝖺𝗆𝗉𝗅𝖾:

• 𝖯𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗈𝖿 𝟩 𝗂𝗌 - 𝗉𝖺𝗋𝖾𝗇𝗍(𝟥) = (𝟥-𝟣) / 𝟤 = 𝟣 𝗌𝗈, 𝗉𝖺𝗋𝖾𝗇𝗍𝖭𝗈𝖽𝖾𝖨𝗇𝖽𝖾𝗑 = 𝟣 (𝟥 𝗂𝗌 𝗂𝗇𝖽𝖾𝗑 𝗈𝖿 𝗂𝗍𝖾𝗆 𝟩)
• 𝖫𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 𝗈𝖿 𝟪 𝗂𝗌, 𝗅𝖾𝖿𝗍(𝟣) = (𝟤 𝗑 𝟣) + 𝟣 = 𝟥 𝗌𝗈, 𝗅𝖾𝖿𝗍𝖢𝗁𝗂𝗅𝖽𝖭𝗈𝖽𝖾𝖨𝗇𝖽𝖾𝗑 = 𝟥 (𝗂𝗍𝖾𝗆: 𝟩)
• 𝖱𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗇𝗈𝖽𝖾 𝗈𝖿 𝟪 𝗂𝗌, 𝗋𝗂𝗀𝗁𝗍(𝟣) = (𝟤 𝗑 𝟣) + 𝟤 = 𝟦 𝗌𝗈, 𝗋𝗂𝗀𝗁𝗍𝖢𝗁𝗂𝗅𝖽𝖭𝗈𝖽𝖾𝖨𝗇𝖽𝖾𝗑 = 𝟦 (𝗂𝗍𝖾𝗆: 𝟣)

Operations

• I𝗇𝗌𝖾𝗋𝗍: Θ(𝗅𝗈𝗀 𝗇)
• D𝖾𝗅𝖾𝗍𝖾: Θ(𝗅𝗈𝗀 𝗇)
• F𝗂𝗇𝖽 𝗆𝗂𝗇/𝗆𝖺𝗑: 𝖮(1) (𝗍𝗁𝖾 𝗆𝖺𝗑𝗂𝗆𝗎𝗆/𝗆𝗂𝗇𝗂𝗆𝗎𝗆 𝗂𝗍𝖾𝗆 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝖺𝗍 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗍𝗁𝗂𝗌 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇 𝗐𝗂𝗍𝗁 O(1) 𝗍𝗂𝗆𝖾 𝖼𝗈𝗆𝗉𝗅𝖾𝗑𝗂𝗍𝗒)

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Binary Search Tree

Note

𝖠 𝖡𝗂𝗇𝖺𝗋𝗒 𝖲𝖾𝖺𝗋𝖼𝗁 𝖳𝗋𝖾𝖾 𝗂𝗌 𝖺 𝗇𝗈𝖽𝖾-𝖻𝖺𝗌𝖾𝖽 𝖽𝖺𝗍𝖺 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗐𝗁𝖾𝗋𝖾 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗌 𝖺 𝗄𝖾𝗒 𝖺𝗇𝖽 𝗍𝗐𝗈 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌, 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍.
𝖳𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗌 𝗈𝗇𝗅𝗒 𝗇𝗈𝖽𝖾𝗌 𝗐𝗂𝗍𝗁 𝗄𝖾𝗒𝗌 𝗅𝖾𝗌𝗌𝖾𝗋 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾’𝗌 𝗄𝖾𝗒. 𝖳𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗌 𝗈𝗇𝗅𝗒 𝗇𝗈𝖽𝖾𝗌 𝗐𝗂𝗍𝗁 𝗄𝖾𝗒𝗌 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾’𝗌 𝗄𝖾𝗒.

𝖫𝖾𝗍 Ｔ = 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾
𝖫𝖾𝗍 Ｎ = 𝗇𝗈𝖽𝖾
𝖥𝗈𝗋 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾 Ｎ 𝗂𝗇 Ｔ, 𝗂𝖿 Ｎ.𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 Ｎ.𝗋𝗂𝗀𝗁𝗍 𝖾𝗑𝗂𝗌𝗍, 𝗍𝗁𝖾𝗇:

• 𝖠𝗅𝗅 𝗏𝖺𝗅𝗎𝖾𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗋𝗈𝗈𝗍𝖾𝖽 𝖺𝗍 Ｎ.𝗅𝖾𝖿𝗍 𝖺𝗋𝖾 𝗅𝖾𝗌𝗌 𝗍𝗁𝖺𝗇 Ｎ.𝗏𝖺𝗅𝗎𝖾.
• 𝖠𝗅𝗅 𝗏𝖺𝗅𝗎𝖾𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗋𝗈𝗈𝗍𝖾𝖽 𝖺𝗍 Ｎ.𝗋𝗂𝗀𝗁𝗍 𝖺𝗋𝖾 𝗀𝗋𝖾𝖺𝗍𝖾𝗋 𝗍𝗁𝖺𝗇 Ｎ.𝗏𝖺𝗅𝗎𝖾.

Operations

• 𝖲𝖾𝖺𝗋𝖼𝗁: 𝖡𝖾𝖼𝖺𝗎𝗌𝖾 𝗈𝖿 𝗂𝗍𝗌 𝗈𝗋𝖽𝖾𝗋𝖾𝖽 𝗇𝖺𝗍𝗎𝗋𝖾, 𝗌𝖾𝖺𝗋𝖼𝗁𝗂𝗇𝗀 𝖿𝗈𝗋 𝖺𝗇 𝖾𝗅𝖾𝗆𝖾𝗇𝗍 𝗂𝗇 𝖺 𝖡𝖲𝖳 𝗂𝗌 𝗍𝗒𝗉𝗂𝖼𝖺𝗅𝗅𝗒 Θ(𝗅𝗈𝗀 𝗇) 𝗈𝗋 𝖮(𝗇) 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗋𝖾𝗌𝖾𝗆𝖻𝗅𝖾𝗌 𝖺 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍
• 𝖨𝗇𝗌𝖾𝗋𝗍: 𝖳𝗒𝗉𝗂𝖼𝖺𝗅𝗅𝗒 Θ(𝗅𝗈𝗀 𝗇) 𝗐𝗁𝖾𝗇 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗋𝖾𝗆𝖺𝗂𝗇𝗌 𝗋𝖾𝖺𝗌𝗈𝗇𝖺𝖻𝗅𝗒 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗈𝗋 𝖮(𝗇) 𝗂𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝗁𝗂𝗀𝗁𝗅𝗒 𝗎𝗇𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽
• 𝖣𝖾𝗅𝖾𝗍𝖾: 𝖲𝗂𝗆𝗂𝗅𝖺𝗋 𝗍𝗈 𝗌𝖾𝖺𝗋𝖼𝗁 𝖺𝗇𝖽 𝗂𝗇𝗌𝖾𝗋𝗍 - Θ(𝗅𝗈𝗀 𝗇) 𝗈𝗋 𝖮(𝗇) 𝖿𝗈𝗋 𝗁𝗂𝗀𝗁𝗅𝗒 𝗎𝗇𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗍𝗋𝖾𝖾

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Red-Black Tree

Note

𝖠 𝖱𝖾𝖽-𝖡𝗅𝖺𝖼𝗄 𝖳𝗋𝖾𝖾 𝗂𝗌 𝖺 𝗄𝗂𝗇𝖽 𝗈𝖿 𝗌𝖾𝗅𝖿-𝖻𝖺𝗅𝖺𝗇𝖼𝗂𝗇𝗀 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾 𝗐𝗁𝖾𝗋𝖾 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝖺𝗇 𝖾𝗑𝗍𝗋𝖺 𝖻𝗂𝗍 𝖿𝗈𝗋 𝖽𝖾𝗇𝗈𝗍𝗂𝗇𝗀 𝗍𝗁𝖾 𝖼𝗈𝗅𝗈𝗋 𝗈𝖿 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾, 𝖾𝗂𝗍𝗁𝖾𝗋 𝗋𝖾𝖽 𝗈𝗋 𝖻𝗅𝖺𝖼𝗄.

𝖠 𝖱𝖾𝖽-𝖡𝗅𝖺𝖼𝗄 𝖳𝗋𝖾𝖾 𝗌𝖺𝗍𝗂𝗌𝖿𝗂𝖾𝗌 𝗍𝗁𝖾 𝖿𝗈𝗅𝗅𝗈𝗐𝗂𝗇𝗀 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗂𝖾𝗌:

• 𝖤𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗂𝗌 𝖾𝗂𝗍𝗁𝖾𝗋 𝗋𝖾𝖽 𝗈𝗋 𝖻𝗅𝖺𝖼𝗄.
• 𝖳𝗁𝖾 𝗋𝗈𝗈𝗍 𝗂𝗌 𝖺𝗅𝗐𝖺𝗒𝗌 𝖻𝗅𝖺𝖼𝗄.
• 𝖤𝗏𝖾𝗋𝗒 𝗇𝖾𝗐 𝗇𝗈𝖽𝖾 𝗂𝗌 𝖺𝖽𝖽 𝖺𝗌 𝗋𝖾𝖽.
• 𝖱𝖾𝖽 𝗇𝗈𝖽𝖾𝗌 𝖼𝖺𝗇𝗇𝗈𝗍 𝗁𝖺𝗏𝖾 𝗋𝖾𝖽 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇 (𝗇𝗈 𝗍𝗐𝗈 𝗋𝖾𝖽 𝗇𝗈𝖽𝖾𝗌 𝖼𝖺𝗇 𝖻𝖾 𝖺𝖽𝗃𝖺𝖼𝖾𝗇𝗍).
• 𝖤𝗏𝖾𝗋𝗒 𝗉𝖺𝗍𝗁 𝖿𝗋𝗈𝗆 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝖺𝗇𝗒 𝗈𝖿 𝗂𝗍𝗌 𝖽𝖾𝗌𝖼𝖾𝗇𝖽𝖺𝗇𝗍 𝖭𝖴𝖫𝖫 𝗇𝗈𝖽𝖾𝗌 𝗀𝗈𝖾𝗌 𝗍𝗁𝗋𝗈𝗎𝗀𝗁 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝖿 𝖻𝗅𝖺𝖼𝗄 𝗇𝗈𝖽𝖾𝗌.

𝖠𝖿𝗍𝖾𝗋 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝖺𝗇𝖽 𝖽𝖾𝗅𝖾𝗍𝗂𝗈𝗇, 𝗍𝗁𝖾 𝗋𝖾𝖽-𝖻𝗅𝖺𝖼𝗄 𝗋𝗎𝗅𝖾𝗌 𝖺𝗋𝖾 𝗋𝖾𝗏𝗂𝖾𝗐𝖾𝖽. 𝖨𝖿 𝗍𝗁𝖾𝗒 𝗁𝖺𝗏𝖾 𝖻𝖾𝖾𝗇 𝗏𝗂𝗈𝗅𝖺𝗍𝖾𝖽, 𝗍𝗁𝖾𝗒 𝗆𝗎𝗌𝗍 𝖻𝖾 𝗋𝖾𝗌𝗍𝗈𝗋𝖾𝖽. 𝖳𝗁𝖺𝗍 𝗁𝖺𝗉𝗉𝖾𝗇𝗌 𝖻𝗒 𝗋𝖾𝖼𝗈𝗅𝗈𝗋𝗂𝗇𝗀 𝗇𝗈𝖽𝖾𝗌 𝖺𝗇𝖽 𝖻𝗒 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌.

Red-Black Tree Adjustments

𝖨𝗇 𝖺 𝖱𝖾𝖽-𝖡𝗅𝖺𝖼𝗄 𝖳𝗋𝖾𝖾, 𝖺𝖿𝗍𝖾𝗋 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝗈𝗋 𝖽𝖾𝗅𝖾𝗍𝗂𝗈𝗇, 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗆𝗂𝗀𝗁𝗍 𝗏𝗂𝗈𝗅𝖺𝗍𝖾 𝗍𝗁𝖾 𝗋𝖾𝖽-𝖻𝗅𝖺𝖼𝗄 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗂𝖾𝗌. 𝖳𝗈 𝖿𝗂𝗑 𝗍𝗁𝖾𝗌𝖾 𝗏𝗂𝗈𝗅𝖺𝗍𝗂𝗈𝗇𝗌, 𝗍𝗐𝗈 𝗆𝖺𝗂𝗇 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝗎𝗌𝖾𝖽: 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝖺𝗇𝖽 𝗋𝖾𝖼𝗈𝗅𝗈𝗋𝗂𝗇𝗀. 𝖳𝗁𝖾 𝖼𝗁𝗈𝗂𝖼𝖾 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾𝗌𝖾 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝖽𝖾𝗉𝖾𝗇𝖽𝗌 𝗈𝗇 𝗍𝗁𝖾 𝗌𝗉𝖾𝖼𝗂𝖿𝗂𝖼 𝗌𝖼𝖾𝗇𝖺𝗋𝗂𝗈 𝖾𝗇𝖼𝗈𝗎𝗇𝗍𝖾𝗋𝖾𝖽.

𝖨𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝖢𝖺𝗌𝖾𝗌

• 𝖳𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖾𝗆𝗉𝗍𝗒.

  • 𝖳𝗁𝖾 𝗇𝖾𝗐𝗅𝗒 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗆𝖺𝖽𝖾 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍 𝖺𝗇𝖽 𝖼𝗈𝗅𝗈𝗋𝖾𝖽 𝖻𝗅𝖺𝖼𝗄.

• 𝖳𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗇𝖾𝗐𝗅𝗒 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝗂𝗌 𝖻𝗅𝖺𝖼𝗄.

  • 𝖭𝗈 𝗏𝗂𝗈𝗅𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾𝖽. 𝖭𝗈 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗋 𝗋𝖾𝖼𝗈𝗅𝗈𝗋𝗂𝗇𝗀 𝗂𝗌 𝗇𝖾𝖾𝖽𝖾𝖽.
    

• 𝖳𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝖺𝗇𝖽 𝗎𝗇𝖼𝗅𝖾 𝖺𝗋𝖾 𝗋𝖾𝖽 (𝖯𝖺𝗋𝖾𝗇𝗍-𝗎𝗇𝖼𝗅𝖾 𝗋𝖾𝖽 𝖼𝖺𝗌𝖾).

  • 𝖠𝖼𝗍𝗂𝗈𝗇: 𝖱𝖾𝖼𝗈𝗅𝗈𝗋 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝖺𝗇𝖽 𝗎𝗇𝖼𝗅𝖾 𝖻𝗅𝖺𝖼𝗄, 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 𝗋𝖾𝖽.
  • 𝖭𝖾𝗑𝗍 𝖲𝗍𝖾𝗉: 𝖨𝖿 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 𝗂𝗌 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍, 𝗂𝗍 𝗂𝗌 𝗋𝖾𝖼𝗈𝗅𝗈𝗋𝖾𝖽 𝖻𝗅𝖺𝖼𝗄. 𝖮𝗍𝗁𝖾𝗋𝗐𝗂𝗌𝖾, 𝖼𝗁𝖾𝖼𝗄 𝖿𝗈𝗋 𝖿𝗎𝗋𝗍𝗁𝖾𝗋 𝗏𝗂𝗈𝗅𝖺𝗍𝗂𝗈𝗇𝗌 𝗎𝗉 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾.
    

    Before	After

• 𝖳𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗂𝗌 𝗋𝖾𝖽 𝖻𝗎𝗍 𝗍𝗁𝖾 𝗎𝗇𝖼𝗅𝖾 𝗂𝗌 𝖻𝗅𝖺𝖼𝗄, 𝖿𝗈𝗋𝗆𝗂𝗇𝗀 𝖺 𝗍𝗋𝗂𝖺𝗇𝗀𝗅𝖾 (𝖯𝖺𝗋𝖾𝗇𝗍 𝗋𝖾𝖽, 𝗎𝗇𝖼𝗅𝖾 𝖻𝗅𝖺𝖼𝗄, 𝗍𝗋𝗂𝖺𝗇𝗀𝗅𝖾 𝖿𝗈𝗋𝗆𝖺𝗍𝗂𝗈𝗇).

  • 𝖠𝖼𝗍𝗂𝗈𝗇: 𝖯𝖾𝗋𝖿𝗈𝗋𝗆 𝖺 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗍𝗈 𝗍𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆 𝗍𝗁𝖾 𝖼𝖺𝗌𝖾 𝗂𝗇𝗍𝗈 𝖺 𝗅𝗂𝗇𝖾 𝖿𝗈𝗋𝗆𝖺𝗍𝗂𝗈𝗇 (𝖢𝖺𝗌𝖾 𝟧).
  • 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇: 𝖫𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝖿 𝗍𝗁𝖾 𝗍𝗋𝗂𝖺𝗇𝗀𝗅𝖾 𝗂𝗌 𝗋𝗂𝗀𝗁𝗍-𝗅𝖾𝖺𝗇𝗂𝗇𝗀, 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝖿 𝗅𝖾𝖿𝗍-𝗅𝖾𝖺𝗇𝗂𝗇𝗀.

    • 𝖨𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾, 𝗐𝖾 𝖿𝗂𝗋𝗌𝗍 𝗋𝗈𝗍𝖺𝗍𝖾 𝖺𝗍 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗈𝗉𝗉𝗈𝗌𝗂𝗍𝖾 𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇 𝗈𝖿 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾.
      𝖶𝗁𝖺𝗍 𝖽𝗈𝖾𝗌 𝗍𝗁𝖺𝗍 𝗆𝖾𝖺𝗇?
      𝖨𝖿 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗈𝖿 𝗂𝗍𝗌 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾, 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖺𝗍 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾. 𝖨𝖿 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽, 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍.
      𝖨𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾, 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 (𝟣𝟩) 𝗂𝗌 𝖺 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽, 𝗌𝗈 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖺𝗍 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 (𝟤𝟢 𝗂𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾)

    • 𝖲𝖾𝖼𝗈𝗇𝖽, 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝖺𝗍 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗈𝗉𝗉𝗈𝗌𝗂𝗍𝖾 𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗋𝖾𝗏𝗂𝗈𝗎𝗌 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇. 𝖨𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾, 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝗅𝖾𝖿𝗍 𝖺𝗋𝗈𝗎𝗇𝖽 𝗍𝗁𝖾 𝟣𝟧
      

    • 𝖶𝖾 𝖼𝗈𝗅𝗈𝗋 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾 𝗐𝖾 𝗃𝗎𝗌𝗍 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 (𝟣𝟩 𝗂𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾) 𝖻𝗅𝖺𝖼𝗄 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗈𝗋𝗂𝗀𝗂𝗇𝖺𝗅 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 (𝟣𝟧 𝗂𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾) 𝗋𝖾𝖽

• 𝖳𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝗂𝗌 𝗋𝖾𝖽, 𝗍𝗁𝖾 𝗎𝗇𝖼𝗅𝖾 𝗂𝗌 𝖻𝗅𝖺𝖼𝗄, 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾𝗌 𝖿𝗈𝗋𝗆 𝖺 𝗌𝗍𝗋𝖺𝗂𝗀𝗁𝗍 𝗅𝗂𝗇𝖾 (𝖯𝖺𝗋𝖾𝗇𝗍 𝗋𝖾𝖽, 𝗎𝗇𝖼𝗅𝖾 𝖻𝗅𝖺𝖼𝗄, 𝗅𝗂𝗇𝖾 𝖿𝗈𝗋𝗆𝖺𝗍𝗂𝗈𝗇).

  • 𝖠𝖼𝗍𝗂𝗈𝗇: 𝖱𝗈𝗍𝖺𝗍𝖾 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍, 𝗍𝗁𝖾𝗇 𝗌𝗐𝖺𝗉 𝗍𝗁𝖾 𝖼𝗈𝗅𝗈𝗋𝗌 𝗈𝖿 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 𝖺𝗇𝖽 𝗉𝖺𝗋𝖾𝗇𝗍.
  • 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇: 𝖱𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝖿 𝗍𝗁𝖾 𝗅𝗂𝗇𝖾 𝗂𝗌 𝗅𝖾𝖿𝗍-𝗅𝖾𝖺𝗇𝗂𝗇𝗀, 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝖿 𝗋𝗂𝗀𝗁𝗍-𝗅𝖾𝖺𝗇𝗂𝗇𝗀.
    • "L𝗂𝗇𝖾 𝖿𝗈𝗋𝗆𝖺𝗍𝗂𝗈𝗇" 𝗆𝖾𝖺𝗇𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗉𝖺𝗍𝗁 𝖿𝗋𝗈𝗆 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 𝗍𝗈 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝖿𝗈𝗋𝗆𝗌 𝖺 𝗅𝗂𝗇𝖾, 𝗌𝗎𝖼𝗁 𝖺𝗌 𝗍𝗁𝖾 𝟣𝟧, 𝟤𝟢, 𝖺𝗇𝖽 𝟤𝟧 𝗂𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾.
      𝖨𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾, 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝖺𝗍 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 (𝟣𝟧) 𝗂𝗇 𝗍𝗁𝖾 𝗈𝗉𝗉𝗈𝗌𝗂𝗍𝖾 𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇 𝗈𝖿 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝖺𝗇𝖽 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 (𝖺𝖿𝗍𝖾𝗋 𝖺𝗅𝗅, 𝖻𝗈𝗍𝗁 𝗀𝗈 𝗂𝗇 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇 𝗂𝗇 𝗍𝗁𝗂𝗌 𝖼𝖺𝗌𝖾).
      𝖨𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾, 𝗍𝗁𝖾 𝗉𝖺𝗋𝖾𝗇𝗍 𝖺𝗇𝖽 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾𝗌 𝖺𝗋𝖾 𝖻𝗈𝗍𝗁 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇, 𝗌𝗈 𝗐𝖾 𝗋𝗈𝗍𝖺𝗍𝖾 𝗅𝖾𝖿𝗍 𝖺𝗍 𝗍𝗁𝖾 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍. 𝖳𝗁𝖾𝗇 𝗐𝖾 𝗋𝖾𝖼𝗈𝗅𝗈𝗋 𝗍𝗁𝖾 𝖿𝗈𝗋𝗆𝖾𝗋 𝗉𝖺𝗋𝖾𝗇𝗍 (𝟤𝟢 𝗂𝗇 𝗍𝗁𝖾 𝖾𝗑𝖺𝗆𝗉𝗅𝖾) 𝖻𝗅𝖺𝖼𝗄 𝖺𝗇𝖽 𝗍𝗁𝖾 𝖿𝗈𝗋𝗆𝖾𝗋 𝗀𝗋𝖺𝗇𝖽𝗉𝖺𝗋𝖾𝗇𝗍 (𝟣𝟧) 𝗋𝖾𝖽.
      

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

AVL Tree

Note

𝖠𝖵𝖫 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺 𝗌𝖾𝗅𝖿-𝖻𝖺𝗅𝖺𝗇𝖼𝗂𝗇𝗀 𝖡𝗂𝗇𝖺𝗋𝗒 𝖲𝖾𝖺𝗋𝖼𝗁 𝖳𝗋𝖾𝖾 (𝖡𝖲𝖳) 𝗐𝗁𝖾𝗋𝖾 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍𝗌 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗐𝗈 𝖼𝗁𝗂𝗅𝖽 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝗈𝖿 𝖺𝗇𝗒 𝗇𝗈𝖽𝖾 𝖽𝗂𝖿𝖿𝖾𝗋 𝖻𝗒 𝖺𝗍 𝗆𝗈𝗌𝗍 𝗈𝗇𝖾. 𝖳𝗁𝗂𝗌 𝖾𝗇𝗌𝗎𝗋𝖾𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗋𝖾𝗆𝖺𝗂𝗇𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖺𝗇𝖽 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇𝗌 𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍 𝗌𝖾𝖺𝗋𝖼𝗁, 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇, 𝖺𝗇𝖽 𝖽𝖾𝗅𝖾𝗍𝗂𝗈𝗇 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌.

AVL Tree Properties:

• 𝖳𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗂𝗌 𝖺𝗍 𝗆𝗈𝗌𝗍 <𝗂>𝗇 𝗅𝗈𝗀(<𝗂>𝗇), 𝗐𝗁𝖾𝗋𝖾 𝗇 𝗂𝗌 𝗍𝗁𝖾 𝗇𝗎𝗆𝖻𝖾𝗋 𝗈𝖿 𝗇𝗈𝖽𝖾𝗌 𝗂𝗇 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾.
• 𝖥𝗈𝗋 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾, 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍𝗌 𝗈𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝖽𝗂𝖿𝖿𝖾𝗋 𝖻𝗒 𝖺𝗍 𝗆𝗈𝗌𝗍 𝗈𝗇𝖾.
• 𝖳𝗁𝖾 𝗅𝖾𝖿𝗍 𝖺𝗇𝖽 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝗈𝖿 𝖾𝗏𝖾𝗋𝗒 𝗇𝗈𝖽𝖾 𝖺𝗋𝖾 𝗍𝗁𝖾𝗆𝗌𝖾𝗅𝗏𝖾𝗌 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾𝗌.

𝖠𝗇 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾 𝗌𝗍𝗈𝗋𝖾𝗌 𝗂𝗇 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾𝗌 𝗋𝗈𝗈𝗍𝖾𝖽 𝖺𝗍 𝗍𝗁𝗂𝗌 𝗇𝗈𝖽𝖾. 𝖳𝗁𝖾𝗇, 𝖿𝗈𝗋 𝖺𝗇𝗒 𝗇𝗈𝖽𝖾, 𝗐𝖾 𝖼𝖺𝗇 𝖼𝗁𝖾𝖼𝗄 𝗂𝖿 𝗂𝗍 𝗂𝗌 𝗁𝖾𝗂𝗀𝗁𝗍 𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽: 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖽𝗂𝖿𝖿𝖾𝗋 𝖻𝗒 𝗇𝗈 𝗆𝗈𝗋𝖾 𝗍𝗁𝖺𝗇 𝗈𝗇𝖾.

Balance Factor

𝖡𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾 𝗂𝗇 𝖺𝗇 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾 𝗂𝗌 𝗍𝗁𝖾 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾 𝖻𝖾𝗍𝗐𝖾𝖾𝗇 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝖺𝗇𝖽 𝗍𝗁𝖺𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝗍𝗁𝖺𝗍 𝗇𝗈𝖽𝖾.
𝖡𝖺𝗅𝖺𝗇𝖼𝖾 𝖥𝖺𝖼𝗍𝗈𝗋 = (𝖧𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝖫𝖾𝖿𝗍 𝖲𝗎𝖻𝗍𝗋𝖾𝖾 - 𝖧𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝖱𝗂𝗀𝗁𝗍 𝖲𝗎𝖻𝗍𝗋𝖾𝖾) 𝗈𝗋 (𝖧𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝖱𝗂𝗀𝗁𝗍 𝖲𝗎𝖻𝗍𝗋𝖾𝖾 - 𝖧𝖾𝗂𝗀𝗁𝗍 𝗈𝖿 𝖫𝖾𝖿𝗍 𝖲𝗎𝖻𝗍𝗋𝖾𝖾).
𝖳𝗁𝖾 𝗌𝖾𝗅𝖿 𝖻𝖺𝗅𝖺𝗇𝖼𝗂𝗇𝗀 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒 𝗈𝖿 𝖺𝗇 𝖺𝗏𝗅 𝗍𝗋𝖾𝖾 𝗂𝗌 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇𝖾𝖽 𝖻𝗒 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋. 𝖳𝗁𝖾 𝗏𝖺𝗅𝗎𝖾 𝗈𝖿 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗌𝗁𝗈𝗎𝗅𝖽 𝖺𝗅𝗐𝖺𝗒𝗌 𝖻𝖾 -𝟣, 𝟢 𝗈𝗋 +𝟣.

• 𝖥𝗈𝗋 𝖺 𝗀𝗂𝗏𝖾𝗇 𝗇𝗈𝖽𝖾
• 𝖨𝖿 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗂𝗌 𝗁𝗂𝗀𝗁𝖾𝗋: 𝟣 (𝗉𝗈𝗌𝗂𝗏𝗂𝗍𝖾 𝗂𝗇𝗍𝖾𝗀𝖾𝗋)
• 𝖨𝖿 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗂𝗌 𝗁𝗂𝗀𝗁𝖾𝗋: -𝟣 (𝗇𝖾𝗀𝖺𝗍𝗂𝗏𝖾 𝗂𝗇𝗍𝖾𝗀𝖾𝗋)

Insertion and Height Update

• 𝖶𝗁𝖾𝗇 𝖺 𝗇𝗈𝖽𝖾 𝗂𝗌 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗂𝗇𝗍𝗈 𝖺𝗇 𝖠𝖵𝖫 𝗍𝗋𝖾𝖾, 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝗉𝗋𝗈𝖼𝖾𝗌𝗌 𝖿𝗈𝗅𝗅𝗈𝗐𝗌 𝗍𝗁𝖾 𝖻𝖺𝗌𝗂𝖼 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇 𝗉𝗋𝗈𝖼𝖾𝗌𝗌 𝗈𝖿 𝖺 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾:
  • 𝖨𝗇𝗌𝖾𝗋𝗍 𝗍𝗁𝖾 𝖭𝗈𝖽𝖾: 𝖲𝗍𝖺𝗋𝗍𝗂𝗇𝗀 𝖿𝗋𝗈𝗆 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍, 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖾 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗍𝗈 𝖿𝗂𝗇𝖽 𝗍𝗁𝖾 𝖼𝗈𝗋𝗋𝖾𝖼𝗍 𝗉𝗈𝗌𝗂𝗍𝗂𝗈𝗇 𝖿𝗈𝗋 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗇𝗈𝖽𝖾, 𝗆𝖺𝗂𝗇𝗍𝖺𝗂𝗇𝗂𝗇𝗀 𝗍𝗁𝖾 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒.
  • 𝖴𝗉𝖽𝖺𝗍𝖾 𝖧𝖾𝗂𝗀𝗁𝗍𝗌: 𝖠𝖿𝗍𝖾𝗋 𝗂𝗇𝗌𝖾𝗋𝗍𝗂𝗈𝗇, 𝖻𝖺𝖼𝗄𝗍𝗋𝖺𝖼𝗄 𝗎𝗉 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝖿𝗋𝗈𝗆 𝗍𝗁𝖾 𝗂𝗇𝗌𝖾𝗋𝗍𝖾𝖽 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍, 𝗎𝗉𝖽𝖺𝗍𝗂𝗇𝗀 𝗍𝗁𝖾 𝗁𝖾𝗂𝗀𝗁𝗍𝗌 𝗈𝖿 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝖾𝗇𝖼𝗈𝗎𝗇𝗍𝖾𝗋𝖾𝖽.
  • 𝖢𝗁𝖾𝖼𝗄 𝖡𝖺𝗅𝖺𝗇𝖼𝖾 𝖥𝖺𝖼𝗍𝗈𝗋𝗌
  • 𝖶𝗁𝗂𝗅𝖾 𝗎𝗉𝖽𝖺𝗍𝗂𝗇𝗀 𝗁𝖾𝗂𝗀𝗁𝗍𝗌, 𝖼𝖺𝗅𝖼𝗎𝗅𝖺𝗍𝖾 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝖿𝗈𝗋 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾. 𝖨𝖿 𝖺 𝗇𝗈𝖽𝖾'𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝟤 𝗈𝗋 -𝟤, 𝗉𝖾𝗋𝖿𝗈𝗋𝗆 𝗍𝗁𝖾 𝖺𝗉𝗉𝗋𝗈𝗉𝗋𝗂𝖺𝗍𝖾 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇(𝗌) 𝗍𝗈 𝗋𝖾𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾.

Handling Imbalance (Balance Factor of 2 or -2)

• 𝖶𝗁𝖾𝗇 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖿𝖺𝖼𝗍𝗈𝗋 𝗈𝖿 𝖺 𝗇𝗈𝖽𝖾 𝖻𝖾𝖼𝗈𝗆𝖾𝗌 𝟤 𝗈𝗋 -𝟤, 𝗂𝗍 𝗂𝗇𝖽𝗂𝖼𝖺𝗍𝖾𝗌 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗁𝖺𝗌 𝖻𝖾𝖼𝗈𝗆𝖾 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝖺𝗍 𝗍𝗁𝖺𝗍 𝗇𝗈𝖽𝖾, 𝖺𝗇𝖽 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝗋𝖾𝗊𝗎𝗂𝗋𝖾𝖽 𝗍𝗈 𝗋𝖾𝗌𝗍𝗈𝗋𝖾 𝗍𝗁𝖾 𝖻𝖺𝗅𝖺𝗇𝖼𝖾. 𝖳𝗁𝖾𝗋𝖾 𝖺𝗋𝖾 𝖿𝗈𝗎𝗋 𝗉𝗈𝗌𝗌𝗂𝖻𝗅𝖾 𝖼𝖺𝗌𝖾𝗌 𝗈𝖿 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾:
  • 𝖫𝖾𝖿𝗍-𝖫𝖾𝖿𝗍 (𝖫𝖫): 𝖨𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖼𝖺𝗎𝗌𝖾𝖽 𝖻𝗒 𝖺𝖽𝖽𝗂𝗇𝗀 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽. 𝖲𝗈𝗅𝗎𝗍𝗂𝗈𝗇: 𝖲𝗂𝗇𝗀𝗅𝖾 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇.
  • 𝖱𝗂𝗀𝗁𝗍-𝖱𝗂𝗀𝗁𝗍 (𝖱𝖱): 𝖨𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖼𝖺𝗎𝗌𝖾𝖽 𝖻𝗒 𝖺𝖽𝖽𝗂𝗇𝗀 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽. 𝖲𝗈𝗅𝗎𝗍𝗂𝗈𝗇: 𝖲𝗂𝗇𝗀𝗅𝖾 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇.
  • 𝖫𝖾𝖿𝗍-𝖱𝗂𝗀𝗁𝗍 (𝖫𝖱): 𝖨𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖼𝖺𝗎𝗌𝖾𝖽 𝖻𝗒 𝖺𝖽𝖽𝗂𝗇𝗀 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽. 𝖲𝗈𝗅𝗎𝗍𝗂𝗈𝗇: 𝖣𝗈𝗎𝖻𝗅𝖾 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇, 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝖿𝗈𝗅𝗅𝗈𝗐𝖾𝖽 𝖻𝗒 𝖺 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗌𝗎𝖻𝗍𝗋𝖾𝖾.
  • 𝖱𝗂𝗀𝗁𝗍-𝖫𝖾𝖿𝗍 (𝖱𝖫): 𝖨𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝖼𝖺𝗎𝗌𝖾𝖽 𝖻𝗒 𝖺𝖽𝖽𝗂𝗇𝗀 𝖺 𝗇𝗈𝖽𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝗌𝗎𝖻𝗍𝗋𝖾𝖾 𝗈𝖿 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽. 𝖲𝗈𝗅𝗎𝗍𝗂𝗈𝗇: 𝖣𝗈𝗎𝖻𝗅𝖾 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇, 𝗋𝗂𝗀𝗁𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝖿𝗈𝗅𝗅𝗈𝗐𝖾𝖽 𝖻𝗒 𝖺 𝗅𝖾𝖿𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾𝖽 𝗌𝗎𝖻𝗍𝗋𝖾𝖾.

Rotations

• 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝗍𝗁𝖾 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝗍𝗁𝖺𝗍 𝗋𝖾𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗍𝗁𝖾 𝗍𝗋𝖾𝖾 𝗍𝗈 𝗋𝖾𝗌𝗍𝗈𝗋𝖾 𝗂𝗍𝗌 𝖻𝖺𝗅𝖺𝗇𝖼𝖾 𝗐𝗁𝗂𝗅𝖾 𝗉𝗋𝖾𝗌𝖾𝗋𝗏𝗂𝗇𝗀 𝗍𝗁𝖾 𝖻𝗂𝗇𝖺𝗋𝗒 𝗌𝖾𝖺𝗋𝖼𝗁 𝗍𝗋𝖾𝖾 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒.
  • 𝖲𝗂𝗇𝗀𝗅𝖾 𝖱𝗂𝗀𝗁𝗍 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇 (𝖫𝖫 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇): 𝖳𝗁𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝖺𝗉𝗉𝗅𝗂𝖾𝖽 𝗐𝗁𝖾𝗇 𝖺 𝗅𝖾𝖿𝗍-𝗅𝖾𝖿𝗍 𝖼𝖺𝗌𝖾 𝗈𝖼𝖼𝗎𝗋𝗌. 𝖳𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾'𝗌 𝗋𝗈𝗈𝗍 𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝖾𝖽 𝗍𝗈 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾.
  • 𝖲𝗂𝗇𝗀𝗅𝖾 𝖫𝖾𝖿𝗍 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇 (𝖱𝖱 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇): 𝖳𝗁𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗂𝗌 𝖺𝗉𝗉𝗅𝗂𝖾𝖽 𝗐𝗁𝖾𝗇 𝖺 𝗋𝗂𝗀𝗁𝗍-𝗋𝗂𝗀𝗁𝗍 𝖼𝖺𝗌𝖾 𝗈𝖼𝖼𝗎𝗋𝗌. 𝖳𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾'𝗌 𝗋𝗈𝗈𝗍 𝗂𝗌 𝗋𝗈𝗍𝖺𝗍𝖾𝖽 𝗍𝗈 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍, 𝗆𝖺𝗄𝗂𝗇𝗀 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝗍𝗁𝖾 𝗇𝖾𝗐 𝗋𝗈𝗈𝗍 𝗈𝖿 𝗍𝗁𝖾 𝗌𝗎𝖻𝗍𝗋𝖾𝖾.
  • 𝖣𝗈𝗎𝖻𝗅𝖾 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇 (𝖫𝖱 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝖺𝗇𝖽 𝖱𝖫 𝖱𝗈𝗍𝖺𝗍𝗂𝗈𝗇): 𝖣𝗈𝗎𝖻𝗅𝖾 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗋𝖾 𝖺𝗉𝗉𝗅𝗂𝖾𝖽 𝗂𝗇 𝗍𝗁𝖾 𝖼𝖺𝗌𝖾 𝗈𝖿 𝖺𝗇 𝖫𝖱 𝗈𝗋 𝖱𝖫 𝗂𝗆𝖻𝖺𝗅𝖺𝗇𝖼𝖾. 𝖨𝗍 𝖼𝗈𝗇𝗌𝗂𝗌𝗍𝗌 𝗈𝖿 𝗍𝗐𝗈 𝗌𝗂𝗇𝗀𝗅𝖾 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇𝗌: 𝖿𝗂𝗋𝗌𝗍 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝖼𝗁𝗂𝗅𝖽 (𝗅𝖾𝖿𝗍 𝗈𝗇 𝗍𝗁𝖾 𝗅𝖾𝖿𝗍 𝖼𝗁𝗂𝗅𝖽 𝖿𝗈𝗋 𝖫𝖱, 𝗋𝗂𝗀𝗁𝗍 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗂𝗀𝗁𝗍 𝖼𝗁𝗂𝗅𝖽 𝖿𝗈𝗋 𝖱𝖫) 𝖺𝗇𝖽 𝗍𝗁𝖾𝗇 𝖺 𝗌𝖾𝖼𝗈𝗇𝖽 𝗋𝗈𝗍𝖺𝗍𝗂𝗈𝗇 𝗈𝗇 𝗍𝗁𝖾 𝗋𝗈𝗈𝗍 (𝗋𝗂𝗀𝗁𝗍 𝖿𝗈𝗋 𝖫𝖱, 𝗅𝖾𝖿𝗍 𝖿𝗈𝗋 𝖱𝖫).

Note

More on AVL Trees and how they work - happycoders.eu

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

LinkedList

Note

𝖫𝗂𝗇𝗄𝖾𝖽𝖫𝗂𝗌𝗍𝗌 𝖺𝗋𝖾 𝖺 𝗌𝖾𝗊𝗎𝖾𝗇𝖼𝖾 𝗈𝖿 𝗇𝗈𝖽𝖾𝗌, 𝖾𝖺𝖼𝗁 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗂𝗇𝗀 𝖽𝖺𝗍𝖺 𝖺𝗇𝖽 𝖺 𝗋𝖾𝖿𝖾𝗋𝖾𝗇𝖼𝖾 (𝗅𝗂𝗇𝗄) 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾. 𝖤𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗍𝗒𝗉𝗂𝖼𝖺𝗅𝗅𝗒 𝖼𝗈𝗇𝗍𝖺𝗂𝗇𝗌 𝗍𝗐𝗈 𝗉𝖺𝗋𝗍𝗌:

• Data: 𝖳𝗁𝖾 𝖺𝖼𝗍𝗎𝖺𝗅 𝗏𝖺𝗅𝗎𝖾 𝗈𝗋 𝗂𝗇𝖿𝗈𝗋𝗆𝖺𝗍𝗂𝗈𝗇 𝗍𝗁𝖺𝗍 𝗍𝗁𝖾 𝗇𝗈𝖽𝖾 𝗋𝖾𝗉𝗋𝖾𝗌𝖾𝗇𝗍𝗌.
• Pointer (or Link): 𝖠 𝗋𝖾𝖿𝖾𝗋𝖾𝗇𝖼𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗌𝖾𝗊𝗎𝖾𝗇𝖼𝖾. 𝖨𝗇 𝖺 𝗌𝗂𝗇𝗀𝗅𝗒 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍, 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗉𝗈𝗂𝗇𝗍𝗌 𝗍𝗈 𝗂𝗍𝗌 𝗌𝗎𝖼𝖼𝖾𝗌𝗌𝗈𝗋, 𝗐𝗁𝗂𝗅𝖾 𝗂𝗇 𝖺 𝖽𝗈𝗎𝖻𝗅𝗒 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍, 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝗉𝗈𝗂𝗇𝗍𝖾𝗋𝗌 𝗍𝗈 𝖻𝗈𝗍𝗁 𝗂𝗍𝗌 𝗉𝗋𝖾𝗏𝗂𝗈𝗎𝗌 𝖺𝗇𝖽 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾.

𝖳𝗁𝖾 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗌𝗍𝖺𝗋𝗍𝗌 𝗐𝗂𝗍𝗁 𝗍𝗁𝖾 𝗁𝖾𝖺𝖽, 𝗐𝗁𝗂𝖼𝗁 𝗉𝗈𝗂𝗇𝗍𝗌 𝗍𝗈 𝗍𝗁𝖾 𝖿𝗂𝗋𝗌𝗍 𝗇𝗈𝖽𝖾, 𝖼𝗈𝗇𝗍𝗂𝗇𝗎𝖾𝗌 𝖺𝗌 𝖾𝖺𝖼𝗁 𝗌𝗎𝖻𝗌𝖾𝗊𝗎𝖾𝗇𝗍 𝗇𝗈𝖽𝖾 𝗉𝗈𝗂𝗇𝗍𝗌 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍, 𝖺𝗇𝖽 𝖼𝗈𝗇𝖼𝗅𝗎𝖽𝖾𝗌 𝗐𝗂𝗍𝗁 𝗍𝗁𝖾 𝗍𝖺𝗂𝗅, 𝗐𝗁𝗂𝖼𝗁 𝗉𝗈𝗂𝗇𝗍𝗌 𝗍𝗈 𝗇𝗅𝗅, 𝗂𝗇𝖽𝗂𝖼𝖺𝗍𝗂𝗇𝗀 𝗍𝗁𝖾 𝖾𝗇𝖽 𝗈𝖿 𝗍𝗁𝖾 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍.
𝖤𝖺𝖼𝗁 𝗅𝗂𝗌𝗍 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝗂𝗌 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗁𝖺𝗌 𝖺 𝗏𝖺𝗅𝗎𝖾 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒 𝖿𝗈𝗋 𝗌𝗍𝗈𝗋𝗂𝗇𝗀 𝖽𝖺𝗍𝖺, 𝖺𝗇𝖽 𝖺 𝗇𝖾𝗑𝗍 𝗉𝗋𝗈𝗉𝖾𝗋𝗍𝗒 𝗍𝗁𝖺𝗍 𝗉𝗈𝗂𝗇𝗍𝗌 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗅𝗂𝗌𝗍.

• Rust:

     pub struct Node<T> {
         pub data: T,
         pub next: Option<NonNull<Node<T>>>
     }
  
     pub struct LinkedList<T> {
         pub head: Option<NonNull<Node<T>>>,
         pub tail: Option<NonNull<Node<T>>>,
         pub length: usize,
     }

• C#:

     public class LinkedList<T>
     {
        private class Node
        {
            public T data;
            public Node next;
        }
  
        public Node head;
        public Node tail;
        public int length;
     }

Types of LinkedLists

• Singly Linked List: 𝖤𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝗈𝗇𝗅𝗒 𝗈𝗇𝖾 𝗉𝗈𝗂𝗇𝗍𝖾𝗋 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾
• Doubly Linked List: 𝖤𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗁𝖺𝗌 𝗍𝗐𝗈 𝗉𝗈𝗂𝗇𝗍𝖾𝗋𝗌, 𝗈𝗇𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾 𝖺𝗇𝖽 𝗈𝗇𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗉𝗋𝖾𝗏𝗂𝗈𝗎𝗌 𝗇𝗈𝖽𝖾
• Circular Linked List: 𝖳𝗁𝖾 𝗅𝖺𝗌𝗍 𝗇𝗈𝖽𝖾 𝗉𝗈𝗂𝗇𝗍𝗌 𝖻𝖺𝖼𝗄 𝗍𝗈 𝗍𝗁𝖾 𝖿𝗂𝗋𝗌𝗍 𝗇𝗈𝖽𝖾, 𝖿𝗈𝗋𝗆𝗂𝗇𝗀 𝖺 𝖼𝗂𝗋𝖼𝗅𝖾 (𝗂𝗍 𝖼𝖺𝗇 𝖻𝖾 𝗌𝗂𝗇𝗀𝗅𝗒 𝗈𝗋 𝖽𝗈𝗎𝖻𝗅𝗒)

Singly Linked Lists vs. Doubly Linked Lists

• 𝖲𝗂𝗇𝗀𝗅𝗒 𝖫𝗂𝗇𝗄𝖾𝖽 𝖫𝗂𝗌𝗍𝗌:
  𝖨𝗇 𝗍𝗁𝖾𝗌𝖾 𝗅𝗂𝗌𝗍𝗌, 𝖾𝖺𝖼𝗁 𝗇𝗈𝖽𝖾 𝗉𝗈𝗂𝗇𝗍𝗌 𝗈𝗇𝗅𝗒 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝗇𝗈𝖽𝖾. 𝖳𝗁𝗂𝗌 𝗌𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝗂𝗌 𝗌𝗂𝗆𝗉𝗅𝖾 𝖺𝗇𝖽 𝗆𝖾𝗆𝗈𝗋𝗒-𝖾𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍, 𝖻𝗎𝗍 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅 𝖼𝖺𝗇 𝗈𝗇𝗅𝗒 𝗈𝖼𝖼𝗎𝗋 𝗂𝗇 𝗈𝗇𝖾 𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇.
• 𝖣𝗈𝗎𝖻𝗅𝗒 𝖫𝗂𝗇𝗄𝖾𝖽 𝖫𝗂𝗌𝗍𝗌:
  𝖳𝗁𝖾𝗌𝖾 𝗅𝗂𝗌𝗍𝗌 𝖺𝗅𝗅𝗈𝗐 𝗇𝗈𝖽𝖾𝗌 𝗍𝗈 𝗉𝗈𝗂𝗇𝗍 𝖻𝗈𝗍𝗁 𝗍𝗈 𝗍𝗁𝖾 𝗇𝖾𝗑𝗍 𝖺𝗇𝖽 𝗍𝗁𝖾 𝗉𝗋𝖾𝗏𝗂𝗈𝗎𝗌 𝗇𝗈𝖽𝖾𝗌, 𝖾𝗇𝖺𝖻𝗅𝗂𝗇𝗀 𝖻𝗂𝖽𝗂𝗋𝖾𝖼𝗍𝗂𝗈𝗇𝖺𝗅 𝗍𝗋𝖺𝗏𝖾𝗋𝗌𝖺𝗅. 𝖳𝗁𝗂𝗌 𝗂𝗇𝖼𝗋𝖾𝖺𝗌𝖾𝖽 𝖿𝗅𝖾𝗑𝗂𝖻𝗂𝗅𝗂𝗍𝗒 𝖼𝗈𝗆𝖾𝗌 𝖺𝗍 𝗍𝗁𝖾 𝖼𝗈𝗌𝗍 𝗈𝖿 𝖺𝖽𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅 𝗆𝖾𝗆𝗈𝗋𝗒 𝗎𝗌𝖺𝗀𝖾 𝖽𝗎𝖾 𝗍𝗈 𝗍𝗁𝖾 𝗌𝖾𝖼𝗈𝗇𝖽 𝗉𝗈𝗂𝗇𝗍𝖾𝗋.

• Rust:

     pub struct Node<T> {
         pub data: T,
         pub next: Option<NonNull<Node<T>>>,
         pub prev: Option<NonNull<Node<T>>>
     }
  
     pub struct LinkedList<T> {
         pub head: Option<NonNull<Node<T>>>,
         pub tail: Option<NonNull<Node<T>>>,
         pub length: usize,
     }

• C#:

     public class LinkedList<T>
     {
        private class Node
        {
            public T data;
            public Node next;
            public Node prev;
        }
  
        public Node head;
        public Node tail;
        public int length;
     }

𝖠𝗌 𝗐𝖾 𝖼𝖺𝗇 𝗌𝖾𝖾 𝗍𝗁𝖾 𝗈𝗇𝗅𝗒 𝖽𝗂𝖿𝖿𝖾𝗋𝖾𝗇𝖼𝖾 𝗂𝗌 𝗍𝗁𝖾 𝖺𝖽𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅 𝗉𝗋𝖾𝗏𝗂𝗈𝗎𝗌 𝗉𝗈𝗂𝗇𝗍𝖾𝗋 (𝗉𝗋𝖾𝗏) 𝗈𝗇 𝗍𝗁𝖾 𝖽𝗈𝗎𝖻𝗅𝗒 𝗅𝗂𝗇𝗄𝖾𝖽 𝗅𝗂𝗌𝗍.

Operations and Complexity

Operation	Location	Complexity
Insertion	At the beginning (head)	O(1)
	At the end (tail)	O(1)
	In the middle	O(n)
Deletion	At the beginning (head)	O(1)
	Singly - At the end (tail)	O(n)
	Doubly - At the end (tail)	O(1)
	In the middle	O(n)
Traversal/Searching	-	O(n)

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Disjoint-set

Note

𝖣𝗂𝗌𝗃𝗈𝗂𝗇𝗍-𝗌𝖾𝗍 𝖣𝖺𝗍𝖺 𝖲𝗍𝗋𝗎𝖼𝗍𝗎𝗋𝖾 𝖺𝗅𝗌𝗈 𝗄𝗇𝗈𝗐𝗇 𝖺𝗌 𝖺 𝗎𝗇𝗂𝗈𝗇-𝖿𝗂𝗇𝖽, 𝗄𝖾𝖾𝗉𝗌 𝗍𝗋𝖺𝖼𝗄 𝗈𝖿 𝖺 𝗌𝖾𝗍 𝗈𝖿 𝖾𝗅𝖾𝗆𝖾𝗇𝗍𝗌 𝗉𝖺𝗋𝗍𝗂𝗍𝗂𝗈𝗇𝖾𝖽 𝗂𝗇𝗍𝗈 𝗌𝖾𝗏𝖾𝗋𝖺𝗅 𝗇𝗈𝗇-𝗈𝗏𝖾𝗋𝗅𝖺𝗉𝗉𝗂𝗇𝗀 𝗌𝗎𝖻𝗌𝖾𝗍𝗌.

Characteristics

• 𝖤𝖿𝖿𝗂𝖼𝗂𝖾𝗇𝗍 𝖿𝗈𝗋 𝗁𝖺𝗇𝖽𝗅𝗂𝗇𝗀 𝖾𝗊𝗎𝗂𝗏𝖺𝗅𝖾𝗇𝖼𝖾 𝗋𝖾𝗅𝖺𝗍𝗂𝗈𝗇𝗌 𝖺𝗇𝖽 𝖼𝗈𝗇𝗇𝖾𝖼𝗍𝖾𝖽 𝖼𝗈𝗆𝗉𝗈𝗇𝖾𝗇𝗍𝗌 𝗂𝗇 𝖺 𝗇𝖾𝗍𝗐𝗈𝗋𝗄.
• 𝖢𝗈𝗆𝗆𝗈𝗇𝗅𝗒 𝗎𝗌𝖾𝖽 𝗂𝗇 𝖺𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆𝗌 𝗍𝗁𝖺𝗍 𝗋𝖾𝗊𝗎𝗂𝗋𝖾 𝖿𝗋𝖾𝗊𝗎𝖾𝗇𝗍 𝖼𝗁𝖾𝖼𝗄𝗌 𝗈𝖿 𝗐𝗁𝖾𝗍𝗁𝖾𝗋 𝗍𝗐𝗈 𝖾𝗅𝖾𝗆𝖾𝗇𝗍𝗌 𝖺𝗋𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗌𝗎𝖻𝗌𝖾𝗍.

Operations

• Find: 𝖣𝖾𝗍𝖾𝗋𝗆𝗂𝗇𝖾𝗌 𝗐𝗁𝗂𝖼𝗁 𝗌𝗎𝖻𝗌𝖾𝗍 𝖺 𝗉𝖺𝗋𝗍𝗂𝖼𝗎𝗅𝖺𝗋 𝖾𝗅𝖾𝗆𝖾𝗇𝗍 𝗂𝗌 𝗂𝗇. 𝖳𝗁𝗂𝗌 𝖼𝖺𝗇 𝖻𝖾 𝗎𝗌𝖾𝖽 𝖿𝗈𝗋 𝖽𝖾𝗍𝖾𝗋𝗆𝗂𝗇𝗂𝗇𝗀 𝗂𝖿 𝗍𝗐𝗈 𝖾𝗅𝖾𝗆𝖾𝗇𝗍𝗌 𝖺𝗋𝖾 𝗂𝗇 𝗍𝗁𝖾 𝗌𝖺𝗆𝖾 𝗌𝗎𝖻𝗌𝖾𝗍
• Union: 𝖩𝗈𝗂𝗇𝗌 𝗍𝗐𝗈 𝗌𝗎𝖻𝗌𝖾𝗍𝗌 𝗂𝗇𝗍𝗈 𝖺 𝗌𝗂𝗇𝗀𝗅𝖾 𝗌𝗎𝖻𝗌𝖾𝗍

Efficiency

• 𝖶𝗂𝗍𝗁 𝗈𝗉𝗍𝗂𝗆𝗂𝗓𝖺𝗍𝗂𝗈𝗇𝗌 𝗅𝗂𝗄𝖾 𝗎𝗇𝗂𝗈𝗇 𝖻𝗒 𝗋𝖺𝗇𝗄 𝖺𝗇𝖽 𝗉𝖺𝗍𝗁 𝖼𝗈𝗆𝗉𝗋𝖾𝗌𝗌𝗂𝗈𝗇, 𝗍𝗁𝖾 𝗍𝗂𝗆𝖾 𝖼𝗈𝗆𝗉𝗅𝖾𝗑𝗂𝗍𝗒 𝗈𝖿 𝖻𝗈𝗍𝗁 𝖥𝗂𝗇𝖽 𝖺𝗇𝖽 𝖴𝗇𝗂𝗈𝗇 𝗈𝗉𝖾𝗋𝖺𝗍𝗂𝗈𝗇𝗌 𝖼𝖺𝗇 𝖻𝖾 𝖻𝗋𝗈𝗎𝗀𝗁𝗍 𝖽𝗈𝗐𝗇 𝖼𝗅𝗈𝗌𝖾 𝗍𝗈 𝖼𝗈𝗇𝗌𝗍𝖺𝗇𝗍 𝗍𝗂𝗆𝖾, O(α(n)), where α 𝗂𝗌 𝗍𝗁𝖾 𝗂𝗇𝗏𝖾𝗋𝗌𝖾 𝖠𝖼𝗄𝖾𝗋𝗆𝖺𝗇𝗇 𝖿𝗎𝗇𝖼𝗍𝗂𝗈𝗇, 𝗐𝗁𝗂𝖼𝗁 𝗀𝗋𝗈𝗐𝗌 𝗏𝖾𝗋𝗒 𝗌𝗅𝗈𝗐𝗅𝗒 𝖺𝗇𝖽 𝗂𝗌 𝗉𝗋𝖺𝖼𝗍𝗂𝖼𝖺𝗅𝗅𝗒 𝖼𝗈𝗇𝗌𝗍𝖺𝗇𝗍 𝖿𝗈𝗋 𝖺𝗅𝗅 𝗋𝖾𝖺𝗌𝗈𝗇𝖺𝖻𝗅𝖾 𝗂𝗇𝗉𝗎𝗍 𝗌𝗂𝗓𝖾𝗌.

𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜:

---

Graph Theory

Graphs are an abstract idea that represents connections between objects.

Note

Formal definition: An (undirected) graph is a collection Ｖ of vertices, and a collection Ｅ of edges each of which connects a pair of verices.

Key Concepts

• 𝚅𝚎𝚛𝚝𝚒𝚌𝚎𝚜 (𝙽𝚘𝚍𝚎𝚜): The individual items or entities in a graph
• 𝙴𝚍𝚐𝚎𝚜 (𝙻𝚒𝚗𝚔𝚜): The connections between nodes
• Loop: Loops connect a vertex to itself. This means that edge from vertex Ａ points to the same vertex Ａ

---

Representing graphs:

Adjacency Matrix

• Vertices Representation: Each vertex in the graph is associated with one row and one column in the matrix. For a graph with ｎ vertices, the adjacency matrix is an ｎ×ｎ square matrix
• Edges Representation:
  • In an undirected graph, if there is an edge between vertex 𝚒 and vertex 𝚓, then the matrix element as well (since the edge is bidirectional). If there's no edge,
  • In a directed graph if there is a directed edge from vertex 𝚒 to vertex 𝚓. If there's no directed edge from 𝚒 to 𝚓, than
• Weights and Multiple Edges: For weighted graphs, instead of using 1 to indicate an edge, the actual weight of the edge is used. In graphs with multiple edges, the matrix can contain values higher than 1.

Adjacency List

• Vertices Representation: Graph is an array or a list of lists. Each element of this array (or list) corresponds to a vertex in the graph.
• Edges Representation:
  • For each vertex 𝚒, the adjacency list stores a list of vertices that are adjacent to 𝚓.
  • Implemented using an array of linked lists, an array of arrays, hash table or a map where keys are vertices and values are lists of adjacent vertices.
• Directed and Undirected Graphs:
  • In an undirected graph, if vertex 𝚒 is connected to vertex 𝚓, then 𝚒 will appear in 𝚓's list and 𝚓 will appear in 𝚒's list.
  • In a directed graph, if there is an edge from 𝚒 to 𝚓, then 𝚓 appears in 𝚒's list but not necessarily vice versa.
• Weights: If the graph is weighted, each entry in the list can be a pair (or a structure) containing the adjacent vertex and the weight of the edge.

*degree - The degree of a node in a graph is the number of edges that are connected to it.

	Is edge	List edge	List neighbors
Adjacency Matrix	Θ(1)	Θ(|V|2)	Θ(|V|)
Adjacency List	Θ(degree)	Θ(|E|)	Θ(degree)

---

Algorithm runtime

Graph algorithm runtime depents on |V| and |E|

• |V|: number on vertices
• |E|: number on edges

Graph performance depends on the density. Graph density is a measure of how many edges are in the graph compared to the maximum possible number of edges between vertices.

• Dense graph - |E| ≈ |V|²
• Sparse graph - |E| ≈ |V|

Types of Graphs

• 𝚄𝚗𝚍𝚒𝚛𝚎𝚌𝚝𝚎𝚍 𝙶𝚛𝚊𝚙𝚑𝚜: Symmetric relationships
• 𝙳𝚒𝚛𝚎𝚌𝚝𝚎𝚍 𝙶𝚛𝚊𝚙𝚑𝚜: Asymmetric relationships, like web links
• 𝚆𝚎𝚒𝚐𝚑𝚝𝚎𝚍 𝙶𝚛𝚊𝚙𝚑𝚜: Graphs with edge weights, useful in routing problems

Graph Algorithms

Graph Implementations:

Graph Implementation in Rust
Graph Implementation in C#

---

DFS (depth-first search)

Note

Depth-First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at a selected node (root) and explores as far as possible along each branch before backtracking.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Depth-first search
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Initialize:
   • Start at the root node (or any node in a graph).
   • Create a Stack to keep track of the path.
   • Add the starting node to the Stack and mark it as visited.
2. DFS Loop:
   • While the Stack is not empty:
     • Pop a node from the Stack.
     • For each unvisited neighbor of this node:
       • Mark the neighbor as visited.
       • Add the neighbor to the Stack.
3. Complete:
   • Repeat until all reachable nodes are visited.

---

BFS (breadth-first search)

Note

Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at a selected node and explores all neighbor nodes at the present depth before moving on to nodes at the next depth level.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Breadth-first search
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Initialize:
   • Start at the root node (or any node in a graph).
   • Create a Queue to keep track of the nodes to visit.
   • Add the starting node to the Queue and mark it as visited.
2. BFS Loop:
   • While the Queue is not empty:
     • Dequeue a node from the Queue.
     • For each unvisited neighbor of this node:
       • Mark the neighbor as visited.
       • Add the neighbor to the Queue.
3. Complete:
   • Repeat until all reachable nodes are visited.

---

Dijkstra's algorithm

Note

Dijkstra's Algorithm is a pathfinding algorithm that finds the shortest path from a starting node to all other nodes in a weighted graph.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Dijkstra's Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

𝙲𝚘𝚖𝚙𝚞𝚝𝚎𝚛𝚙𝚑𝚒𝚕𝚎 - Dijkstra's Algorithm by Dr Michael Pound

1. Initialize:
   • Set initial distances to all nodes as infinity, except the start node which should be zero.
   • Create a priority queue and add the start node with distance 0.
2. Algorithm Loop:
   • While the priority queue is not empty:
     • Remove the node with the smallest distance.
     • For each neighbor, calculate the new distance and update if it's smaller.
3. Complete:
   • All shortest paths from the start node are determined.

---

Bellman-Ford algorithm

Note

The Bellman-Ford algorithm is used for computing shortest paths in a weighted graph. Unlike Dijkstra's, it can handle graphs with negative weight edges.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Bellman-Ford Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Initialize:
   • Set the distance to the source as 0 and all other distances as infinite.
2. Relaxation Loop:
   • For each edge (u, v), update the distance to v if a shorter path is found via u.
   • Repeat this for all edges |V|-1 times (|V| is the number of vertices).
3. Negative Cycle Check:
   • Check for further distance improvements; if found, a negative cycle exists.

---

Floyd Warshall algorithm

Note

The Floyd-Warshall algorithm is used for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Floyd Warshall Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Matrix Setup:
   • Initialize a matrix with distances between all pairs of vertices. Set 0 for self-loops and infinity for no direct path.
2. Dynamic Programming:
   • Update the matrix to find the shortest distance between each pair using an intermediate vertex.
3. Complete:
   • The matrix now contains the shortest distances between all pairs of nodes.

---

Kruskal algorithm

Note

Kruskal's Algorithm is a minimum spanning tree algorithm that finds an edge subset of a connected, weighted graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Kruskal Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Sort Edges:
   • Sort all edges of the graph in non-decreasing order of their weight.
2. Initialize Forest:
   • Create a forest, initially with each vertex as an individual tree. (use Disjoint-set/Union-Find)
3. Edge Selection:
   • For each edge, check if it forms a cycle in the forest.
     • If not, add it to the forest.
4. Complete:
   • Continue until the forest has (V-1) edges (V is the number of vertices).

---

Prim's algorithm

Note

Prim's Algorithm is a minimum spanning tree algorithm used in a connected, weighted graph. It builds the spanning tree by adding the next cheapest vertex to the existing tree until all vertices are included.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Prim's Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Initialize Priority Queue:
   • Start from a root vertex and add all its edges to a priority queue.
2. Select Cheapest Edge:
   • Repeatedly choose the edge with the smallest weight that connects a vertex in the tree to a vertex outside.
3. Check for Cycles:
   • Ensure that adding the chosen edge doesn’t create a cycle. (use Disjoint-set/Union-Find)
4. Expand the Tree:
   • Add the selected edge and vertex to the spanning tree.
5. Repeat:
   • Continue the process until all vertices are included in the spanning tree.

---

Kosaraju's algorithm

Note

Kosaraju's algorithm is a depth-first search based method used to find strongly connected components in a directed graph. The algorithm involves two passes of depth-first search. The first pass is used to calculate finishing times of vertices, and the second pass identifies the strongly connected components based on these times.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Kosaraju's Algorithm
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. First DFS Pass:
   • Perform a depth-first search (DFS) on the original graph.
   • Track the completion order of vertices and push them onto a stack.
2. Second DFS Pass:
   • Pop nodes from the stack in the order they were completed in the first DFS.
   • Perform DFS on the transposed graph starting from each popped node, if it hasn't been visited.
3. Identify Strongly Connected Components:
   • Each DFS call in the second pass identifies a strongly connected component.
   • Collect the nodes visited in each DFS call as a single SCC.
4. Complete:
   • The algorithm finishes when all vertices have been popped and processed in the second DFS pass. At this point, all SCCs in the graph have been identified.

---

Tarjan's algorithm

Note

Tarjan's algorithm is a depth-first search based algorithm used to find strongly connected components (SCCs) in a directed graph. An SCC is a component where every vertex is reachable from every other vertex in the same component. This algorithm is efficient and can find all SCCs in a graph in linear time.

• 𝙲𝚘𝚗𝚌𝚎𝚙𝚝: Understand the Tarjan's SCCs Algorithm (emre.me)
• 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust - C#

1. Initialize:
   • Assign a unique integer index to each node, initially undefined.
   • Define a low-link value for each node, initially set to its index.
2. Graph Traversal
   • Increment discovery time for each visited node.
   • Store discovery time and initial low-link value for each node.
3. DFS Loop:
   • For each node, count its children and track its parent.
   • Apply DFS recursively to unvisited successors.
   • Update the node's low-link value based on children's low-link values.
4. Handling Back Edges
   • Update the low-link value of the current node based on the discovery time of previously visited nodes that are not the parent.
5. Repeat:
   • Repeat this process for all nodes in the graph.
6. Complete:
   • The algorithm terminates when all nodes have been processed.

Open section -> Tarjan's algorithm use cases Articulation Points To find articulation points using Tarjan's algorithm, an additional step of identifying vertices that, if removed, increase the number of connected components is needed. 𝙴𝚡𝚝𝚎𝚗𝚍𝚎𝚍 𝚂𝚝𝚎𝚙: After completing the DFS loop, check each node. If it's a root node with two or more children, it's an articulation point. For other nodes, if the low-link value of a child is greater than or equal to the index of the node, then this node is an articulation point. 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust | C# Subgraph Components To find subgraph components using Tarjan's algorithm, it's essential to focus on grouping nodes into their respective SCCs. 𝙴𝚡𝚝𝚎𝚗𝚍𝚎𝚍 𝚂𝚝𝚎𝚙: Upon finishing the DFS for a node, if the node's low-link value equals its index, it indicates the start of a new SCC. Collect all nodes explored since then into a separate SCC group. 𝙸𝚖𝚙𝚕𝚎𝚖𝚎𝚗𝚝𝚊𝚝𝚒𝚘𝚗𝚜: Rust | C#