2021. 8. 29. 08:00ใ์ฝ๋ฉ ํ ์คํธ ์ค๋น/์๋ฃ๊ตฌ์กฐ
์๋ ํ์ธ์? ์ฃผ๋ํ๋ ์ ๋๋ค.
์ค๋์ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฃ๊ตฌ์กฐ์์ Tree ๊ตฌ์กฐ ๋๋ฒ์งธ ๊ณต๋ถ๋ฅผ ์์ ํด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค!
์์ค ์ฝ๋์ ๋ํด์ ํ์ธ ํ๊ณ ์ถ์ผ์ ๋ถ๋ค๊ป์๋ ์ฃผ๋ํ๋์ Git hub์ ๊ด์ฌ์ ์ฃผ์ธ์!
๋ณธ ํผ๋๋ [์๋ฃ๊ตฌ์กฐ] Tree ๊ตฌ์กฐ(1)์ ์ฐ์ฅ์ด๋ฉฐ, ํด๋น ํผ๋๋ฅผ ๋จผ์ ํ์ธํ์๊ณ , ์ด ํผ๋๋ฅผ ํ์ธํ์๋ ๊ฑธ ์ถ์ฒ ๋๋ฆด๊ฒ์!
๐ Binary Search Tree Node Delete (์ด์ง ํ์ ํธ๋ฆฌ ๋
ธ๋ ์ญ์ )
๐ Case 3-1
๐์ญ์ ํ Node๊ฐ Child Node๋ฅผ ๋ ๊ฐ ๊ฐ์ง๊ณ ์์ ๊ฒฝ์ฐ (์ญ์ ํ Node๊ฐ Parent Node ์ผ์ชฝ์ ์์ ๋)
- ๊ธฐ๋ณธ ์ฌ์ฉ ์ ๋ต
- ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ์ญ์ ํ Node์ Parent Node๊ฐ ๊ฐ๋ฅดํค๋๋ก ํ๋ค.
- ์ญ์ ํ Node์ ์ผ์ชฝ ์์ ์ค, ๊ฐ์ฅ ํฐ ๊ฐ์ ์ญ์ ํ Node์ Parent Node๊ฐ ๊ฐ๋ฆฌํค๋๋ก ํ๋ค.
- ๊ธฐ๋ณธ ์ฌ์ฉ ๊ฐ๋ฅ ์ ๋ต ์ค, 1๋ฒ ์ ๋ต์ ๊ฐ์ง๊ณ Code ๊ตฌํ
- ๊ทธ ์์ ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์
- Case 3-1-1 : ์ญ์ ํ Node๊ฐ Parent Node์ ์ผ์ชฝ์ ์๊ณ , ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ Child Node๊ฐ ์์ ๋
- Case 3-1-2: ์ญ์ ํ Node๊ฐ Parent Node์ ์ผ์ชฝ์ ์๊ณ , ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ ์ค๋ฅธ์ชฝ์ Child Node๊ฐ ์์ ๋
- ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ Child Node๊ฐ ์ผ์ชฝ์ ์์ ๊ฒฝ์ฐ๋ ์๋ค ์๋ํ๋ฉด ์ผ์ชฝ Node๊ฐ ์๋ค๋ ๊ฒ์ ํด๋น Node๋ณด๋ค ๋ ์์ ๊ฐ์ ๊ฐ์ง Node๊ฐ ์๋ค๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ
- ๊ทธ ์์ ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์
if self.current_node.lefe != None and self.current_node.right = None: # Case 3์ ๋ํ ๋ด์ฉ
if value < self.parent.value: # Case 3-1์ ๋ํ ๋ด์ฉ
self.change_node = self.current_node.right
self.change_node_parent = self.change_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None: # Case 3-1-1์ ๋ํ ๋ด์ฉ
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.current_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
๐ Case 3-2
๐์ญ์ ํ Node๊ฐ Child Node๋ฅผ ๋ ๊ฐ ๊ฐ์ง๊ณ ์์ ๊ฒฝ์ฐ (์ญ์ ํ Node๊ฐ Parent Node ์ค๋ฅธ์ชฝ์ ์์ ๋)
- ๊ธฐ๋ณธ ์ฌ์ฉ ์ ๋ต
- ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ์ญ์ ํ Node์ Parent Node๊ฐ ๊ฐ๋ฅดํค๋๋ก ํ๋ค.
- ์ญ์ ํ Node์ ์ผ์ชฝ ์์ ์ค, ๊ฐ์ฅ ํฐ ๊ฐ์ ์ญ์ ํ Node์ Parent Node๊ฐ ๊ฐ๋ฆฌํค๋๋ก ํ๋ค.
- ๊ธฐ๋ณธ ์ฌ์ฉ ๊ฐ๋ฅ ์ ๋ต ์ค, 1๋ฒ ์ ๋ต์ ๊ฐ์ง๊ณ Code ๊ตฌํ
- ๊ทธ ์์ ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์
- Case 3-2-1 : ์ญ์ ํ Node๊ฐ Parent Node์ ์ค๋ฅธ์ชฝ์ ์๊ณ , ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ Child Node๊ฐ ์์ ๋
- Case 3-2-2: ์ญ์ ํ Node๊ฐ Parent Node์ ์ค๋ฅธ์ชฝ์ ์๊ณ , ์ญ์ ํ Node์ ์ค๋ฅธ์ชฝ ์์ ์ค, ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ ์ค๋ฅธ์ชฝ์ Child Node๊ฐ ์์ ๋
- ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง Node์ Child Node๊ฐ ์ผ์ชฝ์ ์์ ๊ฒฝ์ฐ๋ ์๋ค ์๋ํ๋ฉด ์ผ์ชฝ Node๊ฐ ์๋ค๋ ๊ฒ์ ํด๋น Node๋ณด๋ค ๋ ์์ ๊ฐ์ ๊ฐ์ง Node๊ฐ ์๋ค๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ
- ๊ทธ ์์ ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
๐๐ปโ๏ธ ์ ์ฒด ์ฝ๋๋ ์ฃผ๋ํ๋ Git hub์์ ํ์ธํ ์ ์์ต๋๋ค.
์ฐธ๊ณ ํ๋ฉด ์ข์ ๊ณณ : http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html
๐ Python All Code Test
- Use the random Library
- random.randint(์ฒซ๋ฒ์งธ ์ซ์, ๋ง์ง๋ง ์ซ์): ์ฒซ๋ฒ์งธ ์ซ์๋ถํฐ ๋ง์ง๋ง ์ซ์ ์ฌ์ด ๊ฐ๋ค์ Randomํ๊ฒ ์ ํํ์ฌ ๋ฐํ
- ์: random.randint(0, 99) 0 ~ 99๊น์ง ์ซ์ ์ค ํน์ ์ซ์ Random ์ ํ ๋ฐํ
- random.randint(์ฒซ๋ฒ์งธ ์ซ์, ๋ง์ง๋ง ์ซ์): ์ฒซ๋ฒ์งธ ์ซ์๋ถํฐ ๋ง์ง๋ง ์ซ์ ์ฌ์ด ๊ฐ๋ค์ Randomํ๊ฒ ์ ํํ์ฌ ๋ฐํ
# 0 - 999 ์์ ์ค ์์๋ก 100๊ฐ๋ฅผ ์ถ์ถํ์ฌ ์ด์ง ํ์ ํธ๋ฆฌ์ ์
๋ ฅํ๊ณ , ๊ฒ์, ์ญ์ ํด ๋ณด๊ธฐ
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999)) # Randdom Library๋ฅผ ํ์ฉํ์ฌ 0 ~ 999๊น์ง ์ ์ ๋ง๋ค์ด ์ค๋ณต์ ์ธ์ ํ์ง ์๋ set ์งํฉ์ ๋ฃ๊ธฐ
# ์ ํ๋ 100๊ฐ์ ์ซ์๋ฅผ ์ด์ง ํ์ Tree์ ์
๋ ฅ, ์์๋ก Root Node๋ 500์ผ๋ก ๋ฃ๊ธฐ๋ก ํ๋ค.
head = Node(500)
binary_search_tree = NodeMgmt(head)
for num in bst_nums:
binary_search_tree.insert(num)
# ์
๋ ฅํ 100๊ฐ์ ์ซ์ ๊ฒ์ (๊ฒ์ ๊ธฐ๋ฅ ํ์ธ)
for num in bst_nums:
if binary_search_tree.search(num) == False:
print("๊ฒ์์ด ์คํจ ํ์์ต๋๋ค!", num)
else:
print("๊ฒ์์ ์ฑ๊ณต ํ์์ต๋๋ค!", num)
print("=" * 100)
# ์
๋ ฅํ 100๊ฐ์ ์ซ์ ์ค 50๊ฐ์ ์ซ์๋ฅผ Random ์ ํํ์ฌ ์ญ์
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 50:
delete_nums.add(bst_nums[random.randint(0, 99)])
# ์ ํํ 50๊ฐ์ ์ซ์๋ฅผ ์ญ์ (์ญ์ ๊ธฐ๋ฅ ํ์ธ)
for del_num in delete_nums:
if binary_search_tree.delete(del_num) == False:
print("์ญ์ ์คํจํ์์ต๋๋ค!", del_num)
else:
print("์ญ์ ์ฑ๊ณตํ์์ต๋๋ค!", del_num)
๐ ์ด์ง ํ์ ํธ๋ฆฌ์ ์๊ฐ ๋ณต์ก๋์ ๋จ์
๐ ์๊ฐ ๋ณต์ก๋(ํ์์)
- depth(ํธ๋ฆฌ์ ๊น์ด)๋ฅผ h๋ผ๊ณ ํ๊ธฐํ ๋, $O(h)$๋ก ๋ํ๋ผ ์ ์๋ค.
- n๊ฐ์ Node๋ฅผ ๊ฐ์ง๋ค๋ฉด, $h = log2n$์ ๊ฐ๊น๊ธฐ ๋๋ฌธ์, ์๊ฐ๋ณต์ก๋๋ $O(logn)$
- ์ฐธ๊ณ : ๋น
์ค ํ๊ธฐ๋ฒ์์ $logn$์์์ $log$์ ๋ฐ์ 10์ด ์๋๊ณ , 2์ด๋ค.
- ํ๋ฒ ์คํ์๋ง๋ค, 50%์ ์คํํ ํ์๋ฅผ ์ ๊ฑฐํ๋ค๋ ์๋ฏธ. ์ฆ, 50%์ ์คํ์๊ฐ์ ๋จ์ถํ ์ ์๋ค.
- ์ฐธ๊ณ : ๋น
์ค ํ๊ธฐ๋ฒ์์ $logn$์์์ $log$์ ๋ฐ์ 10์ด ์๋๊ณ , 2์ด๋ค.
๐ ์ด์ง ํ์ ํธ๋ฆฌ ๋จ์
์ด์ง ํ์ ํธ๋ฆฌ์ ํ๊ท ์๊ฐ ๋ณต์ก๋๋ $O(logn)$์ด์ง๋ง, ์ด๊ฒ์ ํธ๋ฆฌ๊ฐ ๊ท ํ์ด ์กํ ์์ ๋์ ์ด์ผ๊ธฐ์ธ ๊ฒ์ด์์.
์๋์ ๊ฐ์ด ์์ฃผ ์์๊ฒ ์ญ ๋ป์ด ๋๊ฐ๋ค๋ฉด ๊ทธ๊ฒ์ ๋ฐฐ์ด์ด๋, ๋งํฌ๋ ๋ฆฌ์คํธ์ ๋ค๋ฅผ๋ฐ๊ฐ ์์ด์ง๋ต๋๋ค!
์ด๋ฐ ๊ฒฝ์ฐ ์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ์๋ฃ๊ตฌ์กฐ๊ฐ ๋ฐ๋ก ์๋ ๊ฒ์ด์์!
๋ํ ์์ ๊ฐ์ด ๊ตฌ์ฑ์ด ๋๋ฉด ์๊ฐ ๋ณต์ก๋๋ $(O(n))$์ด ๋์ด ๋ฒ๋ฆฌ๋ ๊ฒ์ด์์.
์ฃผ๋ํ๋์ ๊ธ์ด ๋ง์์ ๋์
จ๋์? ๊ตฌ๋
๊ณผ ๊ณต๊ฐ! ๊ทธ๋ฆฌ๊ณ , ๋๊ธ์ ์ฃผ๋ํ๋์๊ฒ ๋ง์ ํ์ด ๋ฉ๋๋ค
'์ฝ๋ฉ ํ ์คํธ ์ค๋น > ์๋ฃ๊ตฌ์กฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] Heap (1) (0) | 2021.09.06 |
---|---|
[์๋ฃ๊ตฌ์กฐ] Tree ๊ตฌ์กฐ(1) (0) | 2021.08.29 |
[์๋ฃ๊ตฌ์กฐ] 05. Hash Table (0) | 2021.08.27 |
[์๋ฃ๊ตฌ์กฐ] 04. Linked List (0) | 2021.08.15 |
[์๋ฃ๊ตฌ์กฐ] 03. Stack (0) | 2021.08.10 |