algorithm
이진 검색 트리
수색…
소개
이진 트리는 각 노드에 최대 두 개의 자식이있는 트리입니다. BST (Binary Search Tree)는 이원 트리가 특별한 순서로 배치 된 이진 트리입니다. 각 BST에서 왼쪽 하위 트리의 모든 값 (예 : 키)은 오른쪽 하위 트리의 값보다 작습니다.
이진 검색 트리 - 삽입 (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 인 노드).
사례 설명 :
- 삭제할 노드가 리프 노드 일 때 단순히 노드를 삭제하고
nullptr
을 상위 노드로 전달하십시오. - 삭제할 노드에 자식이 하나만있는 경우 자식 값을 노드 값에 복사하고 자식을 삭제합니다 (사례 1로 변환 됨)
- 삭제할 노드에 두 개의 자식이있는 경우 오른쪽 하위 트리의 최소값을 노드에 복사 한 다음 노드의 오른쪽 하위 트리에서 최소값을 삭제할 수 있습니다 (사례 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))