
bainari serch trea

computer shaasthrathil, oro aantharika nodinteyum thacol athath nodinte idathu subtreeyile ellah keekalekkaalum valuthum athinte valath subtriyilullathinekkaal kuravullathumaaya oru verukalulla bainari trea daatta gadanayaanu oordar cheytha allengil sorted bainari trea ennum vilikkunna bainari serch trea (bii. ezz. tii). bainari serch treayile pravartthanangalude samaya sankeernnatha maratthinte uyarathinu nerittu aanupaathikamaanu.
bainari serch treakal daatta enangal vegathil thirayunnathinum kootticherkkunnathinum neekkam cheiyunnathinum bainari thirayal anuvadikkunnu. oro thaarathamyavum sheshikkunna vrukshathinte pakuthiyolam ozhivaakkunna vidhathil oru bii. ezz. tiyile nodukal sthaapichirikkunnathil, lookup prakadanam bainari logarithathinu aanupaathikamaanu. label cheytha daattayude kaaryakshamamaya sambharana prashnathinaayi 1960-kalil bii. ezz. tii. kall aavishkarikkukayum avaa konve bernezhs-liie, david wheeler ennivaykku kaaranamaakukayum cheiyunnu.
oru bainari serch treaude prakadanam maratthilekku nodukal cherkkunna kramatthe aasrayichirikkunnu, kaaranam ekapaksheeyamaaya insersionukal degenerasyilekku nayichekkaam; bainari serch treaude niravadhi vyathiyanangal urappulla ettavum mosham-cases prakadanatthode nirmmikkaan kazhiyum. adisthaana pravarthanangalil iva ulppedunnu thirayal, sanjaaram, ulppeduthal, illaathaakkal. urappulla ettavum mosham-cases sankeernathakalulla bsts, kramappeduthaattha oru shreniyekkaal mikacha prakadanam kaazhchavaykkunnu, ithinu leanier serch samayam aavasyamaanu.
bii. ezz. tii. yude sankeernnatha vishakalanam kaanikkunnath, sharashari, insert, delete, serch enniva formula _ 2 nodukalkku formula _ 1 edukkunnu ennaanu. ettavum mosham saahacharyathil, avaa ottaykku bandhippicha listtilekku tharamthaazhthappedunnu formula _ 3. ekapaksheeyamaaya ulppeduthalukalum illaathaakkalukalum upayogichu maratthinte uyarathinte athirukalillaatha vardhanavu abhisambodhana cheiyunnathinu, ettavum mosham lookup sankeernathaye bainari logarithavumaayi bandhippikkunnathin bst-kalude svayam-balancing vakabhedangal avatharippikkunnu. 1962ll jeorji adalson-velsky evjeni landis kandupidicha aadyathe svayam-santulita bainari thirayal marangalaayirunnu aval marangal.
dynamic settukal, lookup tableukal, munganana cukal thudangiya amoortha daatta tharangal nadappilakkaan bainari serch treakal upayogikkaam, koodaathe trea sortt polulla algorithangal tharamthirikkunnathinum upayogikkaam.
charithram.
bainari serch trea algoritam pii ulppede niravadhi gaveshakar swathanthramaayi kandethi.eph. windley, andrew donald booth, andrew collin, thomas enn. hubbard. 1960 ll magnetic teppukalil label cheytha daatta sambharikkunnathin konve bernezhs-liie, david wheeler ennivar upayogichathaanu eee algoritam. adyakaalavum janapriyavumaya bainari serch trea algorithangalilonnaan hubbard.
nodukal ekapaksheeyamaaya kramatthil cherkkukayaanenkil oru bainari serch treaude samaya sankeernathakal maratthinte uyarathinanusarichu athirukalillaathe vardhikkunnu, athinaal maratthinte uyaram formula 1-maayi bandhippikkunnathin svayam-santulita bainari serch treakal avatharippichu. vrukshathinte uyaram parimithappeduthunnathina vividha uyaram-santulita bainari serch treakal avatharippichu, udaaharanathinu aval trea, treps, chuvapp-karutha marangal. 
vivarangalude kaaryakshamamaya oorganaiseshanaayi 1962 ll jeorji adalson-velsky evjeni landis chernnaanu aval trea kandupidichathu. svayam santhulithamaaya bainari serch trea kandupidicha aadyathe vrukshamaayirunnu ithu.
avalokanam.
eathenkilum prathyeka nooad "eiii" yekkaal valia keekalulla nodukal aaa nodinte valath sub-treakalil "eiii" ykku thulyamo kuravo ulla keekalulla nodukal idathu sub-treakalil "eiii" yilek sookshikkukayum bainari serch property thripthippeduthukayum cheiyunna oru root cheytha bainari treanu bainari serch trea.
bainari serch treakal sortingukalilum serch algorithangalilum falapradamaanu. ennirunnaalum, oru bii. ezz. tii. yude thirayal sankeernnatha nodukal cherkkukayum illaathaakkukayum cheiyunna kramatthe aasrayichirikkunnu; ettavum mosham saahacharyathil, bainari serch treayile thudarchayaaya pravartthanangal degenerasyilekku nayikkukayum ottaykku link cheytha listt (allengil "asanthulithamaaya trea") polulla ghadana roopappeduthukayum cheythekkaam, athinaal link cheytha listtile athe ettavum mosham-cases sankeernathayundu. 
settukal, multisettukal, associative arekal thudangiya amoortha daatta gadanakalude nirmmaanatthil upayogikkunna oru adisthaana daatta ghadana koodiyaanu bainari serch treakal.
pravartthanangal.
thirachil.
oru bainari serch treal oru nirddishta keeykkaayi thirayunnath aavarthichu allengil aavarthichu prograam cheyyaam.
root nooad parishodhichaanu thirayal aarambhikkunnath. maramaanengil, thirayunna thacol maratthil illa. allengil, qee roottinu thulyamaanengil, thirayal vijayikkukayum nooad thirike nalkukayum cheiyunnu. qee rutinekkaal kurravaanengil, idathu subtree parishodhichu thirayal munnott pookunnu. athupole, qee rutinekkaal valuthaanenkil, sariyaaya subtree parishodhichu thirayal munnott pookunnu. qee kandethunnathuvare allengil bakkiyulla subtree formula 5 aakunnathuvare eee prakriya aavarthikkunnu. oru formula 5 subtree athiyathinu sesham thiranja qee kandethiyillengil, qee treal illa.
aavarthana thirayal.
inipparayunna seudocode aavarthanathiloode bii. ezz. tii thirayal nadapadikramam nadappilaakkunnu.
oru formula _ 5 allengil thirayunna formula _ 8 neridunnathuvare aavarthana prakriya thudarunnu.
aavarthana thirayal.
thirachilinte aavarthana pathipp vail looppilekk "antol" cheyyaam. mikka yanthrangalilum, aavarthana pathipp kooduthal kaaryakshamamaanennu kandethiyittundu.
chila leaf nooad vare thirayal thudaraamennathinaal, bst thirayalinte pravartthana samaya sankeernnatha formula 9 aanu, ivide formula 10 ennathu vrukshathinte uyaramaan. ennirunnaalum, bii. ezz. tii thirachilinte ettavum mosham sahacharyam formula _ 3 aanu, ivide formula _ 2 ennathu bii. ezz. tiyile motham nodukalude ennamaanu, kaaranam oru asanthulithamaaya bii. ezz. tii oru link cheytha listtilekku degenerate cheythekkaam. ennirunnaalum, bii. ezz. tii uyaram santhulithamaanenkil uyaram formula _ 1 aanu.
pingami mungami.
chila pravarthanangalkku, oru nooad formula _ 14 nalkiyaal, formula _ 14-nte pingamio mungamio kandethunnathu nirnaayakamaan. bst-nte ellah keekalum vyathyasthamaanennu karuthuka, bst-leeii oru nooad formulayude pingamiyaaya _ 14 formulayude keeyekkaal valuth ettavum cheria qee ulla nodaanu. maruvashathu, bst-leeii oru nooad formula _ 14-nte mungamiyaanu formula _ 14-nte keeyekkaal cheruthaanu ettavum valia qee. bst-ll oru nooad formula _ 14-nte pingami mungami kandethunnathinulla seudocode thaazhepparayunnavayaanu.
nodukalude pingami mungami nirnnayikkunnath polulla chila pravarthanangalil bii. ezz. tiyil oru nooad kandethunnathu polulla pravartthanangal nirnaayakamaan. pravartthanangalude seudocode thaazhepparayunnavayaanu.
ulppeduthal.
insersion, deletion thudangiya pravartthanangal bii. ezz. tii. praathinidhyam chalanathmakamaayi marran kaaranamaakunnu. bii. ezz. tii. yude gunangal nilanilkkunna reethiyil dattaa ghadana parishkarikkanam. bii. ezz. tiyil puthiya nodukal leaf nodukalaayi cherkkunnu. insersion ooppareshante aavarthana nadappakkalaanu thaazhepparayunnath.
formula 14-nte rakshaakarthaavaayi eee nadapadikramam oru "trailing pooyintar" formula _ 21 nilanirthunnu. line 2-ll aarambhikkunnathin sesham, 4-11 lainukalilulla vail lupe pooyintarukal update cheyyaan kaaranamaakunnu. formula _ 21 formula _ 5 aanenkil, bst shoonyamaanu, athinaal formula _ 25 bainari serch trea formula _ 26-nte root nodaayi cherkkunnu, athu formula _ 5 allengil, keekal 15-19 varikalile formula _ 21-maayi thaarathamyam cheythukondu insersion munnott pookukayum athinanusarichu nooad cherkkukayum cheiyunnu.
neekkam cheyyuka.
bainari serch trea formula _ 30 ll ninnu oru nooad illaathaakkunnathinu moonnu kesukalunda
inipparayunna seudocode oru bainari serch treal illaathaakkal pravartthanam nadappilaakkunnu.
formula _ 54 nadapadikramam mukalil soochippicha 3 prathyeka kesukalumaayi bandhappettirikkunnu. 2-3 varikal cases 1 kaikaaryam cheiyunnu; 4-5 varikal cases 2 kaikaaryam cheiyunnu, cases 3-nuu lineukal 6-16 kaikaaryam cheiyunnu. bainari serch trea formula 30-ll nooad formula _ 56-neey formula _ 57 upayogichu maattisthaapikkunnathina helper function formula _ 55 illaathaakkal algorithathinullil upayogikkunnu. eee nadapadikramam formula _ 30-ll ninnu formula _ 56-nte illathacal (pakaravum) kaikaaryam cheiyunnu.
transgender.
inrder, preorder, poosttoordar trea vaakk enningane moonnu adisthaana algorithangaliloode bii. ezz. tii. kadannupokaam.
trea vaakkinte aavarthana nadappakkalaanu thaazhepparayunnath.
santulita bainari serch trease.
punassamyamanam cheyyaathe, oru bainari serch treal ulppeduthukayo illaathaakkukayo cheiyunnathu degenerationilekku nayichekkaam, athinte falamaayi treaude uyara formula _ 2 (ivide formula _ 2 ennathu oru treayile enangalude ennamaanu), athinaal lookup prakadanam oru leanier serchinte prakadanatthilekku vashalaakunnu. serch trea santhulithavum uyaram formula _ 1 kondu parimithappedutthiyathum bainari serch treaude upayogakshamathayude thacolaanu. bainari logarithammik sankeernathayode vrukshathinte uyaram nilanirthaan roopakalppana cheythirikkunna marathilekkulla updation pravarthanangalil "svayam balancing" samvidaanangaliloode ithu nedaan kazhiyum.
uyaram santhulithamaaya marangal.
idathu upavrikshathinteyum valath upavrikshathinteyum uyaram sthiramaaya oru gadakathaal bandhappettirikkunnave urappaanengil oru vrukshathinte uyaram santhulithamaanu. eee vasthu aval maram parichayappedutthukayum chuvanna-karutha maram thudarukayum cheythu. root muthal parishkkaricha leaf nodilekkulla paathayile ellah nodukaludeyum uyaram nireekshikkukayum maratthilekku cherkkukayum illaathaakkukayum cheiyunna oro pravartthanatthilum sariyaakkukayum venam.
bharam santhulithamaaya marangal.
oru santhulithamaaya bharam ulla maratthil, santhulithamaaya oru vrukshathinte maanadandam upavrikshangalude elakalude ennamaanu. idathu, valath subtreeyukalude bharam formula 64 anusarichu vyathyaasappedunnu. ennirunnaalum, vyathyasam bhaaratthinte 65 anupatha formula bandhikkappettirikkunnu, kaaranam formula 64 nte sakthamaaya balance avastha formula 1 rebalancing varkk upayogichu nilanirthaan kazhiyilla. 65-bharamullah santhulithamaaya marangalude soothravaakyam santhulithaavasthayude oru muzhuvan kudumbatthinum nalkunnu, avide oro idathu, valath subtriykkum subtreeyude motham bhaaratthinte 65-aamm formulayude oru bhaagamenkilum undu.
tharangal.
tii-trea, treep, redu-black trea, bii-trea, 2-3 trea, splay trea ennivayulppede niravadhi svayam santulita bainari serch treakalund.
aaplikkeshanukalude udaaharanagal.
tharamthirichu.
bainari serch treakal trea sortt polulla sorting algorithangalil upayogikkunnu, avide ellah gadakangalum oresamayam cherkkukayum trea kramatthil sanjarikkukayum cheiyunnu. bii. ezz. tii. kall quixortilum upayogikkunnu.
munganana kyoo pravartthanangal.
nodile qee mungananakalaayi upayogichu munganana cukal nadappilakkaan bainari serch treakal upayogikkunnu. kyoovil puthiya gadakangal cherkkunnath saadhaarana bii. ezz. tii. insersion pravartthanatthe pinthudarunnu, ennaal neekkam cheyyal pravartthanam munganana kyoovinte tharatthe aasrayichirikkunnu

