데이터 구조의 이 진 트 리 / 이 진 트 리 찾기 수 / 질서 있 는 이 진 트 리 / 정렬 이 진 트 리

개념 ~
이 진 트 리 (영어: Binary Search Tree) 는 이 진 트 리, 질서 있 는 이 진 트 리 (영어: ordered binary tree) 라 고도 부 르 며 이 진 트 리 (영어: sorted binary tree) 를 정렬 합 니 다. 빈 트 리 나 다음 과 같은 성질 을 가 진 이 진 이 진 트 리 를 말 합 니 다.

만약 에 임의의 노드 의 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 작다.

만약 에 임의의 노드 의 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 크다.

임의의 노드 의 왼쪽, 오른쪽 나무 도 각각 두 갈래 로 나 무 를 찾는다.

키 가 같은 노드 가 없습니다.

우세 ~ O (log n)
이 진 트 리 는 다른 데이터 구조 에 비해 검색, 삽입 시간 복잡 도가 낮 습 니 다. O (log n) 입 니 다.
이 진 트 리 는 기본 적 인 데이터 구조 로 더욱 추상 적 인 데이터 구 조 를 구축 하 는 데 사용 된다. 예 를 들 어 집합, multiset, 관련 배열 등 이다.
이 진 트 리 를 찾 는 과정 은 차 우 이 진 트 리 와 유사 하 며, 일반적으로 이 진 트 리 를 이 진 트 리 의 저장 구조 로 사용 합 니 다.중간 순서 로 이 진 트 리 를 옮 겨 다 니 며 나 무 를 찾 으 면 키워드 의 질서 있 는 서열 을 얻 을 수 있 습 니 다. 무질서 한 서열 은 이 진 트 리 를 구성 하여 질서 있 는 서열 로 바 꿀 수 있 습 니 다. 트 리 를 구성 하 는 과정 은 무질서 한 서열 을 찾 는 과정 입 니 다.매번 삽 입 된 새로운 결점 은 두 갈래 로 나무의 새로운 잎 결점 을 찾 는 것 이다. 삽입 작업 을 할 때 다른 결점 을 이동 할 필요 가 없다. 단지 어떤 결점 의 지침 을 바 꾸 고 빈 것 에서 빈 것 으로 바 꾸 면 된다.
검색, 삽입, 삭제 의 복잡 도 는 나무 가 높 고 기대, 최 악 (수열 이 질서 가 있 고 나무 가 선형 표 로 퇴화) 과 같다.
두 갈래 찾기 트 리 의 최 악의 효율 은 O (n) 이지 만 동적 조 회 를 지원 하 며 SBT, AVL 트 리, 붉 은 검 은 나무 등 개선 판 두 갈래 찾기 트 리 가 많 습 니 다.
그러므로 좋 은 동적 검색 방법 을 잃 지 않 는 다.
그 중에서 C + + 의 STL 에 있 는 set 는 빨간색 과 검은색 트 리 를 저장 구조 로 사용 합 니 다 (ps: hash set 는 hash table 을 저장 구조 로 사용 합 니 다).
Search BST
두 갈래 검색 트 리 b 에서 x 를 찾 는 과정 은 다음 과 같 습 니 다.

b 가 빈 나무 라면 검색 에 실 패 했 습 니 다. 그렇지 않 으 면:

x 가 b 의 루트 노드 와 같은 데이터 필드 의 값 을 찾 으 면 성공 합 니 다.그렇지 않 으 면:

x 가 b 의 루트 노드 보다 작은 데이터 필드 의 값 이 있 으 면 왼쪽 트 리 를 검색 합 니 다.그렇지 않 으 면:

오른쪽 나 무 를 찾 습 니 다.

 1 /*      C++  ，  */
 2 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){
 3   //    T                   key     ，     ，
 4   //   p         ，   TRUE，                
 5   //       FALSE，  f  T   ，       NULL
 6   if(!T) { //     
 7     p=f;
 8     return false;
 9   }
10   else if (key == T->data.key) { //    
11     p=T;
12     return true;
13   }
14   else if (key < T->data.key) //         
15     return SearchBST(T->lchild, key, T, p);
16   else //         
17     return SearchBST(T->rchild, key, T, p);
18 }

