[자료구조] Binary Search Tree _ 이진 탐색 트리

Binary Search Tree

1) 데이터 특징: Left Child의 key값은 parent보다 작고, Right Child의 key 값은 parent보다 큼.

2) 형태적 특징: Binary Tree

 

- Inorder Traversal of BST = 오름차순 sort

Searching – Recursive ver.

Searching – Iterative ver.

 

Searching BST의 시간 복잡도

- Average case: O(h), h=height of tree

- Worst case: O(n), n=number of nodes

 

 

 

 

 

 

 

Insertion BST의 시간복잡도

- O(h), h=height of tree

 

Insertion (1)

 

Insertion (2) – Modified Search

- Tree가 비었거나, key가 들어갈 자리가 이미 차있으면 NULL리턴.

- key가 들어갈 tree의 마지막 노드 리턴

treePointer modifiedSearch (treePointer* root, int k) { treePointer tree=root; if (*root == NULL) return NULL; while (tree->leftChild || tree->rightChild){    if (k == tree->data.key) return NULL;    if (k < tree->data.key) tree = tree->leftChild;    else tree = tree->rightChild;    } return tree; }

 

Height of BST

- Average case: O(log2n )

- Worst case: O(n)

- Searching, Insertion, Deletion의 시간 복잡도: O(h), h는 Height of Tree. Skewed Tree일 경우

 

Deletion

1) Deletion of a leaf node

2) Deletion of a node with 1 child: 바로 parent 연결

3) Deletion of a node with 2 child: 둘 중에 하나 끌고 올라옴

void delete(treePointer root, int k) { treePointer parent, ptr, succ, succ_parent, child; parent = NULL; ptr = root; while ((ptr!=NULL) && (ptr->data.key != k)) { parent = ptr; if (k < ptr->data.key) ptr = ptr->leftChild; else ptr = ptr->rightChild; } if (ptr == NULL) { return; } // 데이터가 없을 때 if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) {// child node가 없을 때 if (parent != NULL) { if (parent->leftChild == ptr) parent->leftChild = NULL; else parent->rightChild = NULL;} else root = NULL; } else if ((ptr->leftChild == NULL) || (ptr->rightChild == NULL)) {// child node가 1개 있을 때 if (ptr->leftChild != NULL) child = ptr->leftChild; else child = ptr->rightChild; if (parent != NULL) { if (parent->leftChild == ptr) parent->leftChild = child; else parent->rightChild = child;} else root = child; } else {    // child node가 2개 있을 때 succ_parent = ptr; succ = ptr->leftChild; while (succ->rightChild != NULL) { succ_parent = succ; succ = succ->rightChild;} if (succ_parent->leftChild == succ) succ_parent->leftChild = succ->leftChild; else succ_parent->rightChild = succ->leftChild; ptr->data.key = succ->data.key; ptr = succ; } return; }