practivceAlgorithm/자료구조&알고리즘

[자료구조] 이진트리와 탐색. 파이썬의 bisect

findTheValue 2021. 7. 25. 00:00

이진트리??

최대 두개의 자식 노드를 가지는 트리형태의 자료구조.

단순 저장보다는 탐색혹은 정렬을 위함. 힙도 이진트리의 일종.

이진 탐색트리?

이진트리의 특수한 경우.
모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드보다 작거나 같으며 오른쪽 자식들의 값이 현재 노드의 값보다 크다는 조건을 만족하면 이진 탐색 트리가 된다(작은값은 왼쪽 큰값은 오른쪽에 저장.)
가장 처음 입력된 값이 root

클래스 정의, 초기화

노드 클래스 정의

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

이진 탐색 트리 클래스 정의

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

삽입 메서드, 탐색 메서드

class Node:
    def __init__(self, value):
        # double linked list
        self.value = value
        self.left = None
        self.right = None


class NodeMgmt:
    def __init__(self, head):
        self.head = head  # 루트노드

    # 삽입
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.left  # 비교대상을 바꾼다.
                else:
                    self.current_node.left = Node(value)  # 없다면 새로 만들어 연결시킨다.
                    break
            else:
                if self.current_node.right != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.right  # 비교대상을 바꾼다.
                else:
                    self.current_node.right = Node(value)
                    break

    # 이진 탐색 트리 출력
    def search(self, value):
        self.current_node = self.head

        while self.current_node:
            if self.current_node.value == value:  # 찾았다
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left  # 비교대상 바꾸기
            else:
                self.current_node = self.current_node.right  # 비교대상 바꾸기
        return False  # 다 찾아봤는데 없다.

# 실행
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)

print(BST.search(2))
print(BST.search(5))

4. 삭제 메서드

    def delete(self, value):
        # 삭제할 노드 탐색
        self.current_node = self.head  # 삭제할 노드
        self.parent = self.head  # 삭제할 노드의 부모 노드

        # 일단 해당 노드가 있는지를 찾는다
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.curent_node = self.current_node.left  # 비교대상 변경
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right  # 비교대상 변경

        if searched == False:  # 그런 값을 가진 노드가 없다 = 삭제할 노드가 없다
            return False


        ## 해당노드를 찾았다. 이제 삭제를 하자!
        # case1 왼쪽 삭제
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None


       # case2 오른쪽 삭제
        # 왼쪽 노드만 가지고 있다.
        elif self.current_node.left != None and self.current_node.right == None:
            # 삭제할 노드가 parent의 오른쪽에 있냐 왼쪽에 있냐
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        # 오른쪽 노드만 가지고 있다.
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right




        # case3 : 삭제할 노드가 두개의 자식을 가진다
        if self.current_node.left != None and self.current_node.right != None:

            # case3-1 : 삭제할 노드가 부모 노드의 왼쪽에 있다
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right

                # 가장 작은값은 무조건 left에 있다 = 일단 left 끝까지 가게
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                self.change_node = self.change_node.left

                # 3-1-2
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-1-1
                    self.change_node_parent.left = None

                # 위로 옮기기
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

삭제할 노드의 자식이 양쪽 다 있을 때는 오른쪽 서브트리의 가장 왼쪽 자식을 가져오면 된다

(왼쪽 서브트리보다 크면서 오른쪽 서브트리보다는 작은 중간값.)

트리 순회 알고리즘

깊이 우선 순회(DFT)

class BinarySearchTree(object):
    ...
    def pre_order_traversal(self):
        def _pre_order_traversal(root):
            if root is None:
                pass
            else:
                print(root.data)
                _pre_order_traversal(root.left)
                _pre_order_traversal(root.right)
        _pre_order_traversal(self.root)

뿌리 왼쪽 오른쪽 순서. 출력을 한다시면 출력을 먼저하고 왼쪽 진입, 오른쪽 진입 순서이다.

class BinarySearchTree(object):
    ...
    def in_order_traversal(self):
        def _in_order_traversal(root):
            if root is None:
                pass
            else:
                _in_order_traversal(root.left)
                print(root.data)
                _in_order_traversal(root.right)
        _in_order_traversal(self.root)

왼쪽 진입, 왼쪽 탐색이 다 끝나면 출력 후 오른쪽 진입.

class BinarySearchTree(object):
    ...
    def post_order_traversal(self):
        def _post_order_traversal(root):
            if root is None:
                pass
            else:
                _post_order_traversal(root.left)
                _post_order_traversal(root.right)
                print(root.data)
        _post_order_traversal(self.root)

왼쪽 ,오른쪽 다 탐색 끝나고 루트 출력(제일 마지막 순회가 루트노드이다.)

3. 후위 순회(Post-order traversal)
2. 정위 순회(In-order traversal)
1. 전위 순회(Pre-order traversal)

2. 너비 우선 순회(BFT)

1. 레벨 우선 순회.

