algorithm
이진 검색 트리

소개

이진 검색 트리 - 삽입 (Python)

이것은 Python을 사용하여 이진 검색 트리 삽입을 간단히 구현 한 것입니다.

다음은 그 예입니다.

코드 조각 다음에 각 이미지는이 코드의 작동 방식을 더 쉽게 시각화 할 수 있도록 실행 시각화를 보여줍니다.

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

이진 검색 트리 - 삭제 (C ++)

삭제를 시작하기 전에 이진 검색 트리 (BST)에 몇 가지 조명을 넣기를 원합니다. BST의 각 노드는 최대 두 개의 노드 (왼쪽 및 오른쪽 자식)를 가질 수 있습니다. 노드의 왼쪽 하위 트리에는 키는 친 노드의 키보다 작거나 같습니다. 노드의 오른쪽 하위 트리에는 상위 노드의 키보다 큰 키가 있습니다.

이진 검색 트리 속성 을 유지하면서 트리에서 노드를 삭제합니다 .

노드를 삭제하는 동안 고려해야 할 세 가지 경우가 있습니다.

• 사례 1 : 삭제할 노드가 리프 노드입니다 (값 22 인 노드).
• 사례 2 : 삭제할 노드에 자식이 1 개 있습니다 (값이 26 인 노드).
• 사례 3 : 삭제할 노드가 둘 다 자식을 갖습니다 (값이 49 인 노드).

사례 설명 :

1. 삭제할 노드가 리프 노드 일 때 단순히 노드를 삭제하고 nullptr 을 상위 노드로 전달하십시오.
2. 삭제할 노드에 자식이 하나만있는 경우 자식 값을 노드 값에 복사하고 자식을 삭제합니다 (사례 1로 변환 됨)
3. 삭제할 노드에 두 개의 자식이있는 경우 오른쪽 하위 트리의 최소값을 노드에 복사 한 다음 노드의 오른쪽 하위 트리에서 최소값을 삭제할 수 있습니다 (사례 2로 변환 됨)

참고 : 오른쪽 하위 트리의 최소값은 최대 하나의 자식을 가질 수 있으며 너무 왼쪽 자식이 최소값이 아니거나 BST 속성을 따르지 않는 자식을 가진 경우 해당 자식을 가질 수 있습니다.

트리에있는 노드의 구조와 삭제를위한 코드 :

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

위 코드의 시간 복잡도는 O ( h )입니다. 여기서 h 는 트리의 높이입니다.

BST에서 가장 낮은 공통 조상

BST를 고려하십시오.

22와 26의 가장 낮은 공통 조상은 24입니다.

26과 49의 가장 낮은 공통 조상은 46입니다.

22와 24의 가장 낮은 공통 조상은 24입니다.

이진 검색 트리 속성은 노드가 가장 낮은 조상을 찾는 데 사용될 수 있습니다.

Psuedo code :

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }

이진 검색 트리 - 파이썬

class Node(object):
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.val = val


class BinarySearchTree(object):
    def insert(self, root, node):
        if root is None:
            return node

        if root.val < node.val:
            root.r_child = self.insert(root.r_child, node)
        else:
            root.l_child = self.insert(root.l_child, node)

        return root


    def in_order_place(self, root):
        if not root:
            return None
        else:
            self.in_order_place(root.l_child)
            print root.val
            self.in_order_place(root.r_child)

    def pre_order_place(self, root):
        if not root:
            return None
        else:
            print root.val
            self.pre_order_place(root.l_child)
            self.pre_order_place(root.r_child)

    def post_order_place(self, root):
        if not root:
            return None
        else:
            self.post_order_place(root.l_child)
            self.post_order_place(root.r_child)
            print root.val

"" "다른 노드를 만들고 그것에 데이터를 삽입하십시오." ""

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]

for nd in nodeList:
    node.insert(r, Node(nd))

print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))