Tree node — tree ma’lumot tuzilmasidagi alohida element bo‘lib, qiymat yoki kalit, parentga havola va nol yoki undan ko‘p child bog‘lanishini saqlashi mumkin. Root node’ning parenti yo‘q, leaf node’da esa child mavjud emas.
Tuzilishi
Binary tree node odatda chap va o‘ng child pointeriga ega:
Node {
key
value
left
right
}
N-ary treeda childlar ro‘yxat yoki arrayda saqlanadi. Parent pointer yuqoriga yurishni osonlashtiradi, evaziga har update’da ikki tomon bog‘lanishini izchil saqlash talab etiladi. Immutable tree’da node o‘zgartirilmay, yo‘l bo‘ylab yangi node’lar yaratilishi mumkin.
Root, internal va leaf
Root traversal boshlanadigan yagona yuqori node. Internal node kamida bitta childga ega. Leaf terminal qiymatlarni saqlaydi. Bitta elementli treeda root bir vaqtning o‘zida leaf bo‘lishi mumkin.
Depth rootdan nodegacha edge soni, height node’dan eng uzoq leafgacha edge soni sifatida ko‘p ishlatiladi. Ba’zi manbalar node soni bilan hisoblaydi; hujjatda konvensiya aniq beriladi.
Binary search tree
Binary search tree’da chap subtree kalitlari node kalitidan kichik, o‘ngdagilar katta bo‘ladi; duplicate siyosati alohida belgilanadi. Balans bo‘lmasa sorted insert tree’ni linked listga aylantirib, qidiruvni O(n) qiladi. AVL va red-black tree rotatsiyalar bilan heightni O(log n) atrofida saqlaydi.
Rotation parent-child bog‘lanishlarini o‘zgartiradi, lekin in-order kalit tartibini saqlaydi. Concurrent tree’da pointer update va reader safety lock, copy-on-write yoki epoch/hazard pointer kabi usul talab qiladi.
Storage tree’lari
B-tree/B+tree node odatda disk page’iga mos keladi. Internal node separator kalit va child page pointerlarini, leaf esa record yoki record manzilini saqlaydi. Bitta node ko‘p childga ega bo‘lgani uchun tree height kichik va disk I/O kam bo‘ladi.
Page to‘lsa split, bo‘shasa merge yoki redistribution yuz beradi. Fill factor insertlar uchun joy qoldiradi. Node checksum va page LSN crash recoveryda integrityni tekshiradi.
Traversal
Depth-first traversal preorder, inorder va postorder ko‘rinishida bo‘ladi. Breadth-first traversal queue bilan darajama-daraja yuradi. Recursive implementation sodda, juda chuqur treeda call stack tugashi mumkin; iterative stack ishlatiladi.
Traversal cycle yo‘q deb hisoblaydi. Noto‘g‘ri pointer graph cycle yaratgan bo‘lsa visited set yoki structural validator cheksiz yurishni to‘xtatadi. Shared child mavjud bo‘lsa tuzilma strict tree emas, DAG bo‘lishi mumkin.
Identifikatsiya va serializatsiya
Memory pointer process tashqarisida barqaror ID emas. Database yoki API node uchun stable ID, parent ID va tartib saqlaydi. Recursive JSON katta tree’da payloadni oshiradi; lazy child endpoint yoki flat adjacency list ishlatilishi mumkin.
Node o‘chirilganda subtree bilan nima bo‘lishi — cascade, reparent yoki rad etish — model qoidasi. Parent va child yangilanishi atomik bajariladi. Test root, leaf, bir childli node, duplicate key, deep tree va invalid cycle’ni qamraydi.
Murakkablikka ta’siri
Daraxt balandligi ildizdan barggacha o‘tiladigan tugunlar sonini belgilaydi. Har tugundagi tarmoqlanish ko‘paysa, balandlik kamayishi mumkin, ammo tugun ichida qidirish va uni yangilash narxi o‘zgaradi. Amaliy tuzilmalar shu ikki xarajatni xotira yoki sahifa hajmiga mos muvozanatlashtiradi.
Bog‘liq tushunchalar
Tree, Root node, Leaf node, Internal node, Binary search tree, B-tree, Tree traversal, Parent-child relation