Binary Search Tree

ilustrasi penyisipan/insert data ke pohon

ilustrasi pencarian/search data di dalam pohon

ilustrasi penghapusan data dari sebuah cabang yang memiliki 2 sub cabang

Dahulu kala, pernah membuat sebuah pengembangan materi struktur data, ada beberapa source code yang sudah ada dan jalan. Nah, dibuatlah pengembangan untuk binary search tree disertai dengan simulasinya (meskipun sederhana dan banyak batasan) yang cukup membantu dalam memperlajari/memahami binary search tree. Selamat Belajar. Hehehe.
-----------------------------------------------------------------------------------------
di bawah ini adalah main function
-----------------------------------------------------------------------------------------
bst.cpp

// test binary search tree class

#include <iostream.h>
#include "bst.h"
#include "datatype.h"

/* program ini dibuat untuk mensimulasikan BinarySearch Tree */
/* masukkanlah data yang sederhana, tetapi mewakili dan seperlunya */
/* data sebaiknya tidak lebih dari 4 digit */
/* kedalaman / ketinggian pohon biner sebaiknya tidak lebih dari 5 */
/* semua dilakukan demi kenyamanan simulasi (karena keterbatasan layar) */

BSTree<DataType,int> y;

void main(void)
{
DataType s;
DataType q;
int c;
q.key = 11; q.ID = 'a'; y.Insert(q);
q.key = 6; q.ID = 'b'; y.Insert(q);
q.key = 13; q.ID = 'c'; y.Insert(q);
q.key = 15; q.ID = 'd'; y.Insert(q);
q.key = 8; q.ID = 'e'; y.Insert(q);
q.key = 12; q.ID = 'f'; y.Insert(q);
q.key = 9; q.ID = 'g'; y.Insert(q);
q.key = 9; q.ID = 'h'; y.Insert(q);
q.key = 14; q.ID = 'i'; y.Insert(q);
q.key = 20; q.ID = 'j'; y.Insert(q);
q.key = 4; q.ID = 'k'; y.Insert(q);
q.key = 5; q.ID = 'k'; y.Insert(q);
q.key = 7; q.ID = 'k'; y.Insert(q);
q.key = 3; q.ID = 'k'; y.Insert(q);
getch();
y.Search(20,s);
y.Search(9,s);
y.Search(4,s);
y.Search(6,s); // baru nyoba sampai search
gotoxy(15,15); cout << "Elements in ascending order are" << endl;
gotoxy(15,16); y.Ascend();
y.Delete(11,s);
y.Ascend();
}

-----------------------------------------------------------------------------------------
di bawah ini adalah hasil modifikasi/pengembangan (method asli dijadikan komentar)
-----------------------------------------------------------------------------------------
datatype.h

#ifndef DataType_
#define DataType_

class DataType {
friend void main(void);
friend ostream& operator<<(ostream&, DataType);
public:
operator int() const {return key;}
private:
int key; // element key
char ID; // element identifier
};

ostream& operator<<(ostream& out, DataType x)
{out << x.key << x.ID; return out;}

#endif
/* yang asli
ostream& operator<<(ostream& out, DataType x)
{out << x.key << ' ' << x.ID << ' '; return out;}
*/

bst.h

// unbalanced binary search trees
#ifndef BSTree_
#define BSTree_
#define true 1
#define false 0

#include <conio.h>
#include "binary.h"
#include "xcept.h"

template<class E, class K>
class BSTree : public BinaryTree<E> {
public:
int Search(const K& k, E& e) const;
BSTree<E,K>& Insert(const E& e);
BSTree<E,K>& InsertVisit(const E& e, void(*visit)(E& u));
BSTree<E,K>& Delete(const K& k, E& e);
void Ascend() {InOutput(); ye++;}
private:
int ye;
};

