二分木
出典: フリー百科事典『ウィã‚ペディア(Wikipedia)ã€
計算機科å¦ã§ã„ã†äºŒåˆ†æœ¨ï¼ˆbinary tree; 二進木ã€ãƒã‚¤ãƒŠãƒªãƒ¼ãƒ„リー)ã¯ã€ãƒ‡ãƒ¼ã‚¿æ§‹é€ ã®1ã¤ã§ã‚ã‚‹ã€‚æ ¹ä»˜ãæœ¨æ§‹é€ ã®ä¸ã§ã€ã‚るノード(節点 node)ãŒæŒã¤åã®æ•°ãŒé«˜ã€…2ã§ã‚ã‚‹ã‚‚ã®ã‚’ã„ã†ã€‚典型的ã«ã¯2ã¤ã®åã¯ãã‚Œãžã‚Œã€Œå·¦ã€ã€Œå³ã€ã¨å‘¼ã°ã‚Œã‚‹ã€‚二分探索法ã¨ãƒã‚¤ãƒŠãƒªãƒ’ープãŒä¸»ãªç”¨é€”ã§ã‚る。
以後ã€æ‹¬å¼§ã®ä¸ã¯è‹±èªžè¡¨è¨˜ã€‚
目次[éžè¡¨ç¤º] |
[編集] 用語
親ã‹ã‚‰åã¸æœ‰å‘線分(辺ã€ã‚¨ãƒƒã‚¸ edge)ãŒå¼•ã‹ã‚Œã‚‹ã€‚åã‚’æŒãŸãªã„ノードを葉(リーフ leaf)ãªã„ã—外部ノード (external node) ã¨å‘¼ã¶ã€‚葉ã§ãªã„ノードを内部ノード (internal node) ã¨å‘¼ã¶ã€‚ã‚るノードã®ã€Œæ·±ã•ã€(depth) ã¯ãƒ«ãƒ¼ãƒˆï¼ˆroot ã€Œæ ¹ã€ã«ã‚ãŸã‚‹ãƒŽãƒ¼ãƒ‰ï¼‰ã‹ã‚‰ãã®ãƒŽãƒ¼ãƒ‰ã¾ã§ã«è¾¿ã‚‹çµŒè·¯ï¼ˆãƒ‘ス path)ã®é•·ã•ï¼ˆçµŒè·¯ã®ç¨®é¡žã§ã¯ãªãã€ãƒŽãƒ¼ãƒ‰-ノードを1ã¨æ•°ãˆãŸæ•°ï¼‰ã§ã‚る。特定ã®ã€Œæ·±ã•ã€ã®ãƒŽãƒ¼ãƒ‰ã‚’ç·ç§°ã—ã¦æœ¨ã®ä¸ã§ã®ã€Œãƒ¬ãƒ™ãƒ«ã€(level) ã¨ç§°ã™ã‚‹ã“ã¨ãŒã‚る。ã‚るノードã®ã€Œé«˜ã•ã€ (height) ã¯ãã®ãƒŽãƒ¼ãƒ‰ã‹ã‚‰æœ€ã‚‚é ã„葉ã¾ã§ã®çµŒè·¯ã®é•·ã•ã§ã‚る。åŒã˜è¦ªã‚’æŒã¤ãƒŽãƒ¼ãƒ‰åŒå¿—を兄弟 (siblings) ã§ã‚ã‚‹ã¨å‘¼ã¶ã€‚ノードpã‹ã‚‰ãƒŽãƒ¼ãƒ‰qã¾ã§ã®çµŒè·¯ãŒã‚ã‚‹å ´åˆã€pã¯qã®ã€Œå…ˆç¥–ã€(ancestor)ã€qã¯pã®ã€Œåå«ã€(descendant) ã§ã‚る。ノードã®ã€Œå¤§ãã•ã€(size) ã¯ï¼ˆè‡ªåˆ†è‡ªèº«ã‚’å«ã‚“ã )ãã®ãƒŽãƒ¼ãƒ‰ã®åå«ã®æ•°ã§ã‚る。
[編集] 種類
二分木ã®ä¸ã§ã‚‚ã€å…¨ã¦ã®ãƒŽãƒ¼ãƒ‰ãŒã€Œè‘‰ã§ã‚ã‚‹ã‹ã€äºŒã¤ã®åã‚’æŒã£ã¦ã„る(次数ãŒ2ã§ã‚ã‚‹ã¨ã„ã†ï¼‰ã€ã‚‚ã®ã‚’ã€å…¨äºŒåˆ†æœ¨ (full binary tree) ã¨å‘¼ã¶ã€‚完全二分木 (perfect binary tree, complete binary tree) ã¯å…¨ã¦ã®è‘‰ãŒåŒã˜ã€Œæ·±ã•ã€ã‚’æŒã¤äºŒåˆ†æœ¨ã‚’指ã™ã€‚
Complete binary treeã«ã¯ä»–ã®å®šç¾©ã‚‚ã‚ã‚Šã€ã‚ã‚‹ n ã«ã¤ã„ã¦ã€å…¨ã¦ã®è‘‰ãŒ n ã¾ãŸã¯ n-1 ã®ã€Œæ·±ã•ã€ã‚’æŒã¡ã€å…¨ã¦ã®è‘‰ã‚’ã§ãã‚‹ã ã‘å·¦ã«å¯„ã›ãŸäºŒåˆ†æœ¨ã‚’指ã™ã“ã¨ã‚‚ã‚る。ã“ã®å ´åˆã€ä¸€ç•ªã€Œä¸‹ã€ã®ãƒ¬ãƒ™ãƒ«ã¯å·¦å´ã‹ã‚‰å…¨ã¦é€£ç¶šçš„ã«åŸ‹ã¾ã£ã¦ã„ãªã‘ã‚Œã°ãªã‚‰ãªã„。
「ã»ã¨ã‚“ã©å®Œå…¨ãªäºŒåˆ†æœ¨ã€(almost complete binary tree) ã¯å³ã§ã‚ã‚‹åãŒã„ã‚Œã°å¿…ãšå·¦ã§ã‚ã‚‹åãŒã„ã‚‹ãŒã€é€†ã¯å¿…ãšã—も真ã§ãªã„ã‚‚ã®ã‚’ã„ã†ã€‚
[編集] グラフç†è«–ã§ã®å®šç¾©
典型的ã«ã¯æ¬¡ã®ã‚ˆã†ãªå®šç¾©ãŒç”¨ã„られる。「二分木ã¯é€£çµã•ã‚ŒãŸ (connected) 閉路をもãŸãªã„ (acyclic) グラフã§ã€å„é ‚ç‚¹ (vertex) ã®æ¬¡æ•° (degree) (å„é ‚ç‚¹ã«å‡ºå…¥ã‚Šã™ã‚‹è¾ºã®æ•°ï¼‰ãŒ3を超ãˆãªã„ã‚‚ã®ã€‚ã€ã€€æ¬¡ã®ã“ã¨ãŒè¨¼æ˜Žå¯èƒ½ã§ã‚る。ã„ã‹ãªã‚‹äºŒåˆ†æœ¨ã§ã‚‚ã€æ¬¡æ•°1ã®ãƒŽãƒ¼ãƒ‰ã®æ•°ï¼ˆè‘‰ã«ã‚ãŸã‚‹ï¼‰ã¯æ¬¡æ•°3ã§ã‚るノードã®æ•°ã‚ˆã‚Šã¡ã‚‡ã†ã©2ã ã‘多ãã€æ¬¡æ•°2ã§ã‚るノードã¯ã„ã‹ãªã‚‹æ•°ã«ã‚‚ãªã‚Šã†ã‚‹ã€‚æ ¹ä»˜ã二分木ã¯ã€ã€Œæ ¹ã«ã‚ãŸã‚‹é ‚点ãŒä¸€ã¤ã ã‘決ã‚られã¦ãŠã‚Šã€ãã®é ‚点ã®æ¬¡æ•°ãŒ2を超ãˆãªã„ã‚‚ã®ã€ã‚’ã„ã†ã€‚
ãã®ã‚ˆã†ãªæ ¹ã‚’一ã¤é¸ã¶ã¨ã€å…¨ã¦ã®é ‚点ãŒå„々ユニークãªè¦ªã¨2ã¤ä»¥ä¸‹ã®åã‚’æŒã¤ã“ã¨ã«ãªã‚‹ã€‚ã ãŒã“ã‚Œã ã‘ã§ã¯åä¾›ã®å·¦å³ã‚’決ã‚ã‚‹ã“ã¨ãŒã§ããªã„。連çµæ¡ä»¶ã‚’ã¯ãšã—ãŸã‚‚ã®ï¼ˆé–‰è·¯ã‚’ã‚‚ãŸãªã„ç„¡å‘グラフ)を森 (forest) ã¨å‘¼ã¶ã€‚森ã¯æœ¨ã¨ç•°ãªã‚Šã€äº’ã„ã«é€£çµã—ã¦ã„ã‚‹è¦ç´ ãŒè¤‡æ•°ã‚ã£ã¦ã‚‚よã„。
ã‚‚ã†ä¸€ã¤ã®å®šç¾©ã¯æœ‰å‘グラフ上ã§ã®å†å¸°çš„定義ã§ã‚る。二分木ã¯æ¬¡ã®ã„ãšã‚Œã‹ã‚’指ã™:
- å˜ä¸€ã®é ‚点
- 二ã¤ã®äºŒåˆ†æœ¨ a, b ã¨ä¸€ã¤ã®é ‚点vを用æ„ã—ã€é ‚点vã‹ã‚‰äºŒã¤ã®äºŒåˆ†æœ¨a, bãã‚Œãžã‚Œã®æ ¹ã«å¯¾ã—ã¦è¾ºã‚’引ã„ãŸã‚‚ã®ã€‚
ã“ã®å®šç¾©ã§ã¯å·¦å³ã¯æ±ºã¾ã‚‰ãªã„ãŒã€å”¯ä¸€ã®æ ¹ã‚’決定ã™ã‚‹ã“ã¨ã¯ã§ãる。
[編集] データã®äºŒåˆ†æœ¨ã¸ã®æ ¼ç´æ³•
二分木ã¯ãƒ—ãƒã‚°ãƒ©ãƒŸãƒ³ã‚°è¨€èªžã®åŸºæœ¬çš„ãªè¦ç´ を用ã„ã¦æ§‹ç¯‰ã™ã‚‹ã“ã¨ãŒã§ãる。データ型ã¨ã—ã¦ãƒ¬ã‚³ãƒ¼ãƒ‰åž‹ã¨ãƒã‚¤ãƒ³ã‚¿åž‹ï¼ˆå‚照型)をもã£ãŸãƒ—ãƒã‚°ãƒ©ãƒŸãƒ³ã‚°è¨€èªžã§ã¯ã€å…¸åž‹çš„ãªæ–¹æ³•ã§ã¯ã€ä½•ã‚‰ã‹ã®ãƒ‡ãƒ¼ã‚¿ã¨å·¦å³ã®åã¸ã®ãƒã‚¤ãƒ³ã‚¿ã‹ã‚‰ãªã‚‹ãƒŽãƒ¼ãƒ‰ã‚’組ã¿åˆã‚ã›ã¦æœ¨ã‚’構æˆã™ã‚‹ã€‚å ´åˆã«ã‚ˆã£ã¦ã¯è¦ªã¸ã®ãƒã‚¤ãƒ³ã‚¿ã‚’用æ„ã™ã‚‹ã“ã¨ã‚‚ã‚る。å‚ç…§ã™ã‚‹ç›¸æ‰‹ãŒãªã„(左å³ã©ã¡ã‚‰ã‹ã‚ã‚‹ã„ã¯ä¸¡æ–¹ã®åãŒãªã„ï¼‰å ´åˆã¯ã€ã€Œä½•ã‚‚å‚ç…§ã—ã¦ã„ãªã„ã€ã“ã¨ã‚’示ã™ç‰¹åˆ¥ãªå€¤ nil ã«ã—ã¦ãŠãã‹ã€äº‹å‰ã«æ±ºã‚ãŸã‚るノード(番兵ã¨å‘¼ã¶ï¼‰ã‚’指ã™ã‚ˆã†ã«ã™ã‚‹ã€‚親ã¸ã®å‚照付ãã®ãƒ‡ãƒ¼ã‚¿æ§‹ç¯‰ä¾‹ã‚’Pascalã«ã‚ˆã£ã¦ç¤ºã™ã€‚
type pNode = ^Node; {ノード型ã¸ã®ãƒã‚¤ãƒ³ã‚¿} Node = record data : (* å¿…è¦ãªãƒ‡ãƒ¼ã‚¿ã‚’ãŸã‚る部分 *) left, parent, right : pNode {å·¦ã®åã€è¦ªã€å³ã®åã¸ã®ãƒã‚¤ãƒ³ã‚¿} end; ... var root, newnode : pNode; ... begin new(root); root^.parent := nil; {æ ¹ã‚’æ¤ãˆã‚‹ã€‚æ ¹ã«ã¯è¦ªãŒã„ãªã„} new(newnode); {æ–°ã—ã„ノードをã¤ãã‚‹} with newnode^ do begin left := nil; right := nil; {åã¯ã„ãªã„} parent := root {rootãŒè¦ª} end; root^.left := newnode; {å·¦å´ã®åã«} new(newnode); {æ–°ã—ã„ノードをã¤ãã‚‹} with newnode^ do begin left := nil; right := nil; {åã¯ã„ãªã„} parent := root {rootãŒè¦ª} end; root^.right := newnode {å³å´ã®åã«} ...
明示的ãªæ–¹æ³•ã§ã¯ãªã„ãŒã€é…列ã«äºŒåˆ†æœ¨ã‚’æ ¼ç´ã™ã‚‹æ–¹æ³•ã‚‚ã‚る。完全二分木ãªã‚‰ã°ã€ã“ã®æ–¹æ³•ã§ã‚‚スペースを無駄ã«ã™ã‚‹ã“ã¨ã¯ãªã„ã€‚æ ¹ã®æ·»å—ã‚’0ã¨ã™ã‚‹ã¨ã€ã“ã®å ´åˆã€æ·»å— i ã®ãƒŽãƒ¼ãƒ‰ã®åã¯æ·»å— 2i + 1 㨠2i + 2 ã«æ ¼ç´ã•ã‚Œã€ãã®ãƒŽãƒ¼ãƒ‰è‡ªä½“ã®è¦ªã¯ï¼ˆã‚ã‚Œã°ï¼‰æ·»å— floor((i-1)/2) ã«ã‚る。é…列を用ã„ã‚‹ã¨è¨˜æ†¶å®¹é‡ã®ç¯€ç´„ã«ãªã‚Šã€è¡ŒããŒã‘é †ï¼ˆå…ˆè¡Œé †ã€preorder traversal)ã§ãƒ‡ãƒ¼ã‚¿ã‚’èˆã‚ã‚‹å ´åˆç‰¹ã«å‚ç…§ã®å±€æ‰€æ€§ãŒå‘上ã™ã‚‹ã€‚ã—ã‹ã—ã€é€£ç¶šã—ãŸãƒ¡ãƒ¢ãƒªç©ºé–“ã‚’å¿…è¦ã¨ã—ã€æœ¨ãŒå¤§ãããªã‚‹éš›ã«å¤§ããªå‡¦ç†æ™‚é–“ã‚’å¿…è¦ã¨ã™ã‚‹ã€‚ã¾ãŸ n 個ã®ãƒŽãƒ¼ãƒ‰ã‚’æŒã¤é«˜ã• h ã®æœ¨ã«å¯¾ã—ã€2h - n ã«æ¯”例ã—ãŸãƒ¡ãƒ¢ãƒªã‚’消費ã™ã‚‹ã€‚
MLã®ã‚ˆã†ãªã‚¿ã‚°ä»˜ã共有体を備ãˆãŸè¨€èªžã§ã¯ã€ã—ã°ã—ã°ã‚¿ã‚°ä»˜ã共有体ã¨ã—ã¦äºŒåˆ†æœ¨ã¯æ§‹ç¯‰ã•ã‚Œã‚‹ã€‚ãã‚Œã«ã¯äºŒç¨®é¡žã®ãƒŽãƒ¼ãƒ‰ãŒç”¨ã„られã€ä¸€ã¤ã¯ãƒ‡ãƒ¼ã‚¿ã€å·¦ã®åã€å³ã®åã‚’æŒã£ãŸ3-tupleã®ãƒŽãƒ¼ãƒ‰ã§ã€ã‚‚ã†ä¸€ã¤ã¯ãƒ‡ãƒ¼ã‚¿ã‚‚関数ももãŸãªã„「葉ã€ã§ã‚る(上記Pascalã‚„Cã®ã‚ˆã†ãªãƒã‚¤ãƒ³ã‚¿åž‹ã‚’ã‚‚ã£ãŸè¨€èªžã® nil ã«å½“ãŸã‚‹ï¼‰
[編集] 二分木をèˆã‚る方法
ã—ã°ã—ã°ã€ã‚る二分木ã«å±žã™ã‚‹å„々ã®ãƒŽãƒ¼ãƒ‰ã‚’調ã¹ã‚‹å¿…è¦ãŒå‡ºã¦ãã‚‹ã€‚ãƒŽãƒ¼ãƒ‰ã‚’è¨ªã‚Œã‚‹é †ç•ªã«ã¯å®šç•ªçš„ãªã‚‚ã®ãŒã‚ã‚Šã€ãã‚Œãžã‚Œåˆ©ç‚¹ãŒã‚る。
[編集] è¡ŒããŒã‘é †ã€é€šã‚ŠãŒã‘é †ã€å¸°ã‚ŠãŒã‘é †æŽ¢ç´¢
二分木ã«ãŠã„ã¦ã¯ã‚るノードã¨ãã®åå«ã‚‚ã¾ãŸäºŒåˆ†æœ¨ã‚’構æˆã™ã‚‹ã€‚ã“れを部分木ã¨å‘¼ã¶ã€‚ 従ã£ã¦äºŒåˆ†æœ¨ã‚’部分木ã«åˆ†ã‘ã€å†å¸°ã‚’用ã„ã¦æŽ¢ç´¢ã™ã‚‹æ–¹æ³•ã¯è‡ªç„¶ã§ã‚ã‚‹ã€‚æ ¹ã‚’èª¿ã¹ã¦ã‹ã‚‰ãã‚Œã«ã¶ã‚‰ã•ãŒã‚‹éƒ¨åˆ†æœ¨ã‚’調ã¹ã‚‹ã®ãŒè¡ŒããŒã‘é † (preorder)ã€éƒ¨åˆ†æœ¨ã‚’調ã¹ã¦ã‹ã‚‰ãã®æ ¹ã‚’調ã¹ã‚‹ã®ãŒå¸°ã‚ŠãŒã‘é † (postorder) ã€ç‰‡æ–¹ã®éƒ¨åˆ†æœ¨ã‚’調ã¹ã€æ ¹ã‚’調ã¹ã€æ¬¡ã„ã§å対ã®éƒ¨åˆ†æœ¨ã‚’調ã¹ã‚‹ã®ãŒé€šã‚ŠãŒã‘é † (in-order) ã§ã‚る。二分探索木ã§ã¯é€šã‚ŠãŒã‘é †æŽ¢ç´¢ã¯ãƒŽãƒ¼ãƒ‰ã‚’大ãã•é †ï¼ˆã‚ã‚‹ã„ã¯å¤§ãã•ã®é€†é †ï¼‰ã«èª¿ã¹ã‚‹ã“ã¨ã«ãªã‚‹ã€‚
[編集] æ·±ã•å„ªå…ˆæŽ¢ç´¢
奥優先探索ã¨ã‚‚ã„ã†ã€‚æ ¹ã‹ã‚‰ã§ãã‚‹ã ã‘é ãã€ã—ã‹ã‚‚ã€æ—¢ã«èª¿ã¹ãŸãƒŽãƒ¼ãƒ‰ã®åã§ã‚るノードã‹ã‚‰èª¿ã¹ã¦ã„ã方法ã§ã‚る。一般ã®ã‚°ãƒ©ãƒ•ã¨ç•°ãªã‚Šã“ã‚Œã¾ã§ã«è¨ªã‚ŒãŸãƒŽãƒ¼ãƒ‰ã‚’å…¨ã¦è¨˜æ†¶ã—ã¦ãŠãå¿…è¦ã¯ãªã„。ã¨ã„ã†ã®ã‚‚木ã«ã¯é–‰è·¯ãŒãªã„ã‹ã‚‰ã§ã‚る。行ããŒã‘é †ã€é€šã‚ŠãŒã‘é †ã€å¸°ã‚ŠãŒã‘é †æŽ¢ç´¢ã¯ã™ã¹ã¦ã“ã‚Œã®ç‰¹æ®Šãªä¾‹ã§ã‚る。
[編集] 幅優先探索
æ·±ã•å„ªå…ˆæŽ¢ç´¢ã¨å¯¾ç…§çš„ã«ã€æœªã ã«è¨ªã‚Œã¦ã„ãªã„ノードをã€æ ¹ã«è¿‘ã„æ–¹ã‹ã‚‰æŽ¢ç´¢ã™ã‚‹ã€‚
[編集] 二分木ã®å¿œç”¨
[編集] 二分探索木
ノード毎ã«å€¤ãŒå‰²ã‚ŠæŒ¯ã‚‰ã‚Œã¦ã„ã‚‹ã¨ã™ã‚‹ã€‚ã‚るノードã®å·¦ã®åãŠã‚ˆã³ãã®å…¨ã¦ã®åå«ãƒŽãƒ¼ãƒ‰ã®æŒã¤å€¤ã¯ãã®ãƒŽãƒ¼ãƒ‰ã®å€¤ã‚ˆã‚Šå°ã•ãã€å³ã®ååŠã³ãã®å…¨ã¦ã®åå«ãƒŽãƒ¼ãƒ‰ã®æŒã¤å€¤ã¯ãã®ãƒŽãƒ¼ãƒ‰ã®å€¤ã‚ˆã‚Šå¤§ãããªã‚‹ã‚ˆã†ã«æ§‹æˆã—ãŸäºŒåˆ†æœ¨ã‚’二分探索木 (binary search tree) ã¨ã„ã†ã€‚二分探索木を通りãŒã‘é †ã«æŽ¢ç´¢ã™ã‚‹ã¨ã€å„ノードã®å€¤ã‚’大ãã•é †ï¼ˆã‚ã‚‹ã„ã¯é€†é †ï¼‰ã«å¾—ã‚‹ã“ã¨ãŒã§ãる。
ã“ã®ã‚ˆã†ãªæœ¨ã‚’用ã„ã‚‹ã¨äºŒåˆ†æŽ¢ç´¢ã¯å®¹æ˜“ã«ãªã‚‹ã€‚目的ã¨ã™ã‚‹å€¤ã‚’ x ã¨ã™ã‚‹ã¨ã€æ ¹ã‹ã‚‰å§‹ã‚ã¦ã€
- ノードã®å€¤ n を調ã¹ã‚‹
- x = n → ã‚ãŸã‚Š
- x < n → å·¦ã®éƒ¨åˆ†æœ¨ã‚’åŒæ§˜ã«èª¿ã¹ã‚‹
- x > n → å³ã®éƒ¨åˆ†æœ¨ã‚’åŒæ§˜ã«èª¿ã¹ã‚‹
ã¨ã„ã†å†å¸°çš„コーディングãŒå¯èƒ½ã§ã‚る。
二分探索木ã®æ¤œç´¢åŠ¹çŽ‡ãŒæœ€é«˜ã«ãªã‚‹ã®ã¯ã€æœ¨ã®é«˜ã•ãŒæœ€ä½Žãªæ™‚ã§ã€å³ã¡æ ¹ã‹ã‚‰å„葉ã¾ã§ã®é«˜ã•ãŒã§ãã‚‹ã ã‘ç‰ã—ããªã£ãŸå ´åˆã§ã‚る。ãã®ã‚ˆã†ãªäºŒåˆ†æœ¨ã‚’平衡木 (balanced tree) ã¨å‘¼ã¶ã€‚詳細ã¯2分探索木ã€AVL木をå‚ç…§ã•ã‚ŒãŸã„。
[編集] ãƒã‚¤ãƒŠãƒªãƒ’ープ
åŠé †åºé›†åˆã‚’二分木ã§è¡¨ç¾ã—ãŸã‚‚ã®ã§ã‚る。親åã®é–“ã§ã€å‰²ã‚Šå½“ã¦ã‚‰ã‚ŒãŸå€¤ã«ã¤ã„㦠親 ≤ åã€ãªã„ã—㯠親 ≥ åã®é–¢ä¿‚ãŒå¿…ãšæˆç«‹ã™ã‚‹ã‚‚ã®ã‚’ã„ã†ã€‚å‰è€…ã®å ´åˆæ ¹ãŒæœ€å°ã®å€¤ã€å¾Œè€…ã®å ´åˆã€æ ¹ãŒæœ€å¤§ã®å€¤ã‚’ã‚‚ã¤ã“ã¨ã«ãªã‚‹ã€‚詳細ã¯ãƒ’ープをå‚ç…§ã•ã‚ŒãŸã„。
[編集] ç®—è¡“å¼ã®æ§‹æ–‡æœ¨
図ã®ä¾‹ã§ã¯ã€äºŒé …演算åを用ã„ãŸç®—è¡“å¼ã‚’二分木ã§è¡¨ç¾ã—ã¦ã„る。ã“ã®å¼ã‚’逆ãƒãƒ¼ãƒ©ãƒ³ãƒ‰è¨˜æ³•ã€ä¸ç½®è¨˜æ³•ã€ãƒãƒ¼ãƒ©ãƒ³ãƒ‰è¨˜æ³•ã§è¨˜è¿°ã™ã‚‹ã¨ã€ãã‚Œãžã‚Œ
- a b + c d - × e f + ÷
- (a + b) × (c - d) ÷ (e + f)
- ÷ × + a b - c d + e f
ã¨ãªã‚Šã€å·¦å„ªå…ˆã®å¸°ã‚ŠãŒã‘é †ã€é€šã‚ŠãŒã‘é †ã€è¡ŒããŒã‘é †ã«ç›¸å½“ã™ã‚‹ã€‚強調部分ã¯å›³ã§ç‚¹ç·šã§å›²ã£ãŸéƒ¨åˆ†æœ¨ã§ã‚る。部分木ãŒäºŒåˆ†æœ¨ã§ã‚ã‚‹ã“ã¨ã¯ã€å¼ã®é …ã‚‚ã¾ãŸå¼ã§ã‚ã‚‹ã“ã¨ã¨ã‚ˆã対応ã™ã‚‹ã€‚
[編集] äºŒåˆ†æœ¨æ§‹é€ ã®ã‚¨ãƒ³ã‚³ãƒ¼ãƒ‡ã‚£ãƒ³ã‚°æ³•
[編集] Succinct encodings
Succinct data structure(succinctã¯ã€ŒæŽ§ãˆã‚ãªã€ã¨ã„ã£ãŸæ„味。控ãˆã‚ãªãƒ‡ãƒ¼ã‚¿æ§‹é€ )ã¯æƒ…å ±ç†è«–ã§æ±‚ã‚られる最å°ã®ãƒ‡ãƒ¼ã‚¿ç©ºé–“ã‚’ã®ã¿æ¶ˆè²»ã™ã‚‹ã‚‚ã®ã§ã‚る。n個ã®ãƒŽãƒ¼ãƒ‰ã‚’æŒã¤ç•°ãªã£ãŸäºŒåˆ†æœ¨ã®å€‹æ•°ã¯Cnã€å³ã¡n番目ã®ã‚«ã‚¿ãƒ©ãƒ³æ•°ã§ã‚ã‚‹ï¼ˆæ§‹é€ ãŒåŒã˜æœ¨ã¯åŒä¸€ã®ã‚‚ã®ã¨è¦‹ãªã™ï¼‰ã€‚nãŒå分大ãããªã‚‹ã¨ã€ã“ã‚Œã¯4n程度ã«ãªã‚‹ã€‚従ã£ã¦ã€ãれらをエンコードã™ã‚‹ã«ã¯å°‘ãªãã¨ã‚‚log24n = 2n bit 程度ãŒå¿…è¦ã¨ãªã‚‹ã€‚よã£ã¦ã€Succinct二分木ã¯ãƒŽãƒ¼ãƒ‰ã‚ãŸã‚Š 2bit ã ã‘を消費ã™ã‚‹ã‚‚ã®ã§ãªã‘ã‚Œã°ãªã‚‰ãªã„。
ã“ã®æ¡ä»¶ã‚’満ãŸã™ç°¡å˜ãªè¡¨ç¾æ³•ã¯ã€è¡ŒããŒã‘é †ã«ãƒŽãƒ¼ãƒ‰ã‚’èˆã‚ã€å†…部ノードãªã‚‰1ã€è‘‰ãªã‚‰0を出力ã™ã‚‹æ–¹æ³•ã§ã‚る(ã“ã“ã§ã€Œè‘‰ã€ã¯ãƒ‡ãƒ¼ã‚¿ã‚’å«ã¾ãªã„ã‚‚ã®ã‚’指ã™ï¼‰ã€‚木ã«ãƒ‡ãƒ¼ã‚¿ãŒå«ã¾ã‚Œã‚‹ãªã‚‰ï¼ˆä¾‹ãˆã°å‰è¨˜ã®Pascalã®ä¾‹ã§ã€dataフィールドã®ä¸èº«ãŒç©ºã§ãªã„ãªã‚‰ï¼‰ã€ãれらを次々ã«é…列ã®ä¸ã«æ ¼ç´ã—ã¦ã„ã‘ã°ã„ã„。[1] 次ã®ã‚ˆã†ãªé–¢æ•°ã‚’用ã„ã‚‹:
function EncodeSuccinct(node n, bitstring structure, array data) { ã‚‚ã— n = nil ãªã‚‰ã° structure ã®æœ€å¾Œã« 0 ã‚’è¿½åŠ ã™ã‚‹ ãã†ã§ãªã‘れ㰠structure ã®æœ€å¾Œã« 1 ã‚’è¿½åŠ ã™ã‚‹ data ã®æœ€å¾Œã« n.data ã‚’è¿½åŠ ã™ã‚‹ EncodeSuccinct(n.left, structure, data) EncodeSuccinct(n.right, structure, data) }
string型データ structure ã¯æœ€çµ‚çš„ã« 2n + 1 bit ã«ãªã‚‹ã«ã™ãŽãªã„。ã“ã“㧠n ã¯å†…部ノードã®æ•°ã§ã‚る。structure型データã®é•·ã•ã™ã‚‰è¨˜éŒ²ã™ã‚‹å¿…è¦ãŒãªã„。次ã®é–¢æ•°ã‚’実行ã™ã‚Œã°ã€æƒ…å ±ãŒå…¨ã失ã‚ã‚Œã¦ã„ãªã„ã“ã¨ãŒã‚ã‹ã‚‹ã ã‚ã†ã€‚ã“ã‚Œã¯string型データã‹ã‚‰äºŒåˆ†æœ¨ã‚’å†æ§‹ç¯‰ã™ã‚‹:
function DecodeSuccinct(bitstring structure, array data) { structure ã®æœ€åˆã®ãƒ“ットをå–り除ãã€ãã®ãƒ“ットを b ã«å…¥ã‚Œã‚‹ ã‚‚ã— b ㌠1 ãªã‚‰ æ–°ã—ã„ノード n を作る dataã®æœ€åˆã®è¦ç´ ã‚’å–り除ãã€ãã®è¦ç´ ã‚’ n.data ã«å…¥ã‚Œã‚‹ n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data) n を返㙠ãã†ã§ãªã‘れ㰠nil を返㙠}
æ›´ã«æ´—ç·´ã•ã‚ŒãŸæ–¹æ³•ã‚’用ã„ã‚‹ã¨ã€æœ¨æ§‹é€ をコンパクトã«è¡¨ç¾ã§ãã‚‹ã ã‘ã§ãªãã€succinctã•ã‚’ä¿ã£ãŸã¾ã¾æ¼”ç®—æ“作もã§ã便利ã§ã‚る。
[編集] N進木ã®äºŒåˆ†æœ¨è¡¨ç¾
一般ã«é †åºã®ã‚る木 (ordered tree) ã¨äºŒåˆ†æœ¨ã¨ã®é–“ã«ä¸€å¯¾ä¸€å¯¾å¿œé–¢ä¿‚ã‚’ã¤ã‘ã‚‹ã“ã¨ãŒã§ãる。ã“ã‚Œã¯LISP言語ã§ç‰¹ã«ç”¨ã„られるもã®ã§ã‚ã‚‹ã€‚é †åºæœ¨ã®ä¸ã®ä»»æ„ã®ãƒŽãƒ¼ãƒ‰Nを二分木ã®ãƒŽãƒ¼ãƒ‰nã¨å¯¾å¿œã•ã›ã‚‹ã€‚nã®å·¦ã®åã¯Nã®æœ€åˆã®åã§ã‚る。Nã®æ¬¡ã®åã¯nã®å³ã®åmã€ãã®æ¬¡ã®Nã®åã¯mã®å·¦ã®åã€ãã®ã¾ãŸæ¬¡ã®Nã®åã¯mã®å³ã®åã€ã¨ã„ã£ãŸæ§˜ã«ã€æ¬¡ã€…ã«å³ã«æœ¨ã‚’生やã—ã¦ã„ã‘ã°ã„ã„。
別ã®è¦‹æ–¹ã‚’ã™ã‚Œã°ã€ã“ã‚Œã¯é †åºæœ¨ã®å„ノードã®å…„弟を次々ã«ã€Œå³ã€ãƒ•ã‚£ãƒ¼ãƒ«ãƒ‰ã‚’用ã„ã¦é€£çµã—ãŸä¸€ç¨®ã®é€£çµãƒªã‚¹ãƒˆæ§‹é€ ã«æ ¼ç´ã—ã€æœ€åˆã®è¦ç´ を「左ã€ãƒ•ã‚£ãƒ¼ãƒ«ãƒ‰ã«å…¥ã‚ŒãŸã®ã¨åŒã˜ã§ã‚る。
{B,C,D,E,F,G}ã®6ã¤ã®åã‚’æŒã¤A(左)を二分木(å³ï¼‰ã§è¡¨ç¾ã—ãŸä¾‹ã§ã‚る。
二分木ã¯ã‚ªãƒªã‚¸ãƒŠãƒ«ã®æœ¨ã‚’æ–œã«å‚¾ã‘ã¦è¡¨ç¾ã—ãŸã¨è€ƒãˆã‚‹ã“ã¨ã‚‚ã§ãる。左ã®é»’ã„辺ãŒã€Œæœ€åˆã®åã€ã€å³ã®é’ã„辺ãŒã€Œæ¬¡ã®å…„弟ã€ã‚’表ã™ã€‚å·¦ã®æœ¨ã«ã‚る葉ã¯LISPã§ã¯
- (((M N) H I) C D ((O) (P)) F (L))
ã®ã‚ˆã†ã«è¡¨ç¾ã•ã‚Œã‚‹ã ã‚ã†ã€‚ã“ã‚Œã¯è¨ˆç®—æ©Ÿã®ä¸ã§ã¯å³ã®ã‚ˆã†ã«å®Ÿè£…ã•ã‚Œã¦ã„ã‚‹ã¯ãšã§ã‚る。
[編集] å‚考文献
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp.318–348).