class BinarySearchTree(object):
    ...
    def level_order_traversal(self):
        def _level_order_traversal(root):
            queue = [root]
            while queue:
                root = queue.pop(0)
                if root is not None:
                    print(root.data)
                    if root.left:
                        queue.append(root.left)
                    if root.right:
                        queue.append(root.right)
        _level_order_traversal(self.root)

맨위 노드부터 level순으로 방문탐색한다. 이어져있는 것과 상관없이 FIFO로 큐형태의 탐색.

=> DFS,BFS로 트리 탐색이 가능하며 트리는 순회구조(사이클)이 없기 때문에 구현시 이미 방문한 노드를 기억 할 필요없다.(visited x)

힙(Heap) 완전 이진트리의 일종

완전이진트리: 노드를 삽입할때 왼쪽 하단부터 차례로 삽입하는 트리.

배열-> min,max O(n)

Heap -> O(logn)

이진 탐색 트리는 탐색을 위한 구조, 힙은 최소, 최대의 검색을 위한 구조.

힙의 삽입 구조는 간단하다. 왼쪽 아래부터 채우고 부모와의 비교를 통해 하나씩 swap하는 형태.

루트를 삭제(pop)하면 가장 마지막에 삽입한 노드를 루트로 올리고 swap을 다시하는 방식.

루트 노드의 인덱스 번호0 혹은 1, 부모노드 인덱스 번호는 자식노드 인덱스 번호의//2 2로 나눈 몫

왼쪽자식은 부모의 *2 오른쪽은 *2+1

이를 통해 특정 노드의 인덱스를 알 수 있음.

이진 탐색(binary search)의 구현

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

재귀적 구현

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

파이썬의 이진 탐색 모듈 bisect

def bisect(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect(mylist, 3))

내장된 함수 로직.

def binary_search(array, target, start, end):
    while start<=end:
        mid = (start+end)//2 # 소수점 이하는 버림

        # 탐색성공
        if array[mid] == target: 
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid-1
        # 중간점 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid+1
    return None # 탐색이 끝났으나 찾지 못했다.

다른 로직

예시

import bisect
mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect.bisect(mylist, 3))

bisect는 정렬된 리스트 안에 3을 넣을 때 들어가는 인덱스를 리턴한다.(혹은 이미 있는 값의 인덱스를 리턴한다. logn속도.)

bisect_left는 해당 인자 왼쪽에 삽입. bisect_right는 오른쪽에 삽입.그냥 bisect도 마찬가지 오른쪽.

일반적인 탐색 예시.

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

bisect.insort, insort_left, insort_right는 삽입까지 한다.

저작자표시

'practivceAlgorithm > 자료구조&알고리즘' 카테고리의 다른 글

[자료구조] Segment Tree : 구간 연산 구간 변경 (0)	2021.08.03
[알고리즘] 비트마스크???!!! (0)	2021.07.29
[알고리즘] 최단거리탐색 다익스트라, 플로이드 워셜, 벨만포드, A* (0)	2021.07.23
[알고리즘] 에라토스테네스의 체. (0)	2021.07.21
[알고리즘] 정렬 (0)	2021.07.21

현재글[자료구조] 이진트리와 탐색. 파이썬의 bisect

JS, 파이썬, 2018, Python, http, kakao 2019, kakao 2018, React, 비트마스킹, 다익스트라, DP, codeforce 702, 백준, 비트마스크, TRIE, 슬라이딩 윈도우, BOJ, JS 30, dfs, 분할정복,

Today :
Yesterday :

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

one Book a Day

[자료구조] 이진트리와 탐색. 파이썬의 bisect

이진트리??

이진 탐색트리?

클래스 정의, 초기화

4. 삭제 메서드

트리 순회 알고리즘

2. 너비 우선 순회(BFT)

1. 레벨 우선 순회.

힙(Heap) 완전 이진트리의 일종

이진 탐색(binary search)의 구현

재귀적 구현

파이썬의 이진 탐색 모듈 bisect

bisect_left는 해당 인자 왼쪽에 삽입. bisect_right는 오른쪽에 삽입.그냥 bisect도 마찬가지 오른쪽.

bisect.insort, insort_left, insort_right는 삽입까지 한다.

'practivceAlgorithm > 자료구조&알고리즘' 카테고리의 다른 글

'practivceAlgorithm/자료구조&알고리즘'의 다른글

티스토리툴바

[자료구조] 이진트리와 탐색. 파이썬의 bisect

이진트리??

이진 탐색트리?

클래스 정의, 초기화

4. 삭제 메서드

트리 순회 알고리즘

2. 너비 우선 순회(BFT)

1. 레벨 우선 순회.

힙(Heap) 완전 이진트리의 일종

이진 탐색(binary search)의 구현

재귀적 구현

파이썬의 이진 탐색 모듈 bisect

bisect_left는 해당 인자 왼쪽에 삽입. bisect_right는 오른쪽에 삽입.그냥 bisect도 마찬가지 오른쪽.

bisect.insort, insort_left, insort_right는 삽입까지 한다.

'practivceAlgorithm > 자료구조&알고리즘' 카테고리의 다른 글

'practivceAlgorithm/자료구조&알고리즘'의 다른글

관련글

티스토리툴바