๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

Binary Search Tree3

[Data Structure] AVL(Adelson-Velsky and Landis) ํŠธ๋ฆฌ๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์ €๋ฒˆ์— ์ •๋ฆฌํ–ˆ๋˜ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋ฅผ ๋” ์—…๊ทธ๋ ˆ์ด๋“œ(?)ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ธ AVL ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. (ํ˜น์‹œ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ๋Œ€ํ•ด ๋ชจ๋ฅด์‹œ๋Š” ๋ถ„๋“ค์€ ์—ฌ๊ธฐ ์—์„œ ๋ณด๊ณ  ์™€์ฃผ์„ธ์š”!) ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ AVL(Adelson-Velsky and Landis) ํŠธ๋ฆฌ๋ž€? ๐Ÿค” ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ AVL ํŠธ๋ฆฌ(๋ฐœ๋ช…์ž์˜ ์ด๋ฆ„์ธ Adelson-Velsky and Landis์—์„œ ๋”ฐ์˜จ ์ด๋ฆ„)๋Š” ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์ด๋‹ค. ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ค‘ ์ฒ˜์Œ์œผ๋กœ ๋ฐœ๋ช…๋˜์—ˆ๋‹ค. AVL ํŠธ๋ฆฌ์—์„œ, ๋‘ ์ž์‹ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด๋Š” ํ•ญ์ƒ ์ตœ๋Œ€ 1๋งŒํผ ์ฐจ์ด๋‚œ๋‹ค. ๋งŒ์•ฝ ์–ด๋–ค ์‹œ์ ์—์„œ ๋†’์ด ์ฐจ์ด๊ฐ€ 1๋ณด๋‹ค ์ปค์ง€๋ฉด ์ด ์†์„ฑ์„ ์œ ์ง€ํ•˜๊ธฐ ์œ„ํ•ด์„œ ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š”๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, .. 2021. 12. 1.
[Data Structure] ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree) ๊ตฌํ˜„ํ•ด๋ณด๊ธฐ (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์ €๋ฒˆ ์‹œ๊ฐ„์— ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๊ฐ€ ๋ญ”์ง€ ์ด๋ก ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์•˜๋Š”๋ฐ์š”. ์˜ค๋Š˜์€ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋ฅผ ์ง์ ‘ ๊ตฌํ˜„ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ BSTNode ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๋ฅผ ๋งŒ๋“ค์–ด ์ฃผ๊ฒ ์Šต๋‹ˆ๋‹ค. ๋…ธ๋“œ๋Š” ๊ฐ’,์™ผ์ชฝ,์˜ค๋ฅธ์ชฝ ์ž์‹์˜ ๋…ธ๋“œ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. class BSTNode { var value:T var leftChild:BSTNode? var rightChild:BSTNode? init(value:T) { self.value = value } } Binary Search Tree ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ตœ์ƒ๋‹จ ๊ฐ’์„ ๊ฐ€์งˆ root๋ฅผ ํ”„๋กœํผํ‹ฐ๋กœ ์ •์˜ํ–ˆ์Šต๋‹ˆ๋‹ค. struct BinarySearchTree { var root:BSTNode? Insert public mutatin.. 2021. 11. 18.
[Data Structure] ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree)๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ํšจ์œจ์ ์ธ ๊ฒ€์ƒ‰,์‚ฝ์ž…,์‚ญ์ œ๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)๋ž€? ๐Ÿค” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ์ด์ง„ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋จผ์ € ์ด์ง„ ํŠธ๋ฆฌ๊ฐ€ ๋ญ”์ง€์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ๋กœ, ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ๊ฐ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์™€ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ผ๊ณ  ํ•œ๋‹ค.... - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ๋…ธ๋“œ๋งˆ๋‹ค ์ž์‹์ด 2๊ฐœ ์ดํ•˜์ธ ํŠธ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ ์ด๋ฃจ์–ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. (์ž์‹์ด ์—†์–ด๋„ ๋˜๊ณ , ํ•˜๋‚˜์—ฌ๋„ ๋˜๊ณ , ๋‘ ๊ฐœ์—ฌ๋„ ๋ฉ๋‹ˆ๋‹ค.) ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree)๋ž€? ๐Ÿง ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์†.. 2021. 11. 17.
728x90
๋ฐ˜์‘ํ˜•