자료구조 Binary_Search_Tree

== Binary_Search_Tree(이진트리) ==

- 매우 중요하다!!

- Search, Delete, Insert : O(log n) - performance 좋다!! 

- 구현에 있으서 DP나 Recursion등을 물어볼 수 있기 때문에 이해하고 있어야 한다!! 

- Binary Search Tree

- The left sub-tree of a node has a key less than or equal to its parent node's key. - The right sub-tree of a node has a key greater than or equal to its parent node's key.

 

- Node

- node들이 연결된 것이 tree 이다!! 

Class Node: def __init__(self, item): self.val = item self.left = None self.right = None

- Add

def add(self, item): if self.head.val is None: self.head.val = item else: self.__add_node(self.head, item) def __add_node(self, cur, item): if cur.val >= item: if cur.left is not None: self.__add_node(cur.left, item) else: cur.left = Node(item) else: if cur.right is not None: self.__add_node(cur.right, item) else: cur.right = Node(item)

- Search

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): 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

- Remove(1/3) - node to be removed has no child

- 그냥 지우면 된다.

- Remove(2/3) - node to be removed has one child

- 지우고 자식을 할아버지 node에 연결시켜 주면 된다. 

- Remove(3/3) - node to be removed has two child

- 지우고 오른쪽 자식노드의 맨 왼쪽의 값으로 대체시켜 주면 된다.

---

-- Pre Order Traverse

1) Visit the root

2) Traverse the left subtree

3) Traverse the right subtree

def preorder_traverse(self): if self.head is not None: self.__preorder(self.head) def __preorder(self,cur): self.preorder_list.append(cur.val) print(cur.val) if cur.left is not None: self.__preorder(cur.left) if cur.right is not None: self.__preorder(cur.right)

- 왜 Preorder를 사용해야 하는지? 언제써야 하는지?

- 서버 여러개 놓고 사용을 할 때가 있지, 한 서버의 이 tree 구조를 다르 서버에 그대로 보내고 싶을 때, Preorder를 사용하게 된다. 

- 즉, 트리를 모양 그대로 다른 서버에 전송하고 싶을 때 byte stream으로 전송하고 싶을 때 preorder를 사용하게 된다. 

-- In Order Traverse 

1) Visit left

2) Visit parent

3) Visit right

def inorder_traverse(self): if self.head is not None: self.__inorder(self.head) def __inorder(self, cur): if cur.left is not None: self.__inorder(cur.left) self.inorder_list.append(cur.val) print(cur.val) if cur.right is not None: self.__inorder(cur.right)

- Inorder를 언제 쓰느냐?!

- 이 트리를 정렬해 보세요 할 때는, In order traverse를 활용하면 O(n)의 시간복잡도를 가지고, 정렬 할 수 있다!! 

-- Post Order Traverse

1) Visit left

2) Visit right

3) Visit root

def postorder_traverse(self): if self.head is not None: self.__postorder(self.head) def __postorder(self, cur): if cur.left is not None: self.__postorder(cur.left) if cur.right is not None: self.__postorder(cur.right) self.postorder_list.append(cur.val)

source-code : The-G

---

reference : 상상개발자