حذف نود از درخت MaxHeap و BST (راهنمایی میخوام)

[Safinoor]

سلام دوستان
فردا پروژه باید تحویل بدم از دوستان کسی هستش در مورد حذف نود از درخت MaxHeap و BST سورس ارائه بده + توضیح ؟

بنده سه تا سایت گیر آوردم اگر کسی هم بتونه اینها رو توضیح بده ممنون میشم :

حذف نود از درخت BST :



http://faculty.winthrop.edu/dannellys/csci271/binary_tree_delete.htm


حذف نود از درخت MaxHeap :


http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node7.html

اینم هستش :


http://www.ces.clemson.edu/~warner/M865/HeapDelete.html

پیشاپیش تشکر,بدرود .

[#Elahe#]

حذف از بی اس تی کمی پیچیده تر از درج و جستجوشه
که سه تا حالت میتونه داشته باشه
1 . گره مورد نظر فرزند نداشته باشه ، یعنی برگ باشه
2 . یه فرزند داشته باشه
3 . گره مورد نظر سه فرزند داشته باشه

public static void deleteNode (Node root, int data){
if( root == null ){
return;
}
Node candidate = search(root,data);
if(candidate == null){
return;
}
// Find the candidate to delete
Node originalCandidate = candidate;
if( candidate.left == null || candidate.right == null ){
candidate = originalCandidate;
}else{
candidate = successor(candidate);
}
// Find the branch to link to parent
Node branch;
if(candidate.left != null ){
branch = candidate.left;
}else{
branch = candidate.right;
}
// Find parent of candidate
Node candidateParent = candidate.parent;
if(branch != null){
branch.parent = candidateParent;
}

if( candidateParent == null ) {
root = branch;
}else{
if(candidate == candidateParent.left){
candidateParent.left =branch;
}else{
candidateParent.right =branch;
}
}
if(originalCandidate != candidate){
originalCandidate.data = candidate.data;
}
}

واسه حذف از heap هم باید مفهوم heapify رو بدونید
تو این کد میتونید قسمت حذفش رو تحلیل بکنید واسه خودتون

const int HEAP_SIZE=50;
#define PARENT(i) (i-1)>>1
#define LEFT(x) 2*x+1 // since we start with index 0
#define RIGHT(x) 2*x+2

class MaxHeap
{
int arr[HEAP_SIZE];
int count;
public:
MaxHeap()
{
count=0;
}
bool insert(int element);
bool remove(int& element);
bool increase_element(int element, int idx);
bool decrease_element(int element, int idx);
bool change(int element, int idx);
};

bool MaxHeap::insert(int element)
{
if(count > HEAP_SIZE)
return false;
int i = count;
arr[i] = element;
// the below loop never runs if the input
// array is already in maxheap format!!
while(i>0 && arr[PARENT(i)] < arr[i]) {
int tmp=arr[PARENT(i)];
arr[PARENT(i)] = arr[i];
arr[i] = tmp;
i = PARENT(i);
}
count++;
return true;
}

bool MaxHeap::remove(int& element)
{
if(count < 0)
return false;
element = arr[0];
arr[0] = arr[count-1];
arr[count-1] = INT_MIN;
count = count - 1;
max_heapify(arr, 0, count);
return true;
}

bool MaxHeap::increase_element(int element, int idx)
{
if(idx > count || idx < 0)
return false;
if(arr[idx] > element)
return false;
arr[idx] = element;
// the below code is same as insert
// repeating it, to be clear
while(idx > 0 && arr[PARENT(idx)] < arr[idx]) {
int tmp=arr[PARENT(idx)];
arr[PARENT(idx)] = arr[idx];
arr[idx] = tmp;
idx = PARENT(idx);
}
return true;
}

bool MaxHeap::decrease_element(int element, int idx)
{
if(idx > count || idx < 0)
return false;
if(element > arr[idx])
return false;
arr[idx]= element;
max_heapify(arr, idx, count);
return true;
}

bool MaxHeap::change(int element, int idx)
{
if(idx > count || idx < 0)
return false;
if(element > arr[idx] )
return increase_element(element, idx);
else
return decrease_element(element, idx);
}

void main()
{
MaxHeap obj;
int A[] = {7,2,1,12,15,8,4,0,6,13,9,5};
for(int i=0; i<12;i++) {
obj.insert(A[i]);
}
int val;
obj.remove(val);
obj.increase_element(20, 5);
obj.decrease_element(3, 0);
obj.change(80, 8);
obj.change(0, 0);
}

[#Elahe#]

این هم از heapify
(https://stackoverflow.com/questions/6640397/how-to-delete-from-a-max-heap)