๋ฐ์ํ
๐ ์ด์ง ํธ๋ฆฌ (binary Search tree)
๐ต ์ด์ง ํ์ ํธ๋ฆฌ ํ์
๐บ ํด๋์ค ์ ์ ๋ฐ ์ด๊ธฐํ๋ ์์์ ๋ค๋ค๋ค.
์ด์ง ํ์ ํธ๋ฆฌ์ ์ฐพ๊ณ ์ํ๋ ๊ฐ์ด ์๋์ง๋ฅผ ํ์ธํ๋ ๊ฒ์ด๋ค. ๊ฐ์ด ์์ผ๋ฉด True, ์์ผ๋ฉด False๋ฅผ ๋ฐํํ๋ค.
๋งจ ์์ ์ด๋ฏธ์ง๋ฅผ ๋ณด๋ฉด ์ํ๋ ๊ฐ์ธ 27์ ์ฐพ๋ ๊ณผ์ ์ด๋ค.
- ๋จผ์ ์ต์์ ๋ ธ๋์ธ 21๊ณผ 27์ ๋น๊ตํ๋ค.
- 27์ด ๋ ธ๋๊ฐ๋ณด๋ค ํฌ๋ฏ๋ก ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํด์ ํ์ํ๋ค.
- ๋ค์ ๋ ธ๋๋ฅผ ๋ณด๋ฉด 28์ด๋ค. 27์ด ๋ ธ๋๊ฐ๋ณด๋ค ์์ผ๋ฏ๋ก ์ผ์ชฝ์ผ๋ก ์ด๋ํด์ ํ์ํ๋ค.
- ๋ค์์ 25์ด๋ค. 27์ด ๋ ธ๋๊ฐ๋ณด๋ค ํฌ๋ฏ๋ก ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ค.
- 27์ ์ฐพ์์ผ๋ฏ๋ก ํ์ ์ข ๋ฃ.
๊ทธ๋ฆผ ์๋์ ์ ๋ ฌ๋ ๋ฆฌ์คํธ์ ์์ฐจ์ ์ธ ํ์๊ณผ ๋น๊ตํด๋ณด๋ฉด ํจ์ฌ ๋น ๋ฅธ๊ฑธ ๋ณผ ์ ์๋ค.
๋ค์์ ํ์ ์ฝ๋ ์ด๋ค.
class Node:
def __init__(self, item):
class BinaryTree:
def __init__(self):
def add(self, item):
def __add_node(self, cur, item):
# ์ฐพ๊ธฐ!!
def search(self, item):
if self.head.val is None:
return False
else:
return self.__search_node(self.head, item)
def __search_node(self, cur, item):
print(cur.val, item)
if cur.val == item:
return True
else:
if cur.val >= item:
if cur.left is not None:
return self.__search_node(cur.left, item)
else:
return False
else:
if cur.right is not None:
return self.__search_node(cur.right, item)
else:
return False
๐ต ์ ์ฒด ์ฝ๋
# ๋
ธ๋ ๋ง๋ค๊ธฐ
# A(val)
# / \
# B(left) C(right)
class Node:
def __init__(self, item):
self.val = item
self.left = None
self.right = None
# ์ด์งํธ๋ฆฌ ๋ง๋ค๊ธฐ
class BinaryTree:
# ์ด๊ธฐ๊ฐ head๋ None
def __init__(self):
self.head = Node(None)
self.preorder_list=[]
self.inorder_list=[]
self.postorder_list=[]
# ๊ฐ ์ถ๊ฐํ๊ธฐ head๊ฐ ์์ ๊ฒฝ์ฐ
def add(self, item):
if self.head.val is None:
self.head.val = item
# head๊ฐ ์์ผ๋ฉด ์ผ์ชฝ๋ฐฐ์น or ์ค๋ฅธ์ชฝ๋ฐฐ์น
else:
self.__add_node(self.head, item)
# head๊ฐ ์๋ ๊ฒฝ์ฐ
def __add_node(self, cur, item):
print('๋ถ๋ชจ:', cur.val, '์์:', item)
# head ๊ฐ์ด ํฌ๋ฉด ์ผ์ชฝ์ผ๋ก
if cur.val >= item:
if cur.left is not None:
self.__add_node(cur.left, item)
else:
cur.left = Node(item)
# head ๊ฐ์ด ์์ผ๋ฉด ์ค๋ฅธ์ชฝ์ผ๋ก
else:
if cur.right is not None:
self.__add_node(cur.right, item)
else:
cur.right = Node(item)
# ์ฐพ๊ธฐ!!
def search(self, item):
if self.head.val is None:
return False
else:
return self.__search_node(self.head, item)
def __search_node(self, cur, item):
print(cur.val, item)
if cur.val == item:
return True
else:
if cur.val >= item:
if cur.left is not None:
return self.__search_node(cur.left, item)
else:
return False
else:
if cur.right is not None:
return self.__search_node(cur.right, item)
else:
return False
lst = [50, 30, 24, 5, 28, 45, 98, 52, 60]
bt = BinaryTree()
for num in lst:
bt.add(num)
print(bt.search(60))
๋ฐ์ํ
'CS > Data Structure' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์คํ(Stack) (0) | 2020.11.04 |
---|---|
[python] ์ด์ง ํ์ ํธ๋ฆฌ (binary Search tree) - 4. ์ญ์ (0) | 2020.09.05 |
[python] ์ด์ง ํ์ ํธ๋ฆฌ (binary Search tree) - 3. ์ํ (0) | 2020.09.04 |
[python] ์ด์ง ํ์ ํธ๋ฆฌ (binary Search tree) - 1. ํด๋์ค ์ ์, ์ด๊ธฐํ, ๋ ธ๋ ์ถ๊ฐ (0) | 2020.09.02 |
[python] ์ด์ง ํธ๋ฆฌ (binary tree) - ๊ฐ๋ ์ ๋ฆฌ (0) | 2020.09.01 |