[자료구조] 트리 - Trees(Part 3)

2023-05-16 16 분 소요

트리 - Trees(Part 3)

아래까지 그림 첨부해야함

힙 - heaps

설명

큐 힙

힙에 새 엔트리 추가

1번 2번 따라서

힙에서 엔트리 제거

1번 2번 따라서

힙 구현

총총 및 실습

B-Trees

불균형 트리의 문제점

바이너리 서치 트리에서 1, 2, 3, …, 10을 더하는 경우
게속 오른쪽 하위트리가 생성된다.
따라서 BST의 장점을 살릴 수 없다.
이 경우 B-트리라고 하는 트리를 사용할 수 있다.(AVL tree, red-black tree)

B-tree

B-tree는 각 노드가 어떤 유형의 여러 엔트리를 보유할 수 있는 특별한 종류의 트리다.

엔트리 집합을 저장하도록 B-트리를 공식화할 수 있다.
대안으로, B-트리는 엔트리 백을 저장하도록 공식화될 수 있다.

B-tree Rule

단일 노드에 얼마나 많은 항목이 저장되는지를 결정하는 MININUM이라는 양의 정수가 있다.

Rule1

루트는 하나의 항목만 가질 수 있다(children이 없다면).
다른 모든 노드에는 최소한 MININUM 항목이 있다.

Rule2

노드의 최대 항목 수는 MINIMUM 값의 두 배입니다.

Rule3

각 B-트리 노드의 항목은 부분적으로 채워진 array에 저장되며 가장 작은 항목(인덱스 0)에서 가장 큰 항목(최종 사용된 인덱스)으로 정렬된다.

Rule4

리프가 아닌 노드 아래의 하위 트리 수는 항상 노드의 항목 수보다 하나 많다.
ex. 42개의 항목이 있는 B-트리 노드는 왼쪽에서 오른쪽으로 하위 트리 0, 하위 트리 1, …, 하위 트리 42 등 43개의 하위 트리를 갖는다.

Rule5

리프가 아닌 노드의 경우
(a) 인덱스 i에 있는 항목은 노드의 하위 트리 번호 i에 있는 모든 항목보다 크다.
(b) 인덱스 i에 있는 항목은 노드의 하위 트리 번호 i+1에 있는 모든 항목보다 작다.

Rule6

B-트리의 모든 리프는 동일한 깊이를 가진다.

Set ADT with B-trees

B-트리를 사용하는 세트(템플릿) 클래스

엔트리 사이사이에 subtree를 갖고있다. 그림

비공개 멤버 상수/변수

static const size_t MINIMUM = 200 ;
static const size_t MAXIMUM = 2 * MINIMUM ;
size_t data_count ;
Item data[MAXIMUM+1] ;
size_t child_count ;
set* subset[MAXIMUM+2] ;

B-Tree를 사용하는 set 함수

b-tree의 개념과 insert만 숙지하자

아래 B-tree의 함수들을 확인해본다.

count function (searching for an item in a B-tree)

루트에서 data[i]가 target보다 크거나 같은 첫 번째 인덱스 i를 찾는다.
If (대상이 data[i]에서 발견되면) return 1 ;
else if(루트에 자식이 없는경우) return 0 ;
else return subset[i]->count(target) ;

insert function (searching for an item in a B-tree)

insert할때 두 가지 private 기능을 사용(loose_insert and fix_excess)
loose_insert는 다음을 사용하여 B-트리에 새 항목을 추가
루트가 MAXIMUM+1 항목을 가질 수 있는 가능성
fix_excess는 하위 트리의 루트에 있는 추가 항목(있는 경우)을 처리

그림 추가55p

loose_insert function

루트가 하나의 추가 항목을 가질 수 있는 방식으로 B-트리에 항목을 삽입

In the root, find the first index i such that data[i] >= entry
If (entry is found at data[i]) return false;
else if (루트에 자식이 없는경우) insert the entry to the root at data[i] and return true ;
else { 재귀 호출을 수행하고 초과 문제를 해결 }

4.1 bool b = subset[i]->loose_insert(entry) ;
4.2 check if the root of subset[i] now has an excess entry ;
4.3 If so, fix the subset[i] using the fix_excess function;
4.4 return b ;

그림 추가58p

fix_excess function

루트 노드에 일반 B-트리에 대한 추가 항목이 있는 하위 트리(세미-B-트리)를 만듬

