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

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