- 왼쪽 서브트리 ( left subtree )는 현재 노드의 값 보다 작은 노드들만 위치한다.
- 오른쪽 서브트리 ( right subtree ) 는 현재 노드의 값 보다 큰 노드들만 위치한다.
- 왼쪽, 오른쪽 서브 트리 모두 각각 binary search tree이다.
- 모든 노드는 최대 2개의 자손( successor )를 가질 수 있다.
- 중복되는 값을 가진 노드는 없어야 한다.
- 모든 노드는 root로 부터 고유한 길( unique path )이 있다.
Binary Tree 와 Binary search tree의 차이점.
Binary search tree (BST)는 Binary Tree의 특이한 케이스이다. Binary Tree는 노드가 2개의 자식 노드를 가질 수 있는데, BST는 그 자식 노드가 왼쪽에는 자신보다 작은값을, 오른쪽에는 자신보다 큰 값을 갖는 경우를 말한다.BST의 특이점
Binary "SEARCH" tree라는 이름에서 알 수 있듯, root 및 모든 subtree를 기준으로 특정 값을 찾을 때 찾는 값이 해당 노드값 보다 작으면 왼쪽 subtree를 크다면 오른쪽 subtree를 검색하면 원하는 값을 O(logN)이 런타임으로 찾을 수 있다.트리를 InOrder방식으로 방문하면, 오름 차순으로 정렬된 데이터를 얻을 수 있다.
BST with C++
BST에 사용될 메서드를 생각해보자.1. 값을 추가하는 add() 메서드
2. 값을 제거하는 remove() 메서드
3. 값이 존재하는지 찾는 find()메서드
일단 사용할 Node클래스를 먼저 정의하자.
class Node
{
public:
int data_;
Node* left_;
Node* right_;
Node()
{
data_ = 0;
left_ = right_ = NULL;
}
};
사용할 Tree클래스는 이 Node클래스를 이용해서 메서드를 작성하자.
값을 추가하는 add() 메서드
외부에서 호출하는 addData() 함수를 하나 만들고, 내부적으로 재귀적으로 사용할 _addData() 함수를 만들어서 밖에서는 안보이도록 숨기자. addData() 에서는 추가할 값만 받고, _addData() 함수에서는 부모 노드 값을 받아서 적당한 위치를 찾아 데이터를 만들자.
bool Tree::addData( int value )
{
return _addData( root_, value );
}
외부에서 보이는 addData() 메서드이다. 전달인자는 추가할 값 하나.
bool Tree::_addData( Node*& node, int value )
{
if( node == NULL )
{
node = new Node;
if( node == NULL )
return false;
node->data_ = value;
node->left_ = node->right_ = NULL;
return true;
}
else
{
if( node->data_ > value )
{
return _addData( node->left_, value );
}
else if( node->data_ < value )
{
return _addData( node->right_, value );
}
}
return false;
}
내부적으로 사용하는 _addData() 메서드이다. 추가할 노드의 부모 노드의 참조를 전달인자로 받는다. 만약 Node*& 연산이 가독성이 떨어진다고 생각되면 typedef를 이용해 예쁘게 만들어도 된다. _addData()에 node가 NULL인 경우는 원하는 위치를 찾은 경우이다. 메모리를 할당하고 값을 세팅하자.
넘겨받는 node가 NULL이 아닐 경우 자리를 찾기 위해 값 비교를 한다. 만약 value값이 작다면 node의 left_를, 크다면 right_를 전달인자로 _addData()를 recursive 호출 하자. 그럼 적당한 자리를 찾아가서 값이 추가가 된다.
이런식으로 add된 값들은 balance되지 않는다. 따라서 10, 9, 8, 7 이런식으로 add를 하면 10을 루트로 가진 왼쪽노드로만 이루어진 트리가 만들어진다. AVL트리는 나중에 따로 연구하자.
값을 제거하는 remove()메서드
상대적으로 remove 메서드는 add보다 조금 복잡하다. leaf를 remove하면 간단하지만, 중간에 값을 remove하면 트리를 새로 구성해야 하기 때문이다.
remove하는 시나리오는 크게 3개이다.
- leaf를 remove하는 경우 : 그냥 삭제하자
- left에 subtree가 있는 경우 : left의 subtree에서 가장 큰 값을 가져와 현재 node에 대입하고, 그 노드를 제거
- right에 subtree가 있는 경우 : right의 subtree에서 가장 작은 값을 가져와 현재 node에 대입하고, 그 노드는 제거
- remove를 재귀적으로 호출하도록 하자.
bool Tree::removeData( int value )
{
Node** node = _findNode( value );
if( node == NULL )
return false;
return _removeData( *node );
}
find함수를 이용해 제거 될 node를 찾는다. 이제 이 node를 remove해보자.
bool Tree::_removeData( Node*& node )
{
if( node == NULL )
return false;
if( node->left_ == NULL && node->right_ == NULL )
{
delete node;
node = NULL;
}
else if( node->right_ != NULL )
{
// .2 get smallest node from right node
Node** targetNode = &node->right_;
for(;;)
{
if( (*targetNode)->left_ == NULL )
{
node->data_ = (*targetNode)->data_;
_removeData( (*targetNode) );
break;
}
else
{
targetNode = &(*targetNode)->left_;
}
}
}
else if( node->left_ != NULL )
{
// .3 get biggest node from left node
Node** targetNode = &node->left_;
for(;;)
{
if( (*targetNode)->right_ == NULL )
{
node->data_ = (*targetNode)->data_;
_removeData( (*targetNode) );
break;
}
else
{
targetNode = &(*targetNode)->right_;
}
}
}
return true;
}
내부적으로 호출되는 _removeData() 메서드이다. 일단 제거될 node가 leaf인지 확인하자. 이 노드는 그냥 제거하면 된다. leaf가 아니라면 머리를 써야된다. left나 right중 아무 노드나 골라서 먼저 찾아보자. 이 자리에는 left노드 중 가장 큰 값이나, right 노드 중 가장 작은 값이 오면 BST의 조건을 만족한다.
코드에서는 right먼저 검사를 했다. right에서 가장 작은 값을 찾자. BST특성 상 작은 값은 left에 존재하므로 left만 따라가면 된다. 만약 left가 NULL이라면 이 값이 가장 작은 값이다. 그럼 그 값을 복사해서 내 자리에 놓고 그 자리는 제거한다. 그럼 재귀적으로 제거된 값에 대해서 똑같은 연산이 반복되서 트리가 구성된다.
값을 찾는 find() 메서드
BST의 특징을 따라 노드를 따가라면 된다. 현재 노드와 비교해서 값이 작으면 left로, 반대로 크다면 right로 이동해서 똑같이 비교를 하면 된다.
Node** Tree::_findNode( int value )
{
Node** pNode = &root_;
for(;;)
{
if( pNode == NULL || (*pNode) == NULL )
break;
if( (*pNode)->data_ == value )
break;
if( (*pNode)->data_ > value )
pNode = &(*pNode)->left_;
else
pNode = &(*pNode)->right_;
}
return pNode;
}
http://en.wikipedia.org/wiki/Binary_search_tree
댓글 없음:
댓글 쓰기