항목이 MAXIMUM+1인 노드를 각각 MINIMUM 항목이 포함된 두 개의 노드로 분할
중간에 있는 항목이 상위로 이동

최종 insert funtion

If ( ! loose_insert(entry) )
return false // since entry wasn’t added
If (data_count > MAXIMUM)
fix the root of the entire tree
return true

전체트리의 루트를 수정하는 법

항목이 없는 새 루트를 만들고 이전 루트를 새 루트의 자식으로 만ema
이전 루트에서 fix_excess를 호출

erase funtion

erase는 B-tree에서 항목을 제거하는 funtion이다.

loose_erase 및 fix_shortage 두 가지 private를 사용한다.
loose_erase는 루트에 0개의 항목이 있거나(하나의 하위 항목 포함) 내부 하위 트리의 루트에 최소 항목보다 적은 항목이 있을 수 있는 B-트리에서 항목을 제거
fix_shortage는 하위 트리의 루트에 있는 항목(있는 경우)의 부족을 처리

If ( ! loose_erase(target) )
return false // 대상이 제거되지 않았기 때문에
If ((data_count == 0) && (child_count ==1))
fix the root of the entire tree
return true

loose_erase funtion

루트가 하나의 항목을 너무 적게 가질 수 있는 방식으로 B-트리에서 항목을 제거합니다.
루트에서 data[i] >= entry를 만족하는 인덱스i를 찾는다.
a : 루트에 자식이 없고 타겟을 찾을 수 없으면 false를 return
b : 루트에 자식이 없고 타겟을 찾았으면(leaf) 대상을 제거하고 true를 return
c : else - 루트에 자식이 있는경우
c1 : 루트에 자식이 있고 타겟을 찾을 수 없는 경우
c1 : bool b = subset[i]->loose_erase(target) ;
c1 : Check if the root of subset[i] has MINIMUM-1 entries
c1 : 그렇다면 fix_shortage 함수를 사용하여 subset[i]을 수정합니다.
c2 : 루트에 자식이 있고 타겟이 발견된 경우
subset[i]-> remove_biggest (data[i]) ;
if (subset[i]->data_count < MINIMUM)
fix_shortage(i) ;
return true ;

fix_shortage funtion

Subset[i] has only MINIMUM-1 entries인 경우

a : Transfer an extra entry from subset[i-1]
b : Transfer an extra entry from subset[i+1]
c : Combine subset[i] with subset[i-1]
d : Combine subset[i] with subset[i+1]

remove_biggest funtion

루트가 하나의 항목을 너무 적게 가질 수 있는 방식으로 B-트리에서 가장 큰 항목을 제거합니다.

If the root has no children, copy the last item of data into removed_entry and reduce data_count by 1.
If it has children, remove the biggest item from the rightmost child:
subset[child_count-1]->remove_biggest(removed_entry);
fix_shortage(child_count-1);

실습

items.template, items.h, set.h, set.cpp, test.cpp 총 5개 파일을 가지고 실습

items.h

// FILE: item.h
#ifndef ITEMS_H  // Prevent duplicate definition
#define ITEMS_H
#include <stdlib.h> // Provides size_t type

	// FUNCTIONS for the item toolkit
template <class Item>
Item maximal(Item a, Item b);

template <class Item>
void swap(Item& x, Item& y);

template <class Item, class SizeType>
size_t index_of_maximal(Item data[], SizeType n);

template <class Item, class SizeType>
void ordered_insert(Item data[], SizeType n, Item entry);

template <class Item, class SizeType>
void attach_item(Item data[], SizeType& n, const Item& entry);

template <class Item, class IndexType, class SizeType>
void insert_item(Item data[], IndexType i, SizeType& n, Item entry);

template <class Item, class SizeType>
void detach_item(Item data[], SizeType& n, Item& entry);

template <class Item, class IndexType, class SizeType>
void delete_item(Item data[], IndexType i, SizeType& n, Item& entry);

template <class Item, class SizeType>
void merge(Item data1[], SizeType& n1, Item data2[], SizeType& n2);

template <class Item, class SizeType>
void split(Item data1[], SizeType& n1, Item data2[], SizeType& n2);

#include "items.template" // Include the implementations    
#endif

items.template

// FILE: item_tpl.cxx
#include <assert.h>    // Provides assert
#include <stdlib.h>    // Provides size_t

template <class Item>
Item maximal(Item a, Item b)
{
    if (a > b)
        return a;
    else
    return b;
}