InsertBST
두 갈래 검색 트 리 b 에 노드 s 알고리즘 을 삽입 합 니 다. 과정 은 다음 과 같 습 니 다.

b 가 빈 나무 라면 s 가 가리 키 는 결점 을 뿌리 노드 로 삽입 합 니 다. 그렇지 않 으 면:

s - > data 가 b 의 루트 노드 의 데이터 필드 의 값 과 같 으 면 되 돌려 줍 니 다. 그렇지 않 으 면:

s - > data 가 b 의 뿌리 노드 의 데이터 필드 의 값 보다 작 으 면 s 가 가리 키 는 노드 를 왼쪽 하위 트 리 에 삽입 합 니 다. 그렇지 않 으 면:

s 가 가리 키 는 노드 를 오른쪽 트 리 에 삽입 합 니 다.(새 삽입 노드 는 항상 잎 노드)

 1 /*      T         e.key      ，  e   TRUE，    FALSE*/
 2 Status InsertBST(BiTree *T, ElemType e){  
 3       if(!T)  
 4         {        
 5             s = new BiTNode;
 6             s->data = e; s->lchild = s->rchild = NULL;
 7             T=s;    //    *s      
 8         }
 9       else if(e.key == p->data.key)
10         return false;//     e.key     ，    
11       if (e.key < p->data.key)
12     InsertBST(p->lchild, e);    // e     
13       else 
14     InsertBST(p->rchild, e);    // e     
15       return true;
16  }

DeleteBST
두 갈래 에서 나 무 를 찾 아 결점 을 삭제 하고 세 가지 상황 으로 나 누 어 토론 합 니 다.

만약 에 * p 결점 이 잎 결점 이 라면 PL (왼쪽 나무) 과 PR (오른쪽 나무) 은 모두 빈 나무 이다.잎 결점 을 삭제 하고 나무 전체의 구 조 를 파괴 하지 않 기 때문에 부모 결점 의 지침 만 수정 하면 된다.

만약 에 * p 결점 이 왼쪽 나무 PL 또는 오른쪽 나무 PR 만 있 으 면 PL 또는 PR 을 부모 결점 * f 의 왼쪽 나무 (* p 가 왼쪽 나무 일 때) 또는 오른쪽 나무 (* p 가 오른쪽 나무 일 때) 로 만 들 면 됩 니 다. 이 수정 을 해도 이 진 트 리 의 특성 을 파괴 하지 않 습 니 다.

* p 결점 의 왼쪽 나무 와 오른쪽 나무 가 모두 비어 있 지 않 으 면.* p 를 삭제 한 후에 다른 요소 간 의 상대 적 인 위 치 를 변 하지 않 게 유지 하기 위해 중간 순서에 따라 질서 있 게 조정 할 수 있 습 니 다. 하 나 는 * p 의 왼쪽 나 무 를 * f 의 왼쪽 / 오른쪽 (* p 가 * f 의 왼쪽 나무 인지 오른쪽 나무 인지 에 따라 정 함) 서브 나무 입 니 다. * s 는 * p 왼쪽 나무의 가장 오른쪽 아래 의 결점 이 고 * p 의 오른쪽 나 무 는 * s 의 오른쪽 나무 입 니 다.둘 째 는 * p 의 직접 전구 (in - order predecessor) 나 직접 후계 (in - order successor) 를 * p 대신 한 다음 에 이 진 트 리 에서 직접 전구 (또는 직접 후계) 를 삭제 합 니 다.

