இரு கிளை மரம் – பாகம் 2

ஏற்கெனவே இரு கிளை மரம் என்பதன் அமைப்பையும், வரிசையாக அணுகுதல் முறைகள் பற்றியும் சென்ற அத்தியாயத்தில் பார்த்தோம்.

இரு கிளை மரம் : வேர் ‘2’. இலை நுனிகள் ‘2’, ‘5’, ’11’, ‘4’.

இந்த அத்தியாயத்தில் இப்படி பட்ட மரம் என்ற தரவு வடிவத்தில் மேலும் உபயோகம் உள்ள செயல்பாடுகளான சிலவற்றை எப்படி செய்வது என்று காணலாம்.

இது போன்ற மரங்களில் உள்ள அதிக பட்ச அடுக்கு நிலைகளை எண்ணலாம் ? இந்த மரத்தின் இலை நுனிகள் எத்தனை ? இவற்றை எப்படி அணுகுவது ?

  1. நேர் வரிசையில் அணுகுதலை ஏற்கனேவே பெற்றுவிட்டோம். இதன் அடிப்படையில் தன் -முன் (pre-order traversal) என்பதை நிரல் படுத்தலாம்:
  2. நிரல்பாகம் தன்முன்_வரிசையில்_எடு(வேர்,ப)பதிப்பி “%d,”, வேர்[“மதிப்பு”]
    பின்இணை( ப, வேர்[“மதிப்பு”] )@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
    தன்முன்_வரிசையில்_எடு( வேர்[“இடது_நுனி”] , ப)
    முடி

    @( வேர்[“வலது_நுனி”] != [] ) ஆனால்
    தன்முன்_வரிசையில்_எடு( வேர்[“வலது_நுனி”] , ப)
    முடி

    பின்கொடு ப
    முடி

  3. தன் பின் வரிசையில் அணுகுதலை இதே போல் எழுதலாம் :

 

நிரல்பாகம் தன்பின்_வரிசையில்_எடு(வேர்,ப)

@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
தன்பின்_வரிசையில்_எடு( வேர்[“இடது_நுனி”] , ப)
முடி

@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
தன்பின்_வரிசையில்_எடு( வேர்[“வலது_நுனி”] , ப)
முடி

பதிப்பி “%d,”, வேர்[“மதிப்பு”]
பின்இணை( ப, வேர்[“மதிப்பு”] )

பின்கொடு ப
முடி

மரம் உயரம்

மரம் தரவு வடிவத்தின் உயரம் என்பதை  எப்படி கண்டு பிடிப்பது ? இதனை induction என்ற கணிமை கூற்றினால் ஏற்கெனவே ‘வரிசையில் அணுகுதல்’ என்ற அல்கோரிதம் செய்தது போலவே அணுகலாம்.

  1. மரத்தில் 1 நுனி மட்டும் இருந்தால் அது வெறும் வேர் மட்டுமே உள்ளே மரம். இதன் உயரம் 1.
  2. மரம் என்பதற்கு 2, அல்லது 3 நுனிகள் இருந்தால் இதன் உயரம் 2.
  3. மரம் என்பதன் உயரம் அதன் உயரமான இடது கிளை நுனி அல்லது வலது கிளை நுனி என்பதன் மேல் ஒன்று கூடியது:
    1.  மரம் உயரம் = max ( வலது மரம் உயரம் , இடது மரம் உயரம்) + 1

மேல் கண்டா 3 கோட்பாடுகளை கொண்டு நம்மால் ஒரு அல்கோரிதம் எழுதலாம்,

#height of tree

நிரல்பாகம் தன்_உயரம்(வேர்)
இடது_உயரம் = 0
வலது_உயரம் = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இடது_உயரம் = தன்_உயரம்( வேர்[“இடது_நுனி”])
முடி

  @( வேர்[“வலது_நுனி”] != [] ) ஆனால்
வலது_உயரம்= தன்_உயரம்( வேர்[“வலது_நுனி”])
முடி

   பின்கொடு max( இடது_உயரம்,வலது_உயரம்) + 1
முடி

ஒரு மரம் என்பதற்கு அதன் இலை நுனிகளை எப்படி எடுப்பது  ?

#find leaves
நிரல்பாகம் இலை_நுனிகளை_எடு(வேர்,ப)
இடது_காலி = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இலை_நுனிகளை_எடு( வேர்[“இடது_நுனி”] , ப)
இல்லை
இடது_காலி = 1
முடி
வலது_காலி = 0
@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
இலை_நுனிகளை_எடு( வேர்[“வலது_நுனி”] , ப)
இல்லை
வலது_காலி = 1
முடி
@( வலது_காலி && இடது_காலி) ஆனால்
பதிப்பி “%d,”, வேர்[“மதிப்பு”]
பின்இணை( ப, வேர்[“மதிப்பு”] )
முடி
பின்கொடு ப
முடி

இதே போல, ஒரு மரம் தரவு வடிவத்தில் ஒரு குறிப்பிட்ட மதிப்பு உள்ளதா என்று  எப்படி சொல்லுவது ? தேடல் என்பது நமக்கு இந்த செயல்புரியும் அல்கோரிதம்

# search for value
நிரல்பாகம் மரம்_தேடு(வேர்,மதிப்பு)
வலது = 0
இடது = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இடது = மரம்_தேடு ( வேர்[“இடது_நுனி”] , மதிப்பு )
முடி
@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
வலது = மரம்_தேடு ( வேர்[“வலது_நுனி”] ,மதிப்பு )
முடி
@( வலது || இடது ) ஆனால்
பின்கொடு (வலது || இடது)
முடி

பின்கொடு வேர்[“மதிப்பு”] == மதிப்பு
முடி

மதிப்பு1 = 10
மதிப்பு2 = 1000
உள்ளதா1 = மரம்_தேடு(வேர், மதிப்பு1 )
உள்ளதா2 = மரம்_தேடு(வேர், மதிப்பு2 )
பதிப்பி மதிப்பு1, உள்ளதா1
பதிப்பி மதிப்பு2, உள்ளதா2

இந்த நிரல்களை நீங்கள் இங்கு எழில் மொழியில் காணலாம்.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s