Binary Tree
Data structure में, Binary tree वह tree है जिसमें प्रत्येक node के केवल अधिकतम दो children होते है। जिन्हें left child और right child कहा जाता है। जो root node होता है वह सबसे ऊपरी node होता है।
जब tree में एक भी node नही होता है उसे हम empty tree कहते है।
Threaded Binary Tree
वह binary tree जिसमें वह प्रत्येक node जिसका कोई child नही होता है उसको पॉइंटर replace कर देता है जिसे हम thread कहते है।binary tree के representation में leaf node भी होते है जिनमें null value होती है। जिनके कारण memory का waste होता है इसलिए memory wastage के इस drawback को मिटाने के लिए threaded binary tree के concept को develop किया गया।
यदि tree के left child का node रिक्त(null) हो तो यह नोड उस नोड से replace हो जायेगा जो इस रिक्त नोड के पहले वाला नोड होगा।
इसी प्रकार यदि tree के right child का node रिक्त(null) हो तो यह नोड उस नोड से replace हो जायेगा जो इस रिक्त नोड के पिछले वाला नोड होगा। जो left thread होता है वह predecessor node देता है और जो right thread होता है वह successor node देता है।
image source:threaded binary tree
Threaded Binary tree दो प्रकार के होते है:-
1. Single Threaded Binary Tree
2. Double Threaded Binary Tree
B-Tree
B-tree एकM-Way(multi-way) tree होता है जो कि विशेषकर disk में प्रयोग करने के लिए बनाया जाता है। B-tree को balanced tree कहा जाता है। एक M-way tree के M children हो सकते है। M-way tree एक node में multiple keys को contain कर सकती है। यदि M-way tree का एक नोड keys की k संख्या contain करता है तो उस नोड के children की संख्या k+1 होगी।
B-tree हमेशा perfectly height balanced होती है अर्थात B-tree के प्रत्येक leaf node की समान depth होती है height balanced और weight balanced tree बहुत बड़े डेटा को स्टोर करने के लिए पर्याप्त नही है इसीलिए इस drawback को खत्म करने के लिए B-tree को प्रयोग में लाया जाता है। B-tree का मतलब secondary storage(जैसे-disk) से है। B-tree का प्रयोग ज्यादातर फ़ाइल सिस्टम्स और DBMS में किया जाता है। B-tree डेटाबेस में फाइल्स को locate तथा place करने की method है।