두 갈래 찾기 트 리 에서 결점 을 삭제 하 는 알고리즘 은 다음 과 같 습 니 다.

 1 Status DeleteBST(BiTree *T, KeyType key){
 2   //      T        key      ，        ，   
 3   //TRUE；    FALSE
 4   if(!T) 
 5     return false;    //        key     
 6   else{
 7     if(key == T->data.key) {     //         key     
 8       return Delete(T);
 9     }
10     else if(key < T->data.key)
11       return DeleteBST(T->lchild, key);
12     else
13       return DeleteBST(T->rchild, key);
14   }
15 }
16 
17 Status Delete(BiTree *p){
18   //        ，    
19   BiTree *q, *s;
20   if (!p->rchild && !p->lchild)
21   {
22       delete p;
23       p = NULL;
24   }
25   else if(!p->rchild){    //              
26     q=p->lchild;
27     p->data = p->lchild->data;
28     p->lchild=p->lchild->lchild;
29     p->rchild=p->lchild->rchild;
30 
31     delete q;
32   }
33   else if(!p->lchild){    //             
34     q=p->rchild;
35     p->data = p->rchild->data;
36     p->lchild=p->rchild->lchild;
37     p->rchild=p->rchild->rchild;
38 
39     delete q;  }
40   else{    //       
41     q=p; 
42     s=p->lchild;
43     while(s->rchild){ 
44       q=s; 
45       s=s->rchild;
46     }    //  ，       
47     p->data = s->data;    //s       “  ”
48     if(q!=p)    
49       q->rchild = s->lchild;    //  *q    
50     else 
51       q->lchild = s->lchild;    //  *q    
52     delete s;
53   }
54   return true;
55 }

파 이 썬 버 전
binary_tree_delete

 1 def find_min(self):   # Gets minimum node (leftmost leaf) in a subtree
 2     current_node = self
 3     while current_node.left_child:
 4         current_node = current_node.left_child
 5     return current_node
 6 
 7 def replace_node_in_parent(self, new_value=None):
 8     if self.parent:
 9         if self == self.parent.left_child:
10             self.parent.left_child = new_value
11         else:
12             self.parent.right_child = new_value
13     if new_value:
14         new_value.parent = self.parent
15 
16 def binary_tree_delete(self, key):
17     if key < self.key:
18         self.left_child.binary_tree_delete(key)
19     elif key > self.key:
20         self.right_child.binary_tree_delete(key)
21     else: # delete the key here
22         if self.left_child and self.right_child: # if both children are present
23             successor = self.right_child.find_min()
24             self.key = successor.key
25             successor.binary_tree_delete(successor.key)
26         elif self.left_child:   # if the node has only a *left* child
27             self.replace_node_in_parent(self.left_child)
28         elif self.right_child:  # if the node has only a *right* child
29             self.replace_node_in_parent(self.right_child)
30         else: # this node has no children
31             self.replace_node_in_parent(None)

in-order-traversal

1 def traverse_binary_tree(node, callback):
2     if node is None:
3         return
4     traverse_binary_tree(node.leftChild, callback)
5     callback(node.value)
6     traverse_binary_tree(node.rightChild, callback)

두 갈래 정렬 트 리 만 들 기 ()

 1 def build_binary_tree(values):
 2     tree = None
 3     for v in values:
 4         tree = binary_tree_insert(tree, v)
 5     return tree
 6 
 7 def get_inorder_traversal(root):
 8     '''
 9     Returns a list containing all the values in the tree, starting at *root*.
10     Traverses the tree in-order(leftChild, root, rightChild).
11     '''
12     result = []
13     traverse_binary_tree(root, lambda element: result.append(element))
14     return result

각 결점 은 이 결점 의 층 횟수 이다.최 악의 경우 선후 로 삽 입 된 키워드 가 질서 가 있 을 때 구 성 된 이 진 찾기 트 리 는 한 개의 나무 로 탈바꿈 하고 나무의 깊이 는 평균 찾기 길이 (순서 찾기 와 동일) 이 며 가장 좋 은 경 우 는 이 진 찾기 트 리 의 형태와 반 으로 찾 은 판정 트 리 가 같 으 며 평균 찾기 길이 와 정비례 () 이다.