CH 08 Binary Search Tree

Tree

Tree

• cicle이 없는 관계
• 계층적인 구조
• Root Node: 제일 위에 있는 노드, 부모 노드가 없는 노드
• Leaf Node: 제일 아래 있는 노드, 자식 노드가 없는 노드
• tree의 단계를 내려갈 때마다 level 증가
• tree의 일부분을 잘라내도 subtree 형성
• 실제 자료 구조는 root 하나만 존재하고 tree의 모습은 관념적인 개념

Binary Tree

• parent node: 바로 위의 상위 노드
• child node: 바로 밑의 하위 노드
• parent는 여러 개의 child를 가지는 게 가능하지만, child는 여러 개의 parent를 가질 수 없음
• 하나의 노드가 최대 두 개까지의 child node를 가지는 tree
• path: 특정 노드로 가기 위해 거쳐 가는 경로
  • tree에선 path가 unique
• ancestor node: 자신보다 위에 있는 모든 상위 노드
• descendant node: 자신보다 밑에 있는 모든 하위 노드
• height: level의 number

Full Tree

• 모든 노드들이 2개의 child node를 갖춘 tree
• leaf node가 모두 같은 level에 존재
• non-leaf node는 모두 child node를 두 개씩 가짐
• level이 h인 full tree는 총 2^h -1 개의 노드를 가짐
• 노드 수가 n개인 tree의 level
  • 모든 노드가 선형으로 이루어져 있을 때: n
  • full tree일 때: log_2 (n + 1)

Complete Tree

• Full Tree는 Complete Tree의 한 종류
• left는 채워져 있지만 right가 없는 형태

Binary Search Tree (Recursive)

Binary Search Tree

• 현재값보다 작은 값은 왼쪽 노드에, 큰 값은 오른쪽 노드에 위치하는 binary tree
• item끼리 크다 작다는 개념 필요
• item은 서로 다름

Tree.h

#include <string>
#include <fstream>
#include "QueType.h"

typedef char ItemType;
struct TreeNode;
enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

class TreeType {
public:
  TreeType();
  ~TreeType();
  TreeType(const TreeType& originalTree); 
  void MakeEmpty();
  void operator=(const TreeType& originalTree);
  bool IsEmpty() const;
  bool IsFull() const;
  int LengthIs() const; 
  void RetrieveItem(ItemType& item, bool& found);
  void InsertItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetTree(OrderType order); 
  void GetNextItem (ItemType& item, OrderType order, bool& finished);
  void Print(std::ofstream& outFile) const;
private:
  TreeNode* root;
  QueType preQue;
  QueType inQue;
  QueType postQue;
};

Construtor

# 기본 생성자
TreeType::TreeType()
{
    root = NULL;
}

# 입력 parameter로 tree가 주어졌을 때 생성자
TreeType::TreeType(const TreeType& originalTree)
{
    CopyTree(root, originalTree.root);
}

Destructor

• 입력 paramter가 NULL이 아니라면
• 자기 자신 노드를 먼저 삭제하고 left, right 타고 내려가면서 삭제
• &로 전달되어 노드끼리 이어 주지 않아도 됨

void Destroy(TreeNode*& tree)
{
    if (tree != NULL)
    {
        Destroy(tree->left);
        Destroy(tree->right);
        delete tree;
  }
}

TreeType::~TreeType()
{
    Destroy(root);
}

MakeEmpty

void TreeType::MakeEmpty()
{
     Destroy(root);
     root = NULL;
}

Copy Constructor

• Copy Constructor
  • 자기 자신을 복사하는 경우엔 무시
  • A = B 에서 B가 originalTree
  • originalTree가 root와 다른 경우는 현재 tree 모두 삭제한 뒤 복사
• CopyTree
  • A = B에서 B가 empty tree라면 NULL 반환
  • 그렇지 않다면 root부터 시작해서 타고 내려가면서 노드 생성 후 복사
  • &로 전달하기 때문에 노드는 알아서 연결됨

