ツリー(Tree)(2)

38796 ワード

data structure テキストリンク

バイナリナビゲーションツリーの削除

Leafノードの削除

Leaf Node(=Terminal Node):サブノードのないノード

削除するノードの親ノードは削除するノードを指すことができません.

サブノードがあるノードを削除

ノードを削除する親ノードは、ノードを削除する子ノードを指します.

2つのサブノードを持つノードを削除

2つの方法で削除できます.

ノード右側のサブノードを削除する左側のサブノードのうち、値が最も小さいノード、すなわち最も左側のノードを削除する親ノード.(この方法で実現します.)

削除するノードの左側のサブノードの右側のサブノードのうち、値が最も大きいノード、つまり最も右側のノードを削除する親ノード.

第1の方法の順序

削除するノードの右側のサブノードを選択します.

右の子の一番左のノードを選択します.

このノードを削除するノードの親ノードの左分岐指向.

このノードの左側分岐は削除するノードの左側サブノードを指す.

このノードの右側ブランチは削除するノードの右側サブノードを指す.

ノードが右側のサブノードを有する場合、そのノードの元の親ノードの左側ブランチは、そのノードの右側のサブノードを指す.

バイナリ・ナビゲーション・ツリーの削除の実装

削除するノードのナビゲート

削除するノードがない場合はFalseを返し、関数を終了します.

def deleteNodeSearch(self, value):
        searched = False
        self.current_node = self.head
        self.parent_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif self.current_node.value > value:
                self.parent_node = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent_node = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False
        else:
            return self.current_node, self.parent_node

削除するノードはLeafノードです。

current_node:削除するノード

parent_node:削除するノードの親

def deleteNode(self, value):
        self.current_node, self.parent_node = self.deleteNodeSearch(value)
        
        # 삭제할 노드가 Leaf Node인 경우
        if self.current_node.left == None and self.current_node.right == None: 
            # 삭제할 노드가 부모 노드의 왼쪽에 있는 경우, 오른쪽에 있는 경우
            if self.parent_node.value > value: 
                self.parent_node.left = None
            else:
                self.parent_node.right = None

削除するノードがサブノードが1つしかない場合。

        # 삭제할 노드의 자식 노드가 1개인 경우
        if self.current_node.left != None and self.current_node.right == None: 
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.left
            else:
                self.parent_node.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.right
            else:
                self.parent_node.right = self.current_node.right

削除するノードにサブノードが2つある場合。

利用可能戦略

削除するノードの左側のサブノードの右側のサブノードのうち、値が最も大きいノード、つまり最も右側のノードを削除する親ノード.

削除するノードが親ノードの左側にある場合。

状況の数がまた分かれた.

最小値ノードのサブノードがない場合

最小値を持つノードのサブノード

        # 삭제할 노드의 자식 노드가 2개인 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 가장 작은 값을 가진 노드와 그 노드의 부모 노드
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            # 삭제할 노드가 왼쪽에 있는 경우
            if self.parent_node.value > value:
                # 가장 작은 값을 가진 노드가 오른쪽 자식 노드를 가진 경우
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

削除するノードが親ノードの右側にある場合。

状況の数がまた分かれた.

最小値ノードのサブノードがない場合

最小値を持つノードのサブノード

            # 삭제할 노드가 오른쪽에 있는 경우
            else:
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

完全なコード実装

class Node:
    def __init__(self, value): 
        # head, left, right는 노드의 주소를 가리키는 변수이다.
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self, head):
        # head는 루트노드의 주소를 가진다.
        self.head = head 
    
    def insertNode(self, value):
        # 트리를 순회하며 값을 삽입해야하기 때문에 임의 변수를 선언한다.
        self.current_node = self.head 
        
        while True:
            if self.current_node.value > 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 searchNode(self, value):
        self.current_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif self.current_node.value > value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False
    
    def deleteNodeSearch(self, value):
        searched = False
        self.current_node = self.head
        self.parent_node = self.head
        
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif self.current_node.value > value:
                self.parent_node = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent_node = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return False
        else:
            return self.current_node, self.parent_node
                
    def deleteNode(self, value):
        self.current_node, self.parent_node = self.deleteNodeSearch(value)
        
        # 삭제할 노드가 Leaf Node인 경우
        if self.current_node.left == None and self.current_node.right == None: 
            # 삭제할 노드가 부모 노드의 왼쪽에 있는 경우, 오른쪽에 있는 경우
            if self.parent_node.value > value: 
                self.parent_node.left = None
            else:
                self.parent_node.right = None
        
        # 삭제할 노드의 자식 노드가 1개인 경우
        if self.current_node.left != None and self.current_node.right == None: 
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.left
            else:
                self.parent_node.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if self.parent_node.value > value:
                self.parent_node.left = self.current_node.right
            else:
                self.parent_node.right = self.current_node.right
                
        # 삭제할 노드의 자식 노드가 2개인 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 가장 작은 값을 가진 노드와 그 노드의 부모 노드
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            # 삭제할 노드가 왼쪽에 있는 경우
            if self.parent_node.value > value:
                # 가장 작은 값을 가진 노드가 오른쪽 자식 노드를 가진 경우
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.left = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
            # 삭제할 노드가 오른쪽에 있는 경우
            else:
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent_node.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
                
        del self.current_node
        return True

すべてのコードをテスト

import random

# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))
# print (bst_nums)

# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = BinarySearchTree(head)
for num in bst_nums:
    binary_tree.insertNode(num)
    
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
    if binary_tree.searchNode(num) == False:
        print ('search failed', num)

# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
    if binary_tree.deleteNode(del_num) == False:
        print('delete failed', del_num)

# 출력 없음

Reference

この問題について(ツリー(Tree)(2)), 我々は、より多くの情報をここで見つけました https://velog.io/@zz1996zz/트리Tree-2

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

NSQ単機試験(単一topic)

iperfテスト帯域幅の問題--上下行帯域幅の差が大きい