20강 요약

이진트리의 탐색,삽입등을 구현해봄

20강 내용

탐색

lookup() : 특정 원소를 검색 (탐색)

class Node:
	def lookup(self,key,parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key,self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key,self)
            else:
                return None, None
        else:
            return self, parent
            
            
class BinSearchTree:
	def lookup(self,key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

최솟값과 최댓값

max() : 최대 키를 가지는 원소를 탐색

class Node:
	def max(self):
        if self.right:
            return self.right.max()
        else:
            return self
            
class BinSearchTree:
	def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

min() : 최소 키를 가지는 원소를 탐색

class Node:
	def min(self):
        if self.left:
            return self.left.min()
        else:
            return self

class BinSearchTree:
	def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

삽입

insert() : 트리에 주어진 데이터 원소를 추가

class Node:
	def insert(self,key,data):
        if key < self.key: #작을때
            if self.left: #왼쪽 서브트리가 존재
                self.left.insert(key,data) #왼쪽 서브트리로 이동
            else: #왼쪽 서브트리가 존재x
                node = Node(key,data) #노드 만들어
                self.left = node #왼쪽 자식연결
        elif key > self.key: #클때
            if self.right: #오른쪽 서브트리가 존재
                self.right.insert(key,data) #오른쪽 서브트리로 이동
            else: #오른쪽 서브트리가 존재x
                node = Node(key,data) #노드만들어
                self.right = node #오른쪽 자식연결
        else: #키 중복
            raise KeyError #에러
            
class BinSearchTree:
	def insert(self,key,data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)

문제

이진 탐색 트리의 원소 삽입 연산 구현

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if key < self.key: #작을때
            if self.left: #왼쪽 서브트리가 존재
                self.left.insert(key,data) #왼쪽 서브트리로 이동
            else: #왼쪽 서브트리가 존재x
                node = Node(key,data) #노드 만들어
                self.left = node #왼쪽 자식연결
        elif key > self.key: #클때
            if self.right: #오른쪽 서브트리가 존재
                self.right.insert(key,data) #오른쪽 서브트리로 이동
            else: #오른쪽 서브트리가 존재x
                node = Node(key,data) #노드만들어
                self.right = node #오른쪽 자식연결
        else: #키 중복
            raise KeyError #에러


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0

---

21강 요약

이진 탐색 트리에서 삭제,자식노드수 구하기를 구현해봄

21강 내용

자식 노드 수

간단히 좌,우 자식 노드 있는지, 있다면 +1씩 더함

class Node:
	def countChildren(self):
        count = 0
        if self.left: #좌
            count += 1
        if self.right: #우
            count += 1
        return count

삭제

remove() : 특정 원소를 트리로부터 삭제

class BinSearchTree:
	def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if parent.left == node:
                        parent.left = None
                    elif parent.right == node:
                        parent.right = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    child = node.left
                else:
                    child = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left == node:
                        parent.left = child
                    elif parent.right == node:
                        parent.right = child
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = child
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    parent = successor
                    successor = parent.left
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                

            return True

        else:
            return False

문제

이진 탐색 트리에서 노드의 삭제 연산 구현

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key)


    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            if nChildren == 0:
                if parent:
                    if parent.left == node:
                        parent.left = None
                    elif parent.right == node:
                        parent.right = None
                else:
                    self.root = None
            elif nChildren == 1:
                if node.left:
                    child = node.left
                else:
                    child = node.right
                if parent:
                    if parent.left == node:
                        parent.left = child
                    elif parent.right == node:
                        parent.right = child
                else:
                    self.root = child
            else:
                parent = node
                successor = node.righㅅ
                while successor.left:
                    parent = successor
                    successor = parent.left
                node.key = successor.key
                node.data = successor.data
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                
            return True

        else:
            return False


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0

---

Github

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/20%2C21%EA%B0%95/20%2C21%EA%B0%95.py