void CopyTree(TreeNode*& copy, const TreeNode* originalTree);

void TreeType::operator=(const TreeType& originalTree)
{
     if (&originalTree == this)
         return;             // Ignore assigning self to self
     Destroy(root);      // Deallocate existing tree nodes
     CopyTree(root, originalTree.root);
}

void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
{
     if (originalTree == NULL)
         copy = NULL;
     else
     {
         copy = new TreeNode;
         copy->info = originalTree->info;
         CopyTree(copy->left, originalTree->left);
         CopyTree(copy->right, originalTree->right);
     }
}

IsEmpty

bool TreeType::IsEmpty() const
{
    return root == NULL;
}

IsFull

bool TreeType::IsFull() const
{
    TreeNode* location;
    try
    {
        location = new TreeNode;
        delete location;
        return false;
    }
    catch(std::bad_alloc exception)
    {
        return true;
    }
}

LengthIs

• 현재 자기 노드 기준으로 자신의 노드 수 1 + 왼쪽 tree 노드 수 + 오른쪽 tree 노드 수

int TreeType::LengthIs() const
{
    return CountNodes(root);
}


int CountNodes(TreeNode* tree)
{
    if (tree == NULL)
        return 0;
    else 
        return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

RetrieveItem

• 입력받은 노드가 NULL 이면 찾지 못한 상태이므로 false
• item이 입력받은 노드값보다 작으면 item은 left tree에 존재하기 때문에 left tree 탐색
• item이 입력받은 노드값보다 크면 item은 right tree에 존재하기 때문에 right tree 탐색
• item이 입력받은 노드값보다 작지도 크지도 않고 같으면 item을 찾은 것이므로 true

void Retrieve(TreeNode* tree, ItemType& item, bool& found);

void TreeType::RetrieveItem(ItemType& item, bool& found)
{
	Retrieve(root, item, found);
}

void Retrieve(TreeNode* tree, ItemType& item, bool& found)
{
	if (tree == NULL)
		found = false;                     // item is not found.
	else if (item < tree->info)
		Retrieve(tree->left, item, found); // Search left subtree.
	else if (item > tree->info)
		Retrieve(tree->right, item, found);// Search right subtree.
	else
	{
		item = tree->info;                 // item is found.
		found = true;
	}
}

InsertItem method

• 새로 넣으려는 newitem을 root부터 시작해서 비교
• newitem이 더 크면 오른쪽으로 타고 내려가서 비교
• newitem이 더 작으면 왼쪽으로 타고 내려가서 비교
• 타고타고 내려가다 더 갈 노드가 없을 때 그 자리에 insert
• insert 순서에 따라 tree의 모양이 바뀜
• 시간복잡도: O(logN)
• insert 에서는 tree를 &로 전달해 주기 때문에 pointer끼리 이어 주지 않아도 자동으로 이어짐
  

void Insert(TreeNode*& tree, ItemType item);

void TreeType::InsertItem(ItemType item)
{
	Insert(root, item);
}


void Insert(TreeNode*& tree, ItemType item)
{
	if (tree == NULL)
	{// Insertion place found.
		tree = new TreeNode;
		tree->right = NULL;
		tree->left = NULL;
		tree->info = item;
	}
	else if (item < tree->info)
		Insert(tree->left, item);    // Insert in left subtree.
	else
		Insert(tree->right, item);   // Insert in right subtree.
}

DeleteItem

• child node를 지우는 경우

  • 해당 노드만 삭제

• 하나의 child node를 가지고 있는 node를 지우는 경우

  • 해당 노드를 삭제
  • 해당 노드의 자리는 child node로 대치
    

• 두 개의 child node를 가지고 있는 node를 지우는 경우

  • left tree의 최댓값이나 right tree의 최소값이 삭제된 item 자리 대신
    
  • 노드의 위치를 바꾸고 나서도 delete 상황 점검 필요

• DeleteItem Method 연습
  

• Delete

  • item이 tree의 값보다 작으면 left tree 검색하도록 함
  • item이 tree의 값보다 크면 right tree 검색하도록 함
  • item이 tree값과 일치하면 (삭제할 item을 찾으면) DeleteNode 실행

• DeleteNode

  • tempPtr에 삭제해야 할 item 위치 저장
  • left tree가 NULL이면 (right child만 존재) item 위치에 right child 대치
  • right tree가 NULL이면 (left child만 존재) item 위치에 left child 대치
  • left, right child 모두 존재하면 GetPrecessor에 left tree를 넣고 left tree의 most right node를 data에 반환
    • item 자리에 data를 놓고 item에 대해 다시 Delete 실시
      • item과 data가 뒤바뀐 tree에 대해서도 delete 검사
      • GetPrecessor에 right tree를 넣고 right tree의 most left node를 반환하는 방식으로 변환 가능

void DeleteNode(TreeNode*& tree);

void Delete(TreeNode*& tree, ItemType item);

void GetPredecessor(TreeNode* tree, ItemType& data);

void TreeType::DeleteItem(ItemType item)
{
	Delete(root, item);
}


void Delete(TreeNode*& tree, ItemType item)
{
	if (item < tree->info)
		Delete(tree->left, item);   // Look in left subtree.
	else if (item > tree->info)
		Delete(tree->right, item);  // Look in right subtree.
	else
		DeleteNode(tree);           // Node found; call DeleteNode.
}

void DeleteNode(TreeNode*& tree)
{
	ItemType data;
	TreeNode* tempPtr;

	tempPtr = tree;
	if (tree->left == NULL)
	{
		tree = tree->right;
		delete tempPtr;
	}
	else if (tree->right == NULL)
	{
		tree = tree->left;
		delete tempPtr;
	}
	else
	{
		GetPredecessor(tree->left, data); // GetPredecessor(tree->right, data);
		tree->info = data;
		Delete(tree->left, data);  // Delete(tree->right, data);
	}
}

void GetPredecessor(TreeNode* tree, ItemType& data)
{
	while (tree->right != NULL)
		tree = tree->right;
	data = tree->info;
}

/*
void GetPredecessor(TreeNode* tree, ItemType& data)
{
	while (tree->left != NULL)
		tree = tree->left;
	data = tree->info;
}
*/

ResetTree

• next 개념을 넣기 위해서, 실제 tree를 메모리로 저장하기 위해서는 1차원 배열로 저장
• Tree를 Queue 형태로 저장
• Tree Traversal Method (Tree를 저장하는 순서)
  • PreOrder: tree-> left -> right
    
  • InOrder: left -> tree ->right
    
  • PostOrder: left -> right -> tree
    

void PreOrder(TreeNode*, QueType&);
void InOrder(TreeNode*, QueType&);
void PostOrder(TreeNode*, QueType&);


void TreeType::ResetTree(OrderType order)
{
	switch (order)
	{
	case PRE_ORDER: PreOrder(root, preQue);
		break;
	case IN_ORDER: InOrder(root, inQue);
		break;
	case POST_ORDER: PostOrder(root, postQue);
		break;
	}
}


void PreOrder(TreeNode* tree, QueType& preQue)
{
	if (tree != NULL)
	{
		preQue.Enqueue(tree->info);
		PreOrder(tree->left, preQue);
		PreOrder(tree->right, preQue);
	}
}


void InOrder(TreeNode* tree, QueType& inQue)
{
	if (tree != NULL)
	{
		InOrder(tree->left, inQue);
		inQue.Enqueue(tree->info);
		InOrder(tree->right, inQue);
	}
}


void PostOrder(TreeNode* tree, QueType& postQue)
{
	if (tree != NULL)
	{
		PostOrder(tree->left, postQue);
		PostOrder(tree->right, postQue);
		postQue.Enqueue(tree->info);
	}
}

GetNextItem

• tree를 reset하면 각각의 queue에 순서 맞춰 저장돼 있음
• queue의 특성상 first in, first out
• Deqeue를 하면 다음으로 입력된 값이 출력

void TreeType::GetNextItem(ItemType& item, OrderType order, bool& finished)
{
	finished = false;
	switch (order)
	{
	case PRE_ORDER: preQue.Dequeue(item);
		if (preQue.IsEmpty())
			finished = true;
		break;
	case IN_ORDER: inQue.Dequeue(item);
		if (inQue.IsEmpty())
			finished = true;
		break;
	case  POST_ORDER: postQue.Dequeue(item);
		if (postQue.IsEmpty())
			finished = true;
		break;
	}
}

Binary Search Tree (Iterative)

FindeNode

• tree에서 item이 존재하는 노드를 nodePtr에, item이 존재하는 노드의 부모 노드를 parentPtr에 반환하는 함수
• item이 nodePtr보다 작을 때는 nodePtr을 parentPtr로 설정하고 left tree를 따라 내려가 값 비교
• item이 nodePtr보다 클 때는 nodePtr을 parentPtr로 설정하고 right tree를 따라 내려가 값 비교

void FindNode(TreeNode* tree, ItemType item, TreeNode*& nodePtr, TreeNode*& parentPtr)
{
	nodePtr = tree;
	parentPtr = NULL;
	bool found = false;
	while (nodePtr != NULL && !found)
	{
		if (item < nodePtr->info)
		{
			parentPtr = nodePtr;
			nodePtr = nodePtr->left;
		}
		else if (item > nodePtr->info)
		{
			parentPtr = nodePtr;
			nodePtr = nodePtr->right;
		}
		else
			found = true;
	}
}

InsertItem

• FindNode 함수를 통해 item을 탐색하면 nodePtr은 NULL, parentPtr은 newNode의 parent node를 가리키게 됨
  • InsertItem(13) 실행
    
  • FindNode의 첫 번째 Iteration 후
    
  • FindNode의 두 번째 Iteration 후
    
  • FindNode 세 번째 Iteration 후 최종 결과
    
• parentPtr 값이 NULL인 경우 item이 root
• item이 parentPtr 값보다 큰 경우 right child로 붙임
• item이 parentPtr 값보다 작은 경우 left child로 붙임

void TreeType::InsertItem(ItemType item)
{
	TreeNode* newNode;
	TreeNode* nodePtr;
	TreeNode* parentPtr;

	newNode = new TreeNode;
	newNode->info = item;
	newNode->left = NULL;
	newNode->right = NULL;

	FindNode(root, item, nodePtr, parentPtr);

	if (parentPtr == NULL)		// Insert as root.
		root = newNode;
	else if (item < parentPtr->info)
		parentPtr->left = newNode;
	else parentPtr->right = newNode;
}

DeleteItem

• Delete는 삭제해야 할 값 위치를 알려 주는 함수
• DeleteNode는 child node 수에 따라 경우를 나눠 노드들을 삭제해 주는 함수
• GetPredecessor는 child가 두 개인 노드를 삭제할 때 left tree의 most right node의 값을 찾아서 반환해 주는 함수
• item을 찾은 위치가 root라면 root만 삭제
• item을 찾은 위치가 parentPtr의 left child라면 left child 삭제
• item을 찾은 위치가 parentPtr의 right child라면 right child 삭제
• DeleteNode parameter로는 nodePtr 금지
  • &로 받기 때문에 parentPtr->left, parent->right로 넣어야 노드들이 자연스럽게 연결됨

void GetPredecessor(TreeNode* tree, ItemType& data);
void Delete(TreeNode*& tree, ItemType item);

void DeleteNode(TreeNode*& tree)
{
	ItemType data;
	TreeNode* tempPtr;

	tempPtr = tree;
	if (tree->left == NULL)
	{
		tree = tree->right;
		delete tempPtr;
	}
	else if (tree->right == NULL)
	{
		tree = tree->left;
		delete tempPtr;
	}
	else
	{
		GetPredecessor(tree->left, data);
		tree->info = data;
		Delete(tree->left, data);
	}
}

void Delete(TreeNode*& tree, ItemType item)
{
	if (item < tree->info)
		Delete(tree->left, item);   // Look in left subtree.
	else if (item > tree->info)
		Delete(tree->right, item);  // Look in right subtree.
	else
		DeleteNode(tree);           // Node found; call DeleteNode.
}

void GetPredecessor(TreeNode* tree, ItemType& data)
{
	while (tree->right != NULL)
		tree = tree->right;
	data = tree->info;
}

void TreeType::DeleteItem(ItemType item)
{
	TreeNode* nodePtr;
	TreeNode* parentPtr;

	FindNode(root, item, nodePtr, parentPtr);

	if (nodePtr == root)
		DeleteNode(root);
	else
		if (parentPtr->left == nodePtr)
			DeleteNode(parentPtr->left);
		else DeleteNode(parentPtr->right);
}

Plus

Big-O Comparison

Operation	Binary Search Tree	Array-based List	Linked List
Constructor	O(1)	O(1)	O(1)
Destructor	O(N)	O(1)	O(N)
IsFull	O(1)	O(1)	O(1)
IsEmpty	O(1)	O(1)	O(1)
RetrieveItem	O(logN)	O(logN)	O(N)
InsertItem	O(logN)	O(N)	O(N)
DeleteItem	O(logN)	O(N)	O(N)

Array Representation

• current node: tree.node[index]
• parent node: tree.node[(index-1) / 2]
• left child node: tree.node[index/2 + 1]
• right child node: tree.node[index/2 + 2]

LAB

PtrToSuccessor

• 트리 내의 가장 작은 키를 가진 노드를 찾고 트리에서 그 노드의 연결을 제거한 뒤 연결이 제거된 노드를 가리키는 포인터를 반환
• Recursive

TreeNode* TreeType::PtrToSuccessor(TreeNode*& tree)
{
	if (tree->left != NULL)
		PtrToSuccessor(tree->left);
	else
	{
		TreeNode* tempPtr = tree;
		tree = tree->right;
		return tempPtr;
	}
}

• Iterative

TreeNode* TreeType::PtrToSuccessor(TreeNode*& tree)
{
	while (tree->left == NULL)
		tree = tree->left;
	TreeNode* tempPtr = tree;
	tree = tree->right;
	return tempPtr;
}

isBST

• 해당 tree가 Binary Search Tree가 맞는지 검사하는 함수
• 단순히 현재 노드보다 작은 값은 left, 큰 값은 right에 있는지만 검사해선 안 됨 (아래 예시는 해당 조건을 만족하지만 BST가 아님)
  
• left tree의 most right node가 left tree의 parent보다 작은지 검사해야 함
• right tree의 most left node가 right tree의 parent보다 큰지 검사해야 함

bool Imp_IsBST(TreeNode* tree, ItemType& min, ItemType& max);

bool TreeType::IsBST() 
{
	ItemType min, max;
	return Imp_IsBST(root, min, max);
}

bool Imp_IsBST(TreeNode* tree, ItemType& min, ItemType& max) {
	bool isBST;
	if (tree == NULL)
		return true;

	if (tree->left != NULL) {
		char left_max = tree->info;
		isBST = Imp_IsBST(tree->left, min, left_max);

		if (!isBST || tree->info <= min || left_max > tree->info)
			return false;
	}

	if (tree->right != NULL) {
		char right_min = tree->info;
		isBST = Imp_IsBST(tree->right, right_min, max);

		if (!isBST || tree->info >= max || right_min < tree->info)
			return false;
	}

	min = (tree->left == NULL) ? tree->info : min;
	max = (tree->right == NULL) ? tree->info : max;
	return true;
}

• Level 1: Level 2의 재귀로 left tree를 보내고 left tree의 parent인 8을 left max로 전달
  
• Level 2: 전달받은 left max값이 max가 되고 Level 3의 재귀로 left tree 전달 후 left tree의 parent인 3을 left max로 전달
  
• Level 3: 전달받은 left max값이 max가 되고 Level 4의 재귀로 left tree 전달 후 left tree의 parent인 2를 left_max로 전달
  
• Level 4: 전달받은 left max 값이 max가 되고 더 이상 재귀가 호출되지 않아 min, max 업데이트 후 true return
  
• Level 3: parameter로 넣었던 left max가 1로 업데이트 되고 조건식 검사
  
• Level 3 : min, max 업데이트 후 true 반환
  
• Level 2: isBST가 true가 되고 parameter로 넣었던 left max가 level 3의 max인 2로 변경
  
• Left Tree 검사할 때
  • max: 현재 노드의 parent node
  • left_max: 현재 노드의 left tree의 최대값 (most right node)
• Right Tree 검사할 때
  • min: 현재 노드의 parent node
  • right_min: 현재 노드의 right tree의 최소값 (most left node)

  LeafCount

• BST의 leaf node 수 반환
• tree가 NULL이면 아무것도 아님
• tree의 left, right가 모두 NULL이면 tree는 leaf
• tree의 left, right 중 하나라도 NULL이 아니면 left tree의 leaf + right tree의 leaf 반환

int Imp_LeafCount(TreeNode* tree);

int TreeType::LeafCount()
{
	return Imp_LeafCount(root);
}

int Imp_LeafCount(TreeNode* tree)
{
	if (tree == NULL)
		return 0;
	else if (tree->left == NULL && tree->right == NULL)
		return 1;
	else
		return Imp_LeafCount(tree->left) + Imp_LeafCount(tree->right);
}

SingleParentCount

• BST의 노드 중 하나의 child만 가진 노드 수 반환
• tree가 0이면 0 반환
• tree의 left만 NULL이면 자기 자신 (1) + right tree 검사값 반환
• tree의 right만 NULL이면 자기 자신 (1) + left tree 검사값 반환
• tree의 left, right 모두 NULL이 아니면 left tree 검사값 + right tree 검사값 반환

int Imp_SingleParentCount(TreeNode* tree);

int TreeType::SimgleParentCount()
{
	return Imp_SingleParentCount(root);
}

int Imp_SingleParentCount(TreeNode* tree)
{
	if (tree == NULL)
		return 0;
	else if (tree->left == NULL && tree->right != NULL)
		return 1 + Imp_SingleParentCount(tree->right);
	else if (tree->left != NULL && tree->right == NULL)
		return 1 + Imp_SingleParentCount(tree->left);
	else
		return Imp_SingleParentCount(tree->left) + Imp_SingleParentCount(tree->right);
}

PtrToSuccess 이용한 DeleteNode

• PtrToSuccess: 최소값을 갖는 노드 반환해 주는 함수

TreeNode* TreeType::PtrToSuccessor(TreeNode*& tree)
{
	if (tree->left != NULL)
		PtrToSuccessor_re(tree->left);
	else
	{
		TreeNode* tempPtr = tree;
		tree = tree->right;
		return tempPtr;
	}
}

• DeleteNode 실행 시 left, right child를 모두 다 가지고 있는 경우라면 right tree의 최소값과 값 바꾸기
• PtrToSuccess의 return 값을 tree에 적용
• PtrToSuccess에 넣은 parameter는 최소값 노드의 right sub tree 가리킴

void DeleteNode(TreeNode*& tree)
{
	ItemType data;
	TreeNode* tempPtr;

	tempPtr = tree;
	if (tree->left == NULL)
	{
		tree = tree->right;
		delete tempPtr;
	}
	else if (tree->right == NULL)
	{
		tree = tree->left;
		delete tempPtr;
	}
	else
	{
		PtrToSuccess(tree->right, data);
		tree->info = data;
		Delete(tree->right, data);  // Delete predecessor node.
	}
}

Ancestor

• 현재 노드를 기준으로 조상 노드 출력
• Recursive

bool Imp_Ancestor_re(TreeNode* tree, ItemType value);

void TreeType::Ancestors_re(ItemType value)
{
	Imp_Ancestor_re(root, value);
}

bool Imp_Ancestor_re(TreeNode* tree, ItemType value)
{
	bool found = false;
	if (tree == NULL)
		return false;
	if (tree->info == value)
		return true;
	if (tree->info < value)
	{
		found = Imp_Ancestor_re(tree->right, value);
	}
	else
	{
		found = Imp_Ancestor_re(tree->left, value);
	}
	if (found)
	{
		std::cout << tree->info << std::endl;
		return found;
	}
}

• Iterative

void TreeType::Ancestors_iter(ItemType value)
{
	bool found = false;
	QueType path;
	TreeNode* currentNode = root;
	while (!found && currentNode == NULL)
	{
		if (currentNode->info == value)
			found = true;
		else
		{
			path.Enqueue(currentNode->info);
			if (value > currentNode->info)
				currentNode = currentNode->right;
			else
				currentNode = currentNode->left;
		}
	}
	if (found)
	{
		while (!path.IsEmpty())
		{
			ItemType item;
			path.Dequeue(item);
			std::cout << item << std::endl;
		}
	}
}

Smaller

• 트리내에서 Value 보다 작은 값을 갖는 노드의 수를 반환하는 클라이언트 함수
• IN_ORDER로 저장하면 item이 오름차순으로 Queue에 저장됨
• item에 Queue의 요소들을 차례차례 담아 오고, 이 값이 value보다 작다면 count++
• item 값이 value보다 큰 지점에서 finish 값을 바꿔 반복문 종료

int Smaller(TreeType tree, int value)
{
	ItemType item;
	bool finished = false;
	int count = 0;
	tree.ResetTree(IN_ORDER); // IN_ORDER는 Sorted 형태로 저장됨
	while (!finished)
	{
		tree.GetNextItem(item, IN_ORDER, finished);
		if (item < value)
			count++;
		else
			finished = true;
	}
	return count;
}

MakeTree

• SortedList를 tree로 만드는 작업
• SortedList 길이만큼 item_info에 값을 받아와서 tree에 Insert
• tree에 넣을 때 중간값인 mid부터 insert
  • 첫 번째 값부터 넣으면 깊이가 n인 비효율적 tree 생성
• right tree 생성은 from index를 mid + 1로 전달
• left tree 생성은 to index를 mid - 1로 전달

void AddElement(TreeType& tree, int Array[], int from, int to);
void MakeTree(TreeType& tree, SortedType<int>& list);

void AddElement(TreeType& tree, int Array[], int from, int to) {
	int mid;
	if (from <= to) {
		mid = (from + to) / 2;
		tree.InsertItem(Array[mid]);
		cout << Array[mid] << endl;
		AddElement(tree, Array, mid + 1, to);
		AddElement(tree, Array, from, mid - 1);
	}
}
void MakeTree(TreeType& tree, SortedType<int>& list) {

	int length = list.LengthIs();
	int* array = new int[length];
	int item_info;
	int i;

	list.ResetList();

	for (i = 0; i < length; i++) {
		list.GetNextItem(item_info);
		array[i] = item_info;
	}

	AddElement(tree, array, 0, length - 1);

	delete[] array;
}

PP

Recursive Binary Search Tree

class TreeNode:

    def __init__(self, info):
        self.info = info
        self.left = None
        self.right = None
    
class BST():

    def __init__(self):
        self.root = None
        self.order_list = []
    
    def is_empty(self):
        return (self.root == None)
    
    def count_nodes(self, tree):
        if (tree == None):
            return 0
        else:
            return 1 + self.count_nodes(tree.left) + self.count_nodes(tree.right)

    def length_is(self):
        return self.count_nodes(self.root)

    def insert(self, item):
        self.root = self.insert_item(self.root, item)
        return self.root is not None

    def insert_item(self, node, item):
        if node is None:
            node = TreeNode(item)
        else:
            if item <= node.info:
                node.left = self.insert_item(node.left, item)
            else:
                node.right = self.insert_item(node.right, item)
        return node
  
    def inorder(self, node):
        if(node != None) :
            self.inorder(node.left)
            self.order_list.append(node.info)
            self.inorder(node.right)
    
    def preorder(self, node):
        if(node != None):
            self.order_list.append(node.info)
            self.preorder(node.left)
            self.preorder(node.right)
    
    def postorder(self, node):
        if(node != None):
            self.postorder(node.left)
            self.postorder(node.right)
            self.order_list.append(node.info)

    def delete(self, item):
        self.root = self.delete_node(self.root, item)

    def delete_node(self, current, item):
        if (current == None):
            return current

        if ( item == current.info):
            if(current.left == None and current.right == None):
                current = None
            elif(current.left == None):
                current = current.right
            elif(current.right == None):
                current = current.left
            else:
                data = 0
                data = self.get_predecessor(data)
                current = TreeNode(data)
        elif ( item < current.info):
            current.left = self.delete_node(current.left, item)
        else:
            current.right = self.delete_node(current.right, item)
        return current

    def get_predecessor(tree, data):
        while(tree.right != None):
            tree = tree.right
        data = tree.info
        return data

Iterative Binary Search Tree

class NodeType:
    def __init__(self, data):
        self.info = data
        self.left = None
        self.right = None

class IterBST():
    def __init__(self):
        self.root = None
        self.order_list = []

    def insert(self, data):
        newnode = NodeType(data)
        parentPtr = self.find(data)
        if(parentPtr == None):
            self.root = newnode
        elif (data < parentPtr.info):
            parentPtr.left = newnode
        else:
            parentPtr.right = newnode

    def find(self, key):
        nodePtr, parentPtr, found = self.find_node(self.root, key)
        return parentPtr


    def find_node(self, root, key):
        nodePtr = root
        parentPtr = None
        found = False
        while(nodePtr != None and (not found)):
            if(key < nodePtr.info):
                parentPtr = nodePtr
                nodePtr = nodePtr.left
            elif (key > nodePtr.info):
                parentPtr = nodePtr
                nodePtr = nodePtr.right
            else:
                found = True
        return nodePtr, parentPtr, found

    def delete(self, key):
        self.root = self.delete_node(self.root, key)

    def delete_node(self, node, key):
        if (node == None):
            return node

        if (key == node.info):
            if(node.left == None and node.right == None):
                node = None
            elif(node.left == None):
                node = node.right
            elif(node.right == None):
                node = node.left
            else:
                data = 0
                data = self.get_predecessor(data)
                node = NodeType(data)
        elif (key < node.info):
            node.left = self.delete_node(node.left, key)
        else:
            node.right = self.delete_node(node.right, key)
        return node

        
    def inorder(self, node):
        if(node != None) :
            self.inorder(node.left)
            self.order_list.append(node.info)
            self.inorder(node.right)
    
    def preorder(self, node):
        if(node != None):
            self.order_list.append(node.info)
            self.preorder(node.left)
            self.preorder(node.right)
    
    def postorder(self, node):
        if(node != None):
            self.postorder(node.left)
            self.postorder(node.right)
            self.order_list.append(node.info)


    def get_predecessor(tree, data):
        while(tree.right != None):
            tree = tree.right
        data = tree.info
        return data