[DS] 이진 검색 트리 (Binary Search Tree)

이진 검색 트리의 특성

1. 각 노드는 킷 값을 하나씩 갖는다. 각 노드의 킷 값은 모두 다르다.
2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다.
3. 임의 노드의 킷 값은 자신의 왼쪽 아래에 있는 모든 노드의 킷 값보다 크고,

오른쪽 아래에 있는 모든 노드의 킷 값보다 작다.
* 검색 트리의 높이는 효율성에 큰 영향을 미친다.

1. 원소 검색

Search(tNode, x):
	if tNode == None or x == tNode.item:
		return tNode;
	elif x < tNode.item:
		return search(tNode.left, x);
	else:
		return search(tNode.right, x);

# 검색
    def search(self, x):
        return self.__searchItem(self.__root, x)
    def __searchItem(self, tNode, x):
        if tNode == None:
            return None
        elif x == tNode.item:
            return tNode 
        elif x < tNode.item:
            return self.__searchItem(tNode.left, x)  
        # 최종 리턴값은 x == tNode.item을 만족하는 tNode이어야 함!!
        else:
            return self.__searchItem(tNode.right, x)

2. 원소 삽입

root <--- insert(root, x)

insert(tNode, x):
	if tNode == None:
		tNode = TreeNode(x, None, None)
	elif x < tNode.item:
		tNode.left <--- insert(tNode.left, x)
	else:
		tNode.right <--- insert(tNode.right, x)
	return tNode;

# 삽입
    def insert(self, x):
        self.__root = self.__insertItem(self.__root, x)
    # 직접 리스트로 가서 삽입하는 것이기 때문에 리턴할 것이 아니라 root로 받아주어야 함
    def __insertItem(self, tNode, x):
        if tNode == None:
            tNode = TreeNode(x, None, None)
        elif x < tNode.item:
            tNode.left = self.__insertItem(tNode.left, x)
        else:
            tNode.right = self.__insertItem(tNode.right, x)
        return tNode

3. 원소 삭제

deleteItem 삭제할 노드의 위치를 탐색, 발견한 경우 tNode(=r) <--- deleteNode
deleteNode 삭제할 노드(r)의 자녀를 정리 후 리턴(r 자리에 리턴 값을 넣어 주면 이전의 부모는 사라지는 효과) 하거나 자기자신(r)을 정리후 리턴

# 삭제
    def delete(self, x):
        self.__root =  self.__deleteItem(self.__root, x)
    # 직접 리스트로 가서 삭제하는 것이기 때문에 리턴할 것이 아니라 root로 받아 주어야 함
    def __deleteItem(self, tNode, x):
        if tNode == None:
            return None
        elif x == tNode.item:
            tNode = self.__deleteNode(tNode)
        elif x < tNode.item:
            tNode.left = self.__deleteItem(tNode.left, x)
        else:
            tNode.right = self.__deleteItem(tNode.right, x)
        return tNode
    def __deleteNode(self, tNode):
        # 3가지 Case
        #   1. tNode가 자식이 하나도 없음
        #   2. tNode가 자식이 하나만 있음
        #   3. tNode가 자식이 둘 있음
        if (tNode.left == None) and (tNode.right == None):
            return None
        elif tNode.left == None:
            return tNode.right
        elif tNode.right == None:
            return tNode.left
        else:
            (rtnItem, rtnNode) = self.__deleteMinItem(tNode.right)
            tNode.item = rtnItem
            tNode.right = rtnNode
            return tNode 
    def __deleteMinItem(self, tNode):
        if tNode.left == None:
            return (tNode.item, tNode.right)
        else:
            (rtnItem, rtnNode) = self.__deleteMinItem(tNode.left)
            tNode.left = rtnNode
            return (rtnItem, tNode)

Case 1 : 자식이 없는 경우 -> None을 리턴

Case 2 : 자식노드가 1개인 경우 -> 자식 노드를 리턴

Case 3 : 자식 노드가 2개인 경우

r의 오른쪽 서브트리의 최소 원소 노드 s를 찾는다 deleteMinItem
s를 r 자리로 복사하고, s를 삭제한다.

이진 검색 트리의 구현

class TreeNode:
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right

class BinarySearchTree:
    def __init__(self):
        self.__root = None
    
    # 검색
    def search(self, x):
        return self.__searchItem(self.__root, x)
    def __searchItem(self, tNode, x):
        if tNode == None:
            return None
        elif x == tNode.item:
            return tNode 
        elif x < tNode.item:
            return self.__searchItem(tNode.left, x)  
        # 최종 리턴값은 x == tNode.item을 만족하는 tNode이어야 함!!
        else:
            return self.__searchItem(tNode.right, x)

    # 삽입
    def insert(self, x):
        self.__root = self.__insertItem(self.__root, x)
    # 직접 리스트로 가서 삽입하는 것이기 때문에 리턴할 것이 아니라 root로 받아주어야 함
    def __insertItem(self, tNode, x):
        if tNode == None:
            tNode = TreeNode(x, None, None)
        elif x < tNode.item:
            tNode.left = self.__insertItem(tNode.left, x)
        else:
            tNode.right = self.__insertItem(tNode.right, x)
        return tNode
    
    # 삭제
    def delete(self, x):
        self.__root =  self.__deleteItem(self.__root, x)
    # 직접 리스트로 가서 삭제하는 것이기 때문에 리턴할 것이 아니라 root로 받아 주어야 함
    def __deleteItem(self, tNode, x):
        if tNode == None:
            return None
        elif x == tNode.item:
            tNode = self.__deleteNode(tNode)
        elif x < tNode.item:
            tNode.left = self.__deleteItem(tNode.left, x)
        else:
            tNode.right = self.__deleteItem(tNode.right, x)
        return tNode
    def __deleteNode(self, tNode):
        # 3가지 Case
        #   1. tNode가 자식이 하나도 없음
        #   2. tNode가 자식이 하나만 있음
        #   3. tNode가 자식이 둘 있음
        if (tNode.left == None) and (tNode.right == None):
            return None
        elif tNode.left == None:
            return tNode.right
        elif tNode.right == None:
            return tNode.left
        else:
            (rtnItem, rtnNode) = self.__deleteMinItem(tNode.right)
            tNode.item = rtnItem
            tNode.right = rtnNode
            return tNode 
    def __deleteMinItem(self, tNode):
        if tNode.left == None:
            return (tNode.item, tNode.right)
        else:
            (rtnItem, rtnNode) = self.__deleteMinItem(tNode.left)
            tNode.left = rtnNode
            return (rtnItem, tNode)
        
    def isEmpty(self):
        return self.__root == None
    
    def clear(self):
        self.__root = None

티스토리툴바