19-5-³ª.ÀÌÁø Æ®¸®

³ëµåÀÇ Â÷¼ö¿¡´Â Á¦ÇÑÀÌ ¾øÀ¸¹Ç·Î ÀÓÀÇ °³¼öÀÇ ÀڽĵéÀ» °¡Áú ¼ö ÀÖ´Ù. ÀÌ·± ³ëµå¸¦ Ç¥ÇöÇÏ·Á¸é ´ÙÀ½°ú °°Àº ±¸Á¶Ã¼¸¦ ¼±¾ðÇØ¾ß ÇÑ´Ù.

 

struct Node

{

     int data;

     Node *link;

};

 

data´Â ÀÌ ³ëµå°¡ ÀúÀåÇÒ ½ÇÁ¦ µ¥ÀÌÅÍÀ̸ç ÇÊ¿ä¿¡ µû¶ó ¾ó¸¶µçÁö ´õ ¸¹Àº ¸â¹öµéÀ» Æ÷ÇÔÇÒ ¼ö ÀÖ´Ù. link´Â ÀÚ½Ä ³ëµåµé·Î ¿¬°áµÇ´Â ¸µÅ©ÀÇ ¹è¿­À̸ç ÀÚ½ÄÀÇ °³¼ö¸¸Å­ µ¿ÀûÀ¸·Î ÇÒ´çµÈ´Ù. ¶Ç´Â ÃÖ´ë Â÷¼ö¸¦ ¹Ì¸® ¾Ë ¼ö ÀÖ´Ù¸é Á¤Àû ¹è¿­·Îµµ ¼±¾ðÇÒ ¼ö ÀÖ´Ù. ÀÌ·± ³ëµåµéÀÌ ¼­·Î¸¦ °¡¸®Å´À¸·Î½á Æ®¸®¸¦ ±¸¼ºÇÑ´Ù.

ÀÚ½ÄÀÇ °³¼ö°¡ Á¤ÇØÁ® ÀÖÁö ¾Ê±â ¶§¹®¿¡ ³ëµåÀÇ Â÷¼ö¿¡ µû¶ó ¸µÅ©ÀÇ °³¼ö°¡ °¡º¯ÀûÀÌ´Ù. µ¿Àû ÇÒ´çÇؼ­ ¸¸µå´Â ³ëµåÀÇ ¸â¹ö°¡ ¶Ç µ¿Àû ÇÒ´çÀ» ÇÑ´Ù¸é °ü¸®Çϱ⠹«Ã´ ¹ø°Å·Ó°í ºÒÆíÇØÁø´Ù. ±×·¸´Ù°í Çؼ­ ÃÖ´ë Â÷¼ö¸¸Å­ÀÇ Á¤Àû ¹è¿­À» ÇÒ´çÇÏ¸é ¹Ì»ç¿ë ¸µÅ©°¡ ¸¹¾ÆÁ® ¸Þ¸ð¸®ÀÇ ³¶ºñ°¡ ½ÉÇϸç ÃÖ´ë Â÷¼ö ÀÌ»óÀº Ç¥ÇöÇÏÁö ¸øÇÏ´Â ÇÑ°è°¡ ÀÖ´Ù.

±×·¡¼­ ÀÓÀÇ Â÷¼ö¸¦ Áö¿øÇÏ´Â Æ®¸®´Â Àß »ç¿ëµÇÁö ¾ÊÀ¸¸ç Â÷¼öÀÇ ÃÖ´ë°ªÀ» ÀÏÁ¤ÇÑ Å©±â·Î Á¦ÇÑÇÑ´Ù. ÀÌÁø Æ®¸®(Binary Tree)´Â ¸ðµç ³ëµåÀÇ Â÷¼ö°¡ 2ÀÌÇÏÀÎ Æ®¸®ÀÌ¸ç ±¸Á¶°¡ ´Ü¼øÇϱ⠶§¹®¿¡ Çö½ÇÀûÀ¸·Î °¡Àå ¸¹ÀÌ »ç¿ëµÈ´Ù. ÀÌÁø Æ®¸®ÀÇ ³ëµå´Â ÀÚ½ÄÀ» ÃÖ´ë 2°³±îÁö¸¸ °¡Áú ¼ö ÀÖÀ¸¹Ç·Î ´ÙÀ½°ú °°Àº ±¸Á¶Ã¼·Î °£´ÜÇÏ°Ô Ç¥ÇöÇÒ ¼ö ÀÖ´Ù.

 

struct Node

{

     int data;

     Node *left;

     Node *right;

};

 

³ëµå¿¡ ÀúÀåµÇ´Â µ¥ÀÌÅÍ¿Í ÁÂ¿ì µÎ °³ÀÇ ¸µÅ©¸¦ °¡Áø´Ù. left°¡ ¿ÞÂÊ ÀÚ½ÄÀ» °¡¸®Å°¸ç right°¡ ¿À¸¥ÂÊ ÀÚ½ÄÀ» °¡¸®Å²´Ù. ¹°·Ð ¾çÂÊ ÀÚ½ÄÀÌ ¸ðµÎ Á¸ÀçÇÒ ÇÊ¿ä´Â ¾øÀ¸¸ç ÀÚ½ÄÀÌ ¾ø´Â ÀÙ ³ëµåÀÏ °æ¿ì ¸µÅ©´Â ¸ðµÎ NULL°ªÀ» °¡Áú °ÍÀÌ´Ù. ÀÌ·¸°Ô µÇ¸é ÇÑ ³ëµåÀÇ Á¿ì ÀÚ½Ä ³ëµå´Â ½±°Ô ¾Ë ¼ö Àִµ¥ ÀÌ ³ëµåÀÇ ºÎ¸ð´Â ¾Ë ¼ö ¾ø´Ù´Â ¹®Á¦Á¡ÀÌ ÀÖ´Ù. ¸¸¾à ºÎ¸ð ³ëµå±îÁöµµ ±â¾ïÇÏ°í ½Í´Ù¸é parent¶ó´Â Æ÷ÀÎÅ͸¦ Çϳª ´õ Ãß°¡ÇÏ¸é µÈ´Ù. ÀÌÁø Æ®¸®¿¡ Á» ´õ ¾ö°ÝÇÑ Á¦¾àÀ» °¡ÇÏ¸é ´ÙÀ½°ú °°Àº Æ®¸®¸¦ Á¤ÀÇÇÒ ¼ö ÀÖ´Ù.

 

