CH 08 Binary Search Tree

127212 단어 python 자료구조 C C

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

Author And Source

이 문제에 관하여(CH 08 Binary Search Tree), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@morion002/CH-08-Binary-Search-Tree

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

7_ TDD로 하는 API 서버 개발

2021-12-10 BE

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다