Thynex Academy
Ծրագրավորման ուսումնական գործիքներ
Գործիքների ցանկ

Trees & Advanced Data Structures

BST · AVL · Red-Black Tree · Trie · Heap · Union-Find · Hash · Graph — step-by-step descent, rotation, sift-cascade, path-compression, rehash և BFS/DFS playback ինտերակտիվ visualization-ով։

Binary Search Tree (BST) — դասական ծառ
Յուրաքանչյուր հանգույցի ձախ ենթածառը < բանալին < աջ ենթածառը։ In-order անցումը տալիս է տեսակավորված հաջորդականություն։ Բարդությունը կախված է բարձրությունից h։
  • ✓ insert / find / erase — միջին O(log n)
  • ✓ in-order → տեսակավորված հաջորդականություն
  • ✗ Չհավասարակշռված — worst case O(n) (շղթա)
AVL Tree — ինքնահավասարակշռվող BST
Յուրաքանչյուր հանգույցի balance factor = h(left) − h(right) ∈ {−1, 0, +1}։ Insert / erase-ից հետո կատարվում է rotation (LL, RR, LR, RL)։ Բարձրությունն երաշխավորված ≤ 1.44 · log₂(n+2)։
  • ✓ insert / find / erase — O(log n) երաշխավորված
  • ✓ Հաճախակի rebalance → ավելի «արագ» find vs RBT
  • ✗ Insert/erase-ը մի փոքր ավելի թանկ՝ rotation-ի պատճառով
Red-Black Tree — STL std::set / std::map հիմքը
Հանգույցները կարմիր կամ սև։ Կանոններ՝ root սև, red ↛ red, ամեն path-ում նույն black-height։ Insert/erase-ից հետո՝ recolor + rotation։
  • ✓ insert / find / erase — O(log n) երաշխավորված
  • ✓ Ավելի քիչ rotation vs AVL → ավելի արագ insert/erase
  • ✗ Մի փոքր ավելի «մեծ» (ավելի թույլ հավասարակշռություն)
Trie — prefix tree
Բառի յուրաքանչյուր տառ ⇒ նիշ ենթահաջորդով։ Ընդհանուր prefix-ը կիսվում է, terminal-նիշերը նշվում են isWord։ Operation-ները կախված են բառի երկարությունից L, ոչ թե բառերի քանակից։
  • ✓ insert / find / starts_with — O(L)
  • ✓ Auto-complete, dictionary, IP routing
  • ✗ Memory intensive — մինչև 26 child հանգույց
Binary Heap — array-հիմնված ամբողջական ծառ
Max-heap → parent ≥ children։ Հիմքում՝ std::vector։ Push-ից հետո՝ sift-up, pop-ից հետո՝ sift-down։ Index-ային հաշվարկ՝ parent = ⌊(i−1)/2⌋, children = 2i+1, 2i+2։
  • ✓ push / pop — O(log n), top — O(1)
  • ✓ priority_queue, Dijkstra, top-K, scheduling
  • ✗ Heap ≠ sorted — find, ընդհանուր traversal-ը O(n)
Union-Find / Disjoint Set Union — բազմություններ + միավորում
Յուրաքանչյուր տարրը պահում է իր parent-ը։ find(x)-ը բարձրանում է մինչև root, union(a, b)-ը միացնում է երկու root-ներ։ Path compression + union by rank → գործնականում O(1)։
  • ✓ find / union — O(α(n)) (≈ 4 աշխարհահռչակ չափով)
  • ✓ Kruskal MST, connectivity, Tarjan, image regions
  • ✗ Չի աջակցում split — միայն միավորում
Hash Table — chaining (separate chaining)
Բանալի → hash(key) mod B → bucket index։ Collision-ները լուծվում են շղթայով (linked-list)։ Load factor α = n/B հաջող lookup-ի միջին երկարությունն է։
  • ✓ insert / find / erase — միջին O(1)
  • ✓ unordered_set, unordered_map հիմքը
  • ✗ Worst case O(n) — եթե բոլոր բանալիները նույն bucket-ում
Graph — հանգույցներ + կողեր (V, E)
Adjacency list ներկայացում (edges)։ BFS — հերթով, level-by-level (queue)։ DFS — խորությունով, recursive/stack։ Երկուսն էլ՝ O(V + E)։
  • ✓ add_node / add_edge — O(1)
  • ✓ BFS / DFS — O(V+E) traversal
  • ✓ Կարճագույն ուղի (BFS), connectivity, cycles, topo-sort