이진탐색트리

• 모든 노드는 유일한 키를 갖는다

• 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

• 오른쪽 서브트리의 키들은 루트의 키보다 크다.

• 왼쪽과 오른쪽의 서브트리도 이진탐색트리이다.

• BSTnode class - 생성자로 key 값과 value 값을 받아서 초기화 함

class bstnode:
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

• 이진 탐색트리 생성
• 탐색트리를 만들과 순환구조를 이용해서 최대 키 값을 찾는 함수인 findmax_bst를 만들고 최소 키값을 가지는함수인 findmin_bst를 만듦

def findmax_bst(node):
    if node != None:
        if node.right == None:
            return node
        else:
            return findmax_bst(node.right)

def findmin_bst(node):
    if node != None:
        if node.left == None:
            return node
        else:
            return findmin_bst(node.left)

• 반복문을 이용해서 만든 insert함수

def insert_bst_repeat(compareNode, newNode):

    while(True):

        if newNode.key < compareNode.key:
            if compareNode.left == None:
                compareNode.left = newNode
                return True

            else:
                compareNode = compareNode.left
                # return insert_bst(compareNode.left, newNode)
        elif newNode.key > compareNode.key:
            if compareNode.right == None:
                compareNode.right = newNode
                return True

            else:
                compareNode = compareNode.right
                # return insert_bst(compareNode.right, newNode)
        elif newNode.key == compareNode.key:
            return False

• 이진탬색 트리의 출력을 위해서 이진탐색 트리를 출력하는 함수를 만듦

def showBST(node):

    if node is not None:
        showBST(node.left)
        print(node.key,end='  ')
        showBST(node.right)

• 함수 호출해서 출력하는 부분

showBST(a)#초기에 만든 탐핵이진트리 출력
print()#공간 구문을 위해서 여백출력
newNode = bstnode(9,'H')#삽입을 위해서 노드를 생성
insert_bst_repeat(a,newNode)#반복문을 이용해서 삽입을 진행하는 함수 
showBST(a)#삽입을 진행한 후 탐색트리 다시 출력함.

• 실행결과

F 31
C 3
3 7 12 18 26 27 31
3 7 9 12 18 26 27 31
Process finished with exit code 0

from 자료구조.BSTrecursice.bstNode import bnode

a = bnode(8, 'A')
b = bnode(3, 'B')
c = bnode(1, 'C')
d = bnode(5, 'B')
e = bnode(4, 'E')
f = bnode(9, 'F')
g = bnode(11, 'G')
h = bnode(12, 'H')

list = [a, b, c, d, e, f, g, h]


def insert_bst(compareNode, newNode):
    if compareNode == None:
        return True
    if compareNode.key < newNode.key:
        if compareNode.right == None:
            compareNode.right = newNode
            return True
        else:
            return insert_bst(compareNode.right, newNode)
    elif compareNode.key > newNode.key:
        if compareNode.left == None:
            compareNode.left = newNode
            return True
        else:
            return insert_bst(compareNode.left, newNode)
    else:
        return False


def search_value_repeat(node, key):
    while node != None:
        if node.key < key:
            node = node.right
        elif node.key > key:
            node = node.left
        elif node.key == key:
            return node


def search_value(compareNode, key):
    if compareNode.key == key:
        return compareNode
    elif compareNode.key < key:
        return search_value(compareNode.right, key)
    else:
        return search_value(compareNode.left, key)


def show_bst(node):
    if node is not None:
        show_bst(node.left)
        print(node.key, end=" ")
        show_bst(node.right)


def delete_bst_case1(parent, node, root):  # 삭제가할 노드가 단말 노드라는 가정하에 진행

    if parent is None:  # 부모 노드가 없다는 것은 삭제할 단말노드가 root란 소리고 그러면 트리가 소멸한다.
        root = None
    else:
        if parent.left == node:  # 삭제할 노드가 부모 노드의 왼쪽 노드이먄 부모 노드의 왼쪽 링크를 삭제한다.
            # 근데 위에 비교연산을 설정한 적이 없는데 어케 되는건지 모르겠다.
            parent.left = None
        else:
            parent.right = None
    return root  # root의 변경이 일어날지도 몰라서 반환


def delete_bst_case2(parent, node, root):  # 삭제할 대상의 node가 자식이 있는데 왼쪽이나 오른쪽이나 하나만 가지는 경우

    if node.left is not None:  # 삭제할 노드가 왼쪽 자식만을 가지는 경우
        child = node.left  # 자기 자식의 왼쪽 노드를 child 변수에 담는다.
    else:
        child = node.right  # 삭제하려는 노드가 오른쪽 노드만을 가지는 경우에는 자신의 오른쪽 자식을 child 변수에 할당한다.

    if node == root:  # 삭제하려는 node가 root와 같다면
        root = child  # cild 에 root를 할당한다.
    else:

        if node is parent.right:  # 삭제하려는 노드가 부모 노드의 오른쪽 자식이라면 부모의 right fild에 child를 담는다
            # 메모리를 가리키는 표인터가 존재하지 않게되어서 저절로 사라진다.
            parent.right = child
        else:
            parent.left = child
            # 삭제하려는 node가 부모 노드의 왼쪽 자식이라면 부모의 왼쪽 필드에 삭제하려는 node의 child노드를 할당한다.
    return root


def delete_bst_case3(parent, node, root):  # parameter1: parentnode parameter2: need to be delete parameter3: root
    succp = node  # 삭제할 노드를 후계자 노드의 부모 노드로 설정
    succ = node.right  # 삭제할 노드의 오르쪽 자식을 후계자 노드로 설정

    while (succ.left != None):  # 후계자 노드의 왼쪽 자식이 None일 때 까지
        succp = succ  # 부모노드를 자식 노드로 바꿈
        succ = succ.left  # 후계자 노드의 왼쪽 노드를 후계가 노드로 설정 점점 내려간다.

    if (succp.left == succ):
        succp.left = succ.right
    else:  # 이미 succ.left  = None 양쪽에 둘다 자식이 없던것임
        succp.right = succ.right  # None 값이 succp의 오른쪽 자식에 대입됨

    node.key = succ.key  # 삭제할 node에 succesor 의 자식을 복산한다.
    node.value = succ.value  # 삭제할 node succesor의 자식을 복사한다.
    node = succ  # 함수가 종료 되면서 succ는 연결되어 있는 부모의 링크를 잃었기 땜에 삭제된다. 근데 이게 필요한건지 모르겠음.
    return root


def delelte_bst(root, key):
    if root == None:
        return None
    parent = None
    node = root
    while node != None and node.key != key:
        parent = node
        if key < node.key:
            node = node.left
        else:
            node = node.right
    if node is None: return None

    if node.left is None and node.right is None:
        root = delete_bst_case1(parent, node, root)

    elif node.left is None or node.right is None:
        root = delete_bst_case2(parent, node, root)

    else:
        root = delete_bst_case3(parent, node, root)