template <class Item>
void swap(Item& x, Item& y)
{
    Item temp;

    temp = x;
    x = y;
    y = temp;
}

template <class Item, class SizeType>
size_t index_of_maximal(Item data[ ], SizeType n)
// Library facilities used: assert.h, stdlib.h
{
    size_t answer;
    size_t i;

    assert(n > 0);
    answer = 0;

    for (i = 1; i < n; i++)
    {
        if (data[answer] < data[i])
        answer = i;
        // data[answer] is now biggest from data[0]..data[i]
    }

    return answer;
}

template <class Item, class SizeType>
void ordered_insert(Item data[ ], SizeType n, Item entry)
// Library functions used: stdlib.h
{
    size_t i;

    for (i = n; (i > 0) && (entry < data[i-1]); i--)
        data[i] = data[i-1];

    data[i] = entry;
}
    
template <class Item, class SizeType>
size_t first_ge(const Item data[ ], SizeType n, const Item& entry)
// Library functions used: stdlib.h
{
    size_t i;

    for (i = 0; (i < n) && !(data[i] >= entry); i++);
  
    return i;
}

template <class Item, class SizeType>
void attach_item(Item data[ ], SizeType& n, const Item& entry)
{
    data[n++] = entry;
}

template <class Item, class IndexType, class SizeType>
void insert_item(Item data[ ], IndexType i, SizeType& n, Item entry)
{
    size_t shift_index;

    for (shift_index = n; shift_index > i; shift_index--)
        data[shift_index] = data[shift_index-1];
    data[i] = entry;
    n++;
}

template <class Item, class SizeType>
void detach_item(Item data[ ], SizeType& n, Item& entry)
{
    entry = data[--n];
}

template <class Item, class IndexType, class SizeType>
void delete_item(Item data[ ], IndexType i, SizeType& n, Item& entry)
{
    size_t shift_index;

    entry = data[i];
    for (shift_index = i+1; shift_index < n; shift_index++)
        data[shift_index-1] = data[shift_index];

    n--;
}

template <class Item, class SizeType>
void merge(Item data1[ ], SizeType& n1, Item data2[ ], SizeType& n2)
{
    size_t i;

    for (i = 0; i < n2; i++)
        data1[n1 + i] = data2[i];
    n1 += n2;
    n2 = 0;
}

template <class Item, class SizeType>
void split(Item data1[ ], SizeType& n1, Item data2[ ], SizeType& n2)
{
    size_t i;
    size_t new_size1;

    new_size1 = n1 - n1/2;
    
    for (i = 0; i < n1/2; i++)
        data2[n2 + i] = data1[new_size1 + i];

    n2 += n1/2;
    n1 = new_size1;
}

set.h

// FILE: set.h
#ifndef SET_H
#define SET_H

#include <stdlib.h>   // Provides size_t

class Set
{
public:
	// TYPEDEF
	typedef double Item;
	// CONSTRUCTORS and DESTRUCTOR
	Set();
	Set(const Set& source);
	~Set() { clear(); }
	// MODIFICATION functions
	void operator =(const Set& source);
	void clear();
	void insert(const Item& entry);
	void remove(const Item& target);
	// CONSTANT functions
	bool contains(const Item& target) const;
	bool is_empty() const { return (data_count == 0); }
	// SUGGESTED FUNCTION FOR DEBUGGING
	void print(int indent) const;
private:
	// MEMBER CONSTANTS--make these smaller to debug, then change them back
	static const size_t MINIMUM = 1;
	static const size_t MAXIMUM = 2 * MINIMUM;
	// MEMBER VARIABLES
	size_t data_count;
	Item data[MAXIMUM + 1];
	size_t child_count;
	Set *subset[MAXIMUM + 2];
	// HELPER MEMBER FUNCTIONS
	bool is_leaf() const { return (child_count == 0); }
	void loose_insert(const Item& entry);
	void loose_remove(const Item& entry);
	void remove_biggest(Item& removed_entry);
	void fix_excess(size_t i);
	void fix_shortage(size_t i);
	void transfer_left(size_t i);
	void transfer_right(size_t i);
	void merge_with_next_subset(size_t i);
};

#endif

set.cpp

// FILE: set.cxx
// CLASS IMPLEMENTED: Set (see set.h for documentation)
// INVARIANT for the Set ADT:
//   1. The items of the set are stored in a B-tree, satisfying the six
//      B-tree rules.
//   2. The number of entries in the tree's root is in the member variable
//      data_count, and the number of subtrees of the root is stored in the
//      member variable child_count.
//   3. The root's entries are stored in data[0] through data[data_count-1].
//   4. If the root has subtrees, then these subtrees are stored in the Sets
//      *subset[0] through *subset[child_count-1].
//
// FOR REFERENCE, THE SIX B-tree Rules:
//   B-tree Rule 1: Unless the whole set is empty, the root has at least one
//                  entry; every other node has at least MINIMUM entries.
//   B-tree Rule 2: The maximum number of allowed entries in a node is
//                  MAXIMUM (which is equal to 2*MINIMUM).
//   B-tree Rule 3: The entries of each node are sorted from the smallest entry
//                  (at data[0]) to the largest entry (at data[data_count-1]).
//   B-tree Rule 4: The number of subtrees below a non-leaf node is always one
//                  more than the number of entries in the node.
//   B-tree Rule 5: For any non-leaf node: (a) data[i] is greater than all the
//                  entries in subset[i], and (b) data[i] is less than all the
//                  entries in subset[i+1].
//   B-tree Rule 6: All leaves are at the same depth.

#include <iostream>
#include <iomanip>
#include "stdlib.h" // Provides size_t
#include "set.h"
#include "items.h"  // Has first_ge, merge, split, various *_item functions
using namespace std;

Set::Set()
{
	data_count = 0;
	child_count = 0;
}

Set::Set(const Set& source)
{
	size_t i;

	data_count = source.data_count;
	for (i = 0; i < data_count; i++)
		data[i] = source.data[i];
	child_count = source.child_count;
	for (i = 0; i < child_count; i++)
		subset[i] = new Set(*(source.subset[i]));
}

void Set::operator =(const Set& source)
{
	size_t i;

	if (this != &source)
	{
		clear();
		data_count = source.data_count;
		for (i = 0; i < data_count; i++)
			data[i] = source.data[i];
		child_count = source.child_count;
		for (i = 0; i < child_count; i++)
			subset[i] = new Set(*(source.subset[i]));
	}
}

void Set::clear()
{
	size_t i;

	for (i = 0; i < child_count; i++)
		delete subset[i];
	child_count = 0;
	data_count = 0;
}

void Set::insert(const Item& entry)
{
	size_t i;
	Set* grow_ptr;

	loose_insert(entry);
	if (data_count > MAXIMUM)
	{   // Split the root node into two
		grow_ptr = new Set;
		grow_ptr->data_count = data_count;
		for (i = 0; i < data_count; i++)
			grow_ptr->data[i] = data[i];
		grow_ptr->child_count = child_count;
		for (i = 0; i < child_count; i++)
			grow_ptr->subset[i] = subset[i];
		data_count = 0;
		child_count = 1;
		subset[0] = grow_ptr;
		fix_excess(0);
	}
}

void Set::remove(const Item& target)
{
	size_t i;
	Set* shrink_ptr;

	loose_remove(target);
	if (child_count == 1)
	{   // Remove the root with zero entries and one child
		shrink_ptr = subset[0];
		data_count = shrink_ptr->data_count;
		for (i = 0; i < data_count; i++)
			data[i] = shrink_ptr->data[i];
		child_count = shrink_ptr->child_count;
		for (i = 0; i < child_count; i++)
			subset[i] = shrink_ptr->subset[i];
		shrink_ptr->child_count = 0;
		delete shrink_ptr;
	}
}

bool Set::contains(const Item& target) const
{
	size_t i;
	bool found;

	i = first_ge(data, data_count, target);
	found = (i < data_count) && (target == data[i]);

	if (found)
		return true;
	else if (is_leaf())
		return false;
	else
		return subset[i]->contains(target);
}

void Set::print(int indent) const
{
	size_t i;
	if (child_count > 0)
		subset[child_count - 1]->print(indent + 4);
	for (i = data_count; i > 0; i--)
	{
		cout << setw(indent) << "" << data[i - 1] << endl;
		if (child_count > 0)
			subset[i - 1]->print(indent + 4);
	}
}

// HELPER FUNCTIONS 
// The helper functions are below with precondition/postcondition contracts.

void Set::loose_insert(const Item& entry)
// Precondition:
//   The entire B-tree is valid.
// Postcondition:
//   If entry was already in the set, then the set is unchanged. Otherwise,
//   entry has been added to the set, and the entire B-tree is still valid
//   EXCEPT that the number of entries in the root of this set might be one
//   more than the allowed maximum.
{
	size_t i;
	bool found;

	i = first_ge(data, data_count, entry);
	found = (i < data_count) && (entry == data[i]);

	if ((!found) && is_leaf())
		insert_item(data, i, data_count, entry);
	else if (!found)
	{
		subset[i]->loose_insert(entry);
		if (subset[i]->data_count > MAXIMUM)
			fix_excess(i);
	}
}

void Set::loose_remove(const Item& target)
// Precondition:
//   The entire B-tree is valid.
// Postcondition:
//   If target was in the set, then it has been removed from the set; otherwise
//   the set is unchanged. The entire B-tree is still valid EXCEPT that the
//   number of entries in the root of this set might be one less than the
//   allowed minimum.
{
	size_t i;
	Item temp_entry;
	bool found;

	i = first_ge(data, data_count, target);
	found = (i < data_count) && (data[i] == target);

	if (is_leaf() && found)
		delete_item(data, i, data_count, temp_entry);
	else if (!is_leaf())
	{
		if (found)
			subset[i]->remove_biggest(data[i]);
		else
			subset[i]->loose_remove(target);
		if (subset[i]->data_count < MINIMUM)
			fix_shortage(i);
	}
}

void Set::remove_biggest(Item& removed_entry)
// Precondition: 
//   (data_count > 0) and the entire B-tree is valid.
// Postcondition:
//   The largest item in the set has been removed, and removed_entry has been
//   set equal to a copy of this removed item. The B-tree is still valid EXCEPT
//   that the number of entries in the root of this set might be one less than
//   the allowed minimum.
{
	size_t i;

	if (is_leaf())
		detach_item(data, data_count, removed_entry);
	else
	{   // Continue search for biggest item down the rightmost branch
		i = child_count - 1;
		subset[i]->remove_biggest(removed_entry);
		if (subset[i]->data_count < MINIMUM)
			fix_shortage(i);
	}
}

void Set::fix_excess(size_t i)
// Precondition: 
//   (i < child_count) and the entire B-tree is valid EXCEPT that
//   subset[i] has MAXIMUM + 1 entries. Also, the root is allowed to have
//   zero entries and one child.
// Postcondition: 
//   The tree has been rearranged so that the entire B-tree is valid EXCEPT
//   that the number of entries in the root of this set might be one more than
//   the allowed maximum.
{
	Item temp_entry;

	// Insert a new subset at subset[i+1], and split subset[i]'s subsets
	insert_item(subset, i + 1, child_count, new Set);
	split(subset[i]->subset, subset[i]->child_count, subset[i + 1]->subset, subset[i + 1]->child_count);

	// Split subset[i]'s data
	split(subset[i]->data, subset[i]->data_count, subset[i + 1]->data, subset[i + 1]->data_count);

	// Move the median entry from subset[i] up to data[i].
	detach_item(subset[i]->data, subset[i]->data_count, temp_entry);
	insert_item(data, i, data_count, temp_entry);
}

void Set::fix_shortage(size_t i)
// Precondition: 
//   (i < child_count) and the entire B-tree is valid EXCEPT that
//   subset[i] has only MINIMUM - 1 entries.
// Postcondition: 
//   The tree has been rearranged so that the entire B-tree is valid EXCEPT
//   that the number of entries in the root of this set might be one less than
//   the allowed minimum.
{
	if ((i > 0) && (subset[i - 1]->data_count > MINIMUM))
		transfer_right(i - 1);
	else if ((i + 1 < child_count) && (subset[i + 1]->data_count > MINIMUM))
		transfer_left(i + 1);
	else if (i + 1 < child_count)
		merge_with_next_subset(i);   // Merge subset[i] with subset[i+1]
	else
		merge_with_next_subset(--i); // Merge subset[i-1] with subset[i]
}

void Set::merge_with_next_subset(size_t i)
// Precondition: 
//   (i+1 < child_count) and the entire B-tree is valid EXCEPT that the total
//   number of entries in subset[i] and subset[i+1] is 2*MINIMUM - 1.
// Postcondition: 
//   subset[i] and subset[i+1] have been merged into one subset (now at
//   subset[i]), and data[i] has been passed down to be the median entry of the
//   new subset[i]. As a result, the entire B-tree is valid EXCEPT that the
//   number of entries in the root of this set might be one less than the
//   allowed minimum.
{
	Item temp_entry;
	Set* temp_ptr;

	// Shift an entry from data[i] down to end of subset[i]
	delete_item(data, i, data_count, temp_entry);
	attach_item(subset[i]->data, subset[i]->data_count, temp_entry);

	// Shift all entries from subset i+1 to right end of subset i;
	merge(subset[i]->data, subset[i]->data_count, subset[i + 1]->data, subset[i + 1]->data_count);

	// Shift all subsets of subset i+1 to right end of subset i;
	merge(subset[i]->subset, subset[i]->child_count, subset[i + 1]->subset, subset[i + 1]->child_count);

	// Get rid of subset i+1 in my own subset array
	delete_item(subset, i + 1, child_count, temp_ptr);
	delete temp_ptr;
}

void Set::transfer_right(size_t i)
// Precondition: 
//   (i+1 < child_count) and (subset[i]->data_count > MINIMUM)
//   and the entire B-tree is valid EXCEPT that
//   subset[i] has only MINIMUM - 1 entries.
// Postcondition: One entry has been shifted from the end of subset[i] up to
//   data[i], and the original data[i] has been shifted down to the first entry
//   of subset[i+1]. Also, if subset[i] is not a leaf, then its last subset has
//   been transfered over to be the first subset of subset[i+1].
//   As a result, the entire B-tree is now valid.
{
	// If necessary, shift last subset of subset[i] to front of subset[i+1]
	if (!subset[i]->is_leaf())
	{
		Set* grandchild;
		detach_item(subset[i]->subset, subset[i]->child_count, grandchild);
		insert_item(subset[i + 1]->subset, (unsigned int)0, subset[i + 1]->child_count, grandchild);
	}

	// Copy an entry from data[i] down to front of subset[i+1]
	insert_item(subset[i + 1]->data, (unsigned int)0, subset[i + 1]->data_count, data[i]);

	// Transfer last entry of subset[i] up to replace data[i]
	detach_item(subset[i]->data, subset[i]->data_count, data[i]);
}

void Set::transfer_left(size_t i)
// Precondition: 
//   (0 < i < child_count) and (subset[i]->data_count > MINIMUM)
//   and the entire B-tree is valid EXCEPT that
//   subset[i-1] has only MINIMUM - 1 entries.
// Postcondition:
//   One entry has been shifted from the front of subset[i] up to
//   data[i-1], and the original data[i-1] has been shifted down to the last
//   entry of subset[i-1]. Also, if subset[i] is not a leaf, then its first
//   subset has been transfered over to be the last subset of subset[i-1].
//   As a result, the entire B-tree is now valid.
{
	// If necessary, shift first subset of subset[i] to end of subset[i-1]
	if (!subset[i]->is_leaf())
	{
		Set* grandchild;
		delete_item(subset[i]->subset, 0, subset[i]->child_count, grandchild);
		attach_item(subset[i - 1]->subset, subset[i - 1]->child_count, grandchild);
	}

	// Copy an entry from data[i] down to end of subset[i-1]
	attach_item(subset[i - 1]->data, subset[i - 1]->data_count, data[i - 1]);

	// Transfer first entry of subset[i] up to replace data[i-1]
	delete_item(subset[i]->data, 0, subset[i]->data_count, data[i - 1]);
}

test.cpp

#include <iostream>
#include "set.h"
using namespace std;

int main(void)
{
	Set s1;
	s1.insert(17); s1.insert(4); s1.insert(12); s1.insert(19); s1.insert(22); s1.insert(6);
	s1.print(0); cout << "-----------" << endl;
	s1.insert(18);
	s1.print(0); cout << "-----------" << endl;
	s1.remove(6);
	s1.print(0); cout << "-----------" << endl;
	return 0;
}

결과

Twitter Facebook LinkedIn

[자료구조] 트리 - Trees(Part 3)

트리 - Trees(Part 3)

힙 - heaps

힙에 새 엔트리 추가

힙에서 엔트리 제거

힙 구현

총총 및 실습

B-Trees

B-tree

B-tree Rule

Set ADT with B-trees

B-Tree를 사용하는 set 함수

insert function (searching for an item in a B-tree)

erase funtion

실습

공유하기

댓글남기기

참고

[알고리즘] 입출력과 사칙연산

[파이썬] Data Structures

[파이썬] Replti을 이용해 파이썬 기초 배우기

[자료구조] Graphs