template<class E, class K>
int BSTree<E,K>::Search(const K& k, E &e) const
{ /* Mencari elemen yang cocok dengan k */
/* pointer p mulai dari root */
/* deklarasi variabel */
int x = 30, y = 4; /* koordinat awal root */
int z = 16; /* jarak antar sub cabang dalam simulasi */

gotoxy(1,1); cout << "Keterangan : Searching " << k << " ";
BinaryTreeNode<E> *p = root;
gotoxy(x,y);
/* periksa p->data, apakah ada yang sama dengan k ? */
while(p) { if(k < p->data) { p = p->LeftChild;
cout << "?";
getch();
gotoxy(x+1,y); cout << "> " << k;
getch();
gotoxy(x,y); cout << " ";
gotoxy(x-=z,y+=1);
}
else if (k > p->data) { p = p->RightChild;
cout << "?";
getch();
gotoxy(x+1,y); cout << "< " << k;
getch();
gotoxy(x,y); cout << " ";
gotoxy(x+=z,y+=1);
}
else { /* elemen ditemukan (k == p-> data) */
gotoxy(x,y); cout << '?';
getch();
gotoxy(x+1,y); cout << "=" << k;
getch();
gotoxy(x,y); cout << " ";
e = p->data;
return true;
}
z=z/2;
}
/* jika tidak ketemu */
gotoxy(1,ye+1); cout << "??????????????<? " << k << " ?>???????????????????";
getch();
/* menghapus jika tidak ketemu */
gotoxy(1,ye+1); cout << " ";
return false;
}

template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
{ /* memasukkan e jika tidak duplicate */
/* deklarasi variabel */
int z=16; /* jarak antar sub root atau daun */
int k = -4; /* untuk spasi penulisan -> ?????tChild baris 2 & 3 */
int x = 30, y = 4; /* koordinat awal, letak root */
bool duplicate = false; /* untuk mengetahui duplicate atau tidak */
int arahpp; /* -1 = kiri, 1 = kanan */

gotoxy(1,1); cout << "Keterangan : Inserting " << e;
/* deklarasi pointer */
BinaryTreeNode<E> *p = root, /* pointer p pada awalnya menunjuk ke root */
*pp = 0; /* parent dari p */

/* memeriksa p -> data, berhenti jika p = 0 atau p -> data == e */
gotoxy(1,2);cout << "pp = 0";
gotoxy(1,3);cout << "p = root";
while (p) { pp = p;
/* p bergerak ke cabang */
/* mencetak keterangam pada pp = p -> */
if(pp != root)
{ if(arahpp == -1) { gotoxy(k,2);
cout << " -> LeftChild";
}
if(arahpp == 1) { gotoxy(k,2);
cout << " -> RightChild";
}
}
gotoxy(1,2);cout << "pp = root";
/* mencetak keterangam pada p = p -> */
if(e < p->data) { p = p -> LeftChild;
arahpp = -1;
gotoxy(k+=14,3); cout << " -> LeftChild";
gotoxy(x-=z,y+=1); cout << e << "<";
gotoxy(x+z,y-1); cout << " ";
getch();
}
else
if(e > p->data) { p = p -> RightChild;
arahpp = 1;
gotoxy(k+=14,3);
cout << " -> RightChild";
gotoxy(x+=z,y+=1); cout << "<" << e;
gotoxy(x-z,y-1); cout << " ";
getch();
}
else
if(e == p-> data) { /* duplicate */
p = 0;
duplicate = true;
}
z=z/2;
}

/* memasukkan data menjadi daun dalam simulasi*/
if(!duplicate)
{ /* memasukkan e ke dalam pohon (menjadi daun) dalam simulasi */
gotoxy(x,y+=1);
cout << e;
/* menghapus data sebelum menjadi daun (tepat di atas daun) dalam simulasi */
gotoxy(x,y-1); cout << " ";
cout << endl;
getch();
}
else { /* menghapus data di atas daun yang duplicate dalam simulasi */
gotoxy(x,y); cout << " ";
getch();
}

/* mendapatkan node dari e (data yang di-insert) dan di-attach ke pp */
BinaryTreeNode<E> *r = new BinaryTreeNode<E> (e);
/* jika root != 0 & tidak duplicate*/
if(root && !duplicate) { gotoxy(k,2);
if(e < pp->data) { pp->LeftChild = r;
cout << " -> LeftChild";
}
else { pp->RightChild = r;
cout << " -> RightChild";
}
cout << " -> data = " << e;
}
/* jika duplicate */
else if(duplicate) { pp = 0;
gotoxy(k+15,2);
cout << "<Duplicate>";
}
/* jika root == 0 */
else { root = r;
gotoxy(10,2);
cout << " = " << e;
}

if(y > ye) ye = y; /* mencari nilai y tertinggi */
gotoxy(1,ye);
getch();
/* menghapus keterangan data yang di-insert pada baris 1 dalam simulasi*/
gotoxy(24,1); cout << " ";
/* menghapus setelah pp = p -> pada baris ke-2 pada simulasi */
gotoxy(6,2);
for(int i=0; i < k + 22; i++)
cout << ' ';
/* menghapus setelah p = p -> pada baris ke-3 pada simulasi */
gotoxy(6,3);
for(int i=0; i < k + 22; i++)
cout << ' ';
return *this;
}