Æ÷È­ ÀÌÁø Æ®¸®(Full Binary Tree) : Æ®¸®ÀÇ ³ôÀ̱îÁö ¸ðµç ³ëµå°¡ °¡µæÂù Æ®¸®ÀÌ´Ù. ³ôÀÌ°¡ 1ÀÌ¸é ·çÆ® Çϳª¸¸ ÀÖÀ¸¹Ç·Î ³ëµå °³¼ö´Â 1°³ÀÌ¸ç ³ôÀÌ°¡ 2ÀÌ¸é ·çÆ®¿Í ¾çÂÊ ÀÚ½ÄÀ» ÇÕÃÄ ¼¼ °³ÀÇ ³ëµå°¡ Á¸ÀçÇÑ´Ù. ³ôÀÌ°¡ 3À̸é 7°³, 4À̸é 15°³À̸ç ÀϹÝÀûÀ¸·Î ³ôÀÌ°¡ nÀÎ Æ÷È­ ÀÌÁø Æ®¸®ÀÇ ³ëµå °³¼ö´Â 2n-1°³ÀÌ´Ù.

¿ÏÀü ÀÌÁø Æ®¸®(Complelte Binary Tree) : Æ÷È­ ÀÌÁø Æ®¸®ÀÇ ³ëµå¸¦ Á¿¡¼­ ¿ì·Î, À§¿¡¼­ ¾Æ·¡·Î ¹øÈ£¸¦ ºÙ¿´À» ¶§ ¹øÈ£°¡ Å« µÚÂÊ ³ëµå¸¸ »ý·«µÈ Æ®¸®ÀÌ´Ù. °°Àº ³ôÀÌÀÇ Æ÷È­ ÀÌÁø Æ®¸®¿Í ´ëÀÀµÇ´Â ³ëµåÀÇ ¼ø¼­°ªÀÌ ÀÏÄ¡ÇÑ´Ù. ´ÙÀ½ ±×¸²À» ÅëÇØ µÎ ÀÌÁø Æ®¸®¸¦ ±¸ºÐÇØ º¸ÀÚ.

ù ¹ø° Æ®¸®ÀÇ ³ôÀÌ´Â 3Àε¥ ³ëµåÀÇ °³¼ö°¡ 7(23-1)°³À̹ǷΠÀÌ Æ®¸®´Â Æ÷È­ ÀÌÁø Æ®¸®ÀÌ´Ù. º¸´Ù½ÃÇÇ ºóÆ´¾øÀÌ ¸ðµç ³ëµå°¡ °¡µæ Â÷ ÀÖÀ¸¸ç ÀÙ ³ëµå¸¦ Á¦¿ÜÇÏ°í´Â ¸ðµÎ Â÷¼ö°¡ 2ÀÌ´Ù. Æ÷È­ ÀÌÁø Æ®¸®¿¡¼­ 7, 6, 5, 4¸¦ Â÷·Ê´ë·Î »ý·«ÇÒ ¶§ ÀÌ Æ®¸®¸¦ ¿ÏÀü ÀÌÁø Æ®¸®¶ó°í ÇÑ´Ù. ±×·¯³ª ¾Æ·¡ÂÊÀº ¼ø¼­°ªÀÌ ºü¸¥ ³ëµå°¡ ¸ÕÀú »ý·«µÇ¾î Æ÷È­ ÀÌÁø Æ®¸®ÀÇ ³ëµå ¼ø¼­°ª°ú °°Áö ¾ÊÀ¸¹Ç·Î ¿ÏÀü ÀÌÁø Æ®¸®´Â ¾Æ´Ï´Ù.

Á¤ÀÇ°¡ Á¶±Ý º¹ÀâÇÏÁö¸¸ ½±°Ô ¸»ÇÏÀÚ¸é Æ÷È­ ÀÌÁø Æ®¸®¿¡¼­ Áß°£¿¡ ºüÁø ³ëµå°¡ ¾ø´Â Æ®¸®¸¦ ¿ÏÀü ÀÌÁø Æ®¸®¶ó°í ÇÑ´Ù. ³ôÀÌ°¡ nÀÎ ¿ÏÀü ÀÌÁø Æ®¸®ÀÇ ³ëµå °³¼ö´Â 2n-1º¸´Ù Å©°Å³ª °°°í 2n-1º¸´Ù À۰ųª °°´Ù. Æ÷È­ ÀÌÁø Æ®¸®´Â ¹°·Ð ¿ÏÀü ÀÌÁø Æ®¸®ÀÇ ÀÏÁ¾ÀÌ´Ù.