Ordered Data Structures # WEEK 2 : Binary Search Trees (BST) - Find, Insert, Remove

이진 탐색트리는 정렬된 이진트리.

find 시, 정렬되어 있으므로 해당 노드보다 큰지 작은지 판단 후 좌우 이동.

insert 시, find와 같음. find가 반환하는 포인터를 바탕으로 삽입 위치 찾음.

remove, 보통은 연결 리스트의 제거 원리가 적용되지만, 자식이 2개일 경우 IOP 순회흐름에서 우선하는 것, 즉 왼쪽 트리의 가장 아래노드와 swap후 제거한다.

이런 원리를 바탕으로 이메일(key)로 개인정보(data)에 접근하는 딕셔너리 등을 만들 때 활용되기도 한다.

 

2.4 Binary Search Trees(이진탐색트리)

 

A binary search tree(BST) is an ordered binary tree capable of being used as a search structure.

 

BST Order Property

A binary tree is a BST if for every node in the tree:

• Nodes in the left subtree are less than itself.
• Nodes in the right subtree are greater than itself.

---

https://machineboy0.tistory.com/148

트리 (Tree Data Structure) 기초 , 이진트리와 이진탐색트리

---

Dictionary

A dictionary associates a key with data:

• Your login email  ➜ Your profile data
• Your phone number  ➜  Your phone record
• A website URL  ➜ The webpage
• Your street address  ➜  Your home

implement dictionary by BST

Key need to be unique identifier.

 

Dictionary ADT

find	FInds the data associated with a key in the dictionary
insert	Adds a key/data pair to the dictionary
remove	Removes a key from the dictionary
empty	Returns true if the dictionary is empty

 

want to be able to look up information about you given your phone number, when you log into website using your e-mail address, we want to make sure that email address, so find is going to take a key in and find the data associated with that key.

 

전화번호나 이메일이 나의 정보(data)에 관한 key가 된다.

 

BST-Based Dictionary

A BST used to implement a dictionary will store both a key and data at every node:

 

but we're always going to be looking up by key and returning the data.

at every point in time, you always have keys and you always have data

 

Example: Finding in a BST

start at the root at each level we determine if we move left or right until we find the node.

• 37 - 51 - 42 (오른쪽으로 갈지 왼쪽으로 갈지 결정하는 루트 노드에서 시작)
• 37- 19 - 4 - 11
• 17은 없음

we know that 17 is not in our dataset, we know this because we reached a leaf in the tree and we can't go any further to search deeper.

 

Once we've gone one path througth the tree following the rules every step of the way, if we reach the end and we haven't found the data, we know for a fact that data is not in our data sturcture even though we haven't searched the entire tree.

규칙에 따라 리프노드까지 탐색을 마쳤음에도 찾는 데이터가 없다면 전체 트리에서도 없다는 것을 의미

 

 

Runtime of BST::find

Worst-case outcome(결과) of find:

트리가 한 쪽으로만 쭉 뻗어있고, 트리에 존재하지 않는 노드를 찾으려고 할 때 높이만큼 탐색해야하니까 worst case

 

we're not looking through all of the data, this is not as bad as an array or a linked list where we have to travel over every single piece of data, here we only need to take one path through the tree.

 

So the very worst case is going to be visiting nodes proportional to the height of the tree. so, the very worst case is going to be visiting the longest path. O(height)

 

Insert into a BST

 

find location exact location that should be inserted at and insert.

The insert algorithm is trivial because we're able to use the fact the find algorithm returns a pointer by reference to the exact location where we need to insert at.

 

Remove from a BST

 

one child removing

 

we know exactly how to repair this becuase we've repaired a linked list instead of simply deleting everything at this pointer and setting it equal to null, we delete the node and repair it by moving this pointer to the one child. so in the case of a one child remove.

 

two child removing

• If I were to remove the root of the tree, what is the best candidate to be placed at the root of the tree?
  • best suited to be root position in a tree that wouldn't disturb anything else.
  • best node to replace 37 is going to be the node that is closest to 37, either less than it or greater than it.
• 20 is the best node in this left sub-tree to replcase 37.

In-Order Predecessor(IOP

quantify this to a algorithm.

 

The in-order predecessor is the previous node in an in-order traversal of a BST

순회 시, 선택 노드보다 우선하는 것들.

 

So, the in-order predecessor of a node is going to be an in-order traversal of a binary search tree such that we choose the element that appears immediately before the route.

 

선택노드보다 순회 시, 바로 우선하는 것을 선택함.

 

The IOP of a node will always be the right-most node in the node's left sub-tree.

 

세 가지 조건

• Zero children : simple, delete the node.
• One children: simple, works like a linked list.
• Two children
  • Find the IOP of the node to be removed
  • Swap with the IOP
  • Remove the node in it's new position