template<class E, class K>
BSTree<E,K>& BSTree<E,K>::InsertVisit(const E& e, void(*visit)(E& u))
{// Insert e if not duplicate.
// Visit e if duplicate.

// search for a matching element
BinaryTreeNode<E> *p = root, // search pointer
*pp = 0; // parent of p
while (p) {// examine p->data
pp = p;
if (e < p->data) p = p->LeftChild;
else if (e > p->data) p = p->RightChild;
else {// duplicate
visit(p->data);
return *this;};
}

// not a duplicate
// get a node for e and attach to pp
BinaryTreeNode<E> *r = new BinaryTreeNode<E> (e);
if (root) {// tree not empty
if (e < pp->data) pp->LeftChild = r;
else pp->RightChild = r;}
else // insertion into empty tree
root = r;

return *this;
}

template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Delete(const K& k, E& e)
{ // Delete element with key k and put it in e.
int x = 30, y = 4; /* koordinat awal root */
int z = 16; /* jarak antar sub cabang dalam simulasi */

gotoxy(1,1); cout << "Keterangan : Deleting " << k << " ";
gotoxy(x,y);
// set p to point to node with key k
BinaryTreeNode<E> *p = root, *pp = 0; // parent of p
while (p && p->data != k)// move to a child of p
{ pp = p;
if (k < p->data) { p = p->LeftChild;
cout << "?";
getch();
gotoxy(x+1,y);
cout << "> " << k; getch();
gotoxy(x,y); cout << " ";
gotoxy(x-=z,y+=1);
}
else { p = p->RightChild;
cout << "?";
getch();
gotoxy(x+1,y); cout << "< " << k;
getch();
gotoxy(x,y); cout << " ";
gotoxy(x+=z,y+=1);
}
z = z/2;
}

if(p) { gotoxy(x,y); cout << '?';
getch();
gotoxy(x+1,y); cout << "=" << k;
getch();
gotoxy(x,y); cout << " ";
}
int xp = x, yp = y+1;

if (!p) throw BadInput(); // no element with key k

e = p->data; // save element to delete

// restructure tree
// handle case when p has two children
if (p->LeftChild && p->RightChild) // two children
{ // convert to zero or one child case
// find largest element in left subtree of p
BinaryTreeNode<E> *s = p->LeftChild, *ps = p; // parent of s
gotoxy(x-=z,y+=1);
cout << "s";
getch();
gotoxy(x,y);
cout << " ";

while (s->RightChild) // move to larger element
{ ps = s;
s = s->RightChild;
z = z/2;
gotoxy(x+=z,y+=1);
cout << "max";
getch();
gotoxy(x,y); cout << " ";
}

// move largest from s to p
p->data = s->data;
getch();
gotoxy(xp,yp);
cout << s->data << " ";
p = s;
pp = ps;
}

// p has at most one child
// save child pointer in c
BinaryTreeNode<E> *c;
if (p->LeftChild) c = p->LeftChild;
else c = p->RightChild;

// delete p
if (p == root) root = c;
else
{ // is p left or right child of pp?
if (p == pp->LeftChild)
pp->LeftChild = c;
else pp->RightChild = c;
}
delete p;
getch();
gotoxy(x,y+1);
cout << " ";
gotoxy(1,ye+1);
return *this;
}

#endif
/* method asli */
/*
template<class E, class K>
int BSTree<E,K>::Search(const K& k, E &e) const
{ // Search for element that matches k.
// pointer p starts at the root and moves through
// the tree looking for an element with key k
BinaryTreeNode<E> *p = root;
while (p) // examine p->data
if (k < p->data) p = p->LeftChild;
else if (k > p->data) p = p->RightChild;
else {// found element
e = p->data;
return true;}
return false;
}
*/
/*
template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
{// Insert e if not duplicate.
cout << "Inserting " << e;
BinaryTreeNode<E> *p = root, // search pointer
*pp = 0; // parent of p
// find place to insert
while (p)// examine p->data
{
pp = p;
// move p to a child
if (e < p->data) p = p->LeftChild;
else if (e > p->data) p = p->RightChild;
else
throw BadInput(); // duplicate
}
cout << endl;
// get a node for e and attach to pp
BinaryTreeNode<E> *r = new BinaryTreeNode<E> (e);
if (root) {// tree not empty
if (e < pp->data) pp->LeftChild = r;
else pp->RightChild = r;
}
else // insertion into empty tree
root = r;
return *this;
}
*/

/*
template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Delete(const K& k, E& e)
{// Delete element with key k and put it in e.

// set p to point to node with key k
BinaryTreeNode<E> *p = root, // search pointer
*pp = 0; // parent of p
while (p && p->data != k) // move to a child of p
{ pp = p;
if (k < p->data) p = p->LeftChild;
else p = p->RightChild;
}

if (!p) throw BadInput(); // no element with key k

e = p->data; // save element to delete

// restructure tree
// handle case when p has two children
if (p->LeftChild && p->RightChild) // two children
{ // convert to zero or one child case
// find largest element in left subtree of p
BinaryTreeNode<E> *s = p->LeftChild,
*ps = p; // parent of s
while (s->RightChild) // move to larger element
{ ps = s;
s = s->RightChild;
}

// move largest from s to p
p->data = s->data;
p = s;
pp = ps;
}

// p has at most one child
// save child pointer in c
BinaryTreeNode<E> *c;
if (p->LeftChild) c = p->LeftChild;
else c = p->RightChild;

// delete p
if (p == root) root = c;
else
{ // is p left or right child of pp?
if (p == pp->LeftChild)
pp->LeftChild = c;
else pp->RightChild = c;
}
delete p;

return *this;
}
*/

-----------------------------------------------------------------------------------------
di bawah ini adalah bukan hasil kerja saya
-----------------------------------------------------------------------------------------
binary.h

#ifndef BinaryTree_
#define BinaryTree_
int _count;

#include<iostream.h>
#include "lqueue.h"
#include "btnode2.h"
#include "xcept.h"

template<class E, class K> class BSTree;
template<class E, class K> class DBSTree;

template<class T>
class BinaryTree {
friend BSTree<T,int>;
friend DBSTree<T,int>;
public:
BinaryTree() {root = 0;};
~BinaryTree(){};
int IsEmpty() const
{return ((root) ? 0 : 1);} //false : true);}
int Root(T& x) const;
void MakeTree(const T& element,
BinaryTree<T>& left, BinaryTree<T>& right);
void BreakTree(T& element, BinaryTree<T>& left,
BinaryTree<T>& right);
void PreOrder(void(*Visit)(BinaryTreeNode<T> *u))
{PreOrder(Visit, root);}
void InOrder(void(*Visit)(BinaryTreeNode<T> *u))
{InOrder(Visit, root);}
void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))
{PostOrder(Visit, root);}
void LevelOrder(void(*Visit)(BinaryTreeNode<T> *u));
void PreOutput() {PreOrder(Output, root); cout << endl;}
void InOutput() {InOrder(Output, root); cout << endl;}
void PostOutput() {PostOrder(Output, root); cout << endl;}
void LevelOutput() {LevelOrder(Output); cout << endl;}
void Delete() {PostOrder(Free, root); root = 0;}
int Height() const {return Height(root);}
int Size()
{_count = 0; PreOrder(Add1, root); return _count;}
private:
BinaryTreeNode<T> *root; // pointer to root
void PreOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
void InOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
void PostOrder(void(*Visit)
(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
static void Free(BinaryTreeNode<T> *t) {delete t;}
static void Output(BinaryTreeNode<T> *t)
{cout << t->data << ' ';}
static void Add1(BinaryTreeNode<T> *t) {_count++;}
int Height(BinaryTreeNode<T> *t) const;
};

template<class T>
int BinaryTree<T>::Root(T& x) const
{// Return root data in x.
// Return false if no root.
if (root) {x = root->data;
return 1;} //true;}
else return 0; //false; // no root
}

template<class T>
void BinaryTree<T>::MakeTree(const T& element,
BinaryTree<T>& left, BinaryTree<T>& right)
{// Combine left, right, and element to make new tree.
// left, right, and this must be different trees.
// create combined tree
root = new BinaryTreeNode<T>
(element, left.root, right.root);

// deny access from trees left and right
left.root = right.root = 0;
}

template<class T>
void BinaryTree<T>::BreakTree(T& element,
BinaryTree<T>& left, BinaryTree<T>& right)
{// left, right, and this must be different trees.
// check if empty
if (!root) throw BadInput(); // tree empty

// break the tree
element = root->data;
left.root = root->LeftChild;
right.root = root->RightChild;

delete root;
root = 0;
}

template<class T>
void BinaryTree<T>::PreOrder(
void(*Visit)(BinaryTreeNode<T> *u),
BinaryTreeNode<T> *t)
{// Preorder traversal.
if (t) {Visit(t);
PreOrder(Visit, t->LeftChild);
PreOrder(Visit, t->RightChild);
}
}

template <class T>
void BinaryTree<T>::InOrder(
void(*Visit)(BinaryTreeNode<T> *u),
BinaryTreeNode<T> *t)
{// Inorder traversal.
if (t) {InOrder(Visit, t->LeftChild);
Visit(t);
InOrder(Visit, t->RightChild);
}
}

template <class T>
void BinaryTree<T>::PostOrder(
void(*Visit)(BinaryTreeNode<T> *u),
BinaryTreeNode<T> *t)
{// Postorder traversal.
if (t) {PostOrder(Visit, t->LeftChild);
PostOrder(Visit, t->RightChild);
Visit(t);
}
}

template <class T>
void BinaryTree<T>::LevelOrder(
void(*Visit)(BinaryTreeNode<T> *u))
{// Level-order traversal.
LinkedQueue<BinaryTreeNode<T>*> Q;
BinaryTreeNode<T> *t;
t = root;
while (t) {
Visit(t);
if (t->LeftChild) Q.Add(t->LeftChild);
if (t->RightChild) Q.Add(t->RightChild);
try {Q.Delete(t);}
catch (OutOfBounds) {return;}
}
}

template <class T>
int BinaryTree<T>::Height(BinaryTreeNode<T> *t) const
{// Return height of tree *t.
if (!t) return 0; // empty tree
int hl = Height(t->LeftChild); // height of left
int hr = Height(t->RightChild); // height of right
if (hl > hr) return ++hl;
else return ++hr;
}

#endif

lqueue.h

// linked queue

#ifndef LinkedQueue_
#define LinkedQueue_
#include "node.h"
#include "xcept.h"

template<class T>
class LinkedQueue {
// FIFO objects
public:
LinkedQueue() {front = rear = 0;} // constructor
~LinkedQueue(); // destructor
int IsEmpty() const
{return ((front) ? 0 : 1);} //false : true);}
int IsFull() const;
T First() const; // return first element
T Last() const; // return last element
LinkedQueue<T>& Add(const T& x);
LinkedQueue<T>& Delete(T& x);
private:
Node<T> *front; // pointer to first node
Node<T> *rear; // pointer to last node
};

template<class T>
LinkedQueue<T>::~LinkedQueue()
{// Queue destructor. Delete all nodes.
Node<T> *next;
while (front) {
next = front->link;
delete front;
front = next;
}
}

template<class T>
int LinkedQueue<T>::IsFull() const
{// Is the queue full?
Node<T> *p;
try {p = new Node<T>;
delete p;
return 0;} //false;}
catch (NoMem) {return 1;} //true;}
}

template<class T>
T LinkedQueue<T>::First() const
{// Return first element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return front->data;
}

template<class T>
T LinkedQueue<T>::Last() const
{// Return last element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return rear->data;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
{// Add x to rear of queue. Do not catch
// possible NoMem exception thrown by new.

// create node for new element
Node<T> *p = new Node<T>;
p->data = x;
p->link = 0;

// add new node to rear of queue
if (front) rear->link = p; // queue not empty
else front = p; // queue empty
rear = p;

return *this;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{// Delete first element and put it in x. Throw
// OutOfBounds exception if the queue is empty.

if (IsEmpty()) throw OutOfBounds();

// save element in first node
x = front->data;

// delete first node
Node<T> *p = front;
front = front->link;
delete p;

return *this;
}

#endif

node.h

#ifndef Node_
#define Node_

template <class T> class LinkedStack;
template <class T> class LinkedQueue;

template <class T>
class Node {
friend LinkedStack<T>;
friend LinkedQueue<T>;
private:
T data;
Node<T> *link;
};

#endif

btnode2.h

#ifndef BinaryTreeNode_
#define BinaryTreeNode_

template class BinaryTree;
template class BSTree;
template class DBSTree;

template
class BinaryTreeNode {
friend BinaryTree;
friend void PlaceBoosters(BinaryTreeNode *);
friend BSTree;
friend DBSTree;
public:
BinaryTreeNode() {LeftChild = RightChild = 0;}
BinaryTreeNode(const T& e)
{data = e; LeftChild = RightChild = 0;}
BinaryTreeNode(const T& e, BinaryTreeNode *l,
BinaryTreeNode *r)
{data = e; LeftChild = l; RightChild = r;}
private:
T data;
BinaryTreeNode *LeftChild, // left subtree
*RightChild; // right subtree
};

#endif

xcept.h

// exception classes for various error types

#ifndef Xcept_
#define Xcept_

#include <except.h>
#include <new.h>

// bad initializers
class BadInitializers {
public:
BadInitializers() {}
};

// insufficient memory
class NoMem {
public:
NoMem() {}
};

// change new to throw NoMem instead of xalloc
void my_new_handler()
{
throw NoMem();
};

new_handler Old_Handler_ = set_new_handler(my_new_handler);

// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
public:
OutOfBounds() {}
};

// use when operands should have matching size
class SizeMismatch {
public:
SizeMismatch() {}
};

// use when zero was expected
class MustBeZero {
public:
MustBeZero() {}
};

// use when zero was expected
class BadInput {
public:
BadInput() {}
};

#endif