Konversi C ke JavaScript
#include <stdio.h>
#include <stdlib.h>
struct CCB
{
int so;
int cao;
struct CCB *trai, *phai;
};
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
int chieuCao(struct CCB *N)
{
if (N == NULL)
return 0;
return N->cao;
}
int layCanBang(struct CCB *N)
{
if (N == NULL)
return 0;
return chieuCao(N->trai) - chieuCao(N->phai);
}
struct CCB* nutNhoNhat(struct CCB *N)
{
struct CCB* p = N;
/* Tim nut trai nhat */
while (p->trai != NULL)
p = p->trai;
return p;
}
struct CCB *quayPhai(struct CCB *y)
{
struct CCB *x = y->trai;
struct CCB *T2 = x->phai;
x->phai = y;
y->trai = T2;
y->cao = max(chieuCao(y->trai), chieuCao(y->phai))+1;
x->cao = max(chieuCao(x->trai), chieuCao(x->phai))+1;
return x;
}
struct CCB *quayTrai(struct CCB *x)
{
struct CCB *y = x->phai;
struct CCB *T2 = y->trai;
y->trai = x;
x->phai = T2;
x->cao = max(chieuCao(x->trai), chieuCao(x->phai))+1;
y->cao = max(chieuCao(y->trai), chieuCao(y->phai))+1;
return y;
}
struct CCB* them(struct CCB *goc, int x)
{
/* 1. Thuc hien them vao cay tim kiem nhi phan */
if (goc == NULL)
{
goc = (struct CCB*) malloc(sizeof(struct CCB));
goc->so = x;
goc->cao = 1;
goc->trai = goc->phai = NULL;
return goc;
}
else
if (x < goc->so)
goc->trai = them(goc->trai, x);
else if (x > goc->so)
goc->phai = them(goc->phai, x);
else // Trùng khóa, không thêm
return goc;
/* 2. Cap nhat chieu cao */
goc->cao = 1 + max(chieuCao(goc->trai), chieuCao(goc->phai));
/* 3. Kiem tra can bang */
int cb = layCanBang(goc);
// Xet 4 truong hop khong can bang
// Truong hop Trai-Trai
if (cb > 1 && x < goc->trai->so)
return quayPhai(goc);
// Truong hop Phai-Phai
if (cb < -1 && x > goc->phai->so)
return quayTrai(goc);
// Truong hop Trai-Phai
if (cb > 1 && x > goc->trai->so)
{
goc->trai = quayTrai(goc->trai);
return quayPhai(goc);
}
// Truung hop Phai-Trai
if (cb < -1 && x < goc->phai->so)
{
goc->phai = quayPhai(goc->phai);
return quayTrai(goc);
}
return goc;
}
struct CCB* xoa(struct CCB* goc, int x)
{
// 1: Xoa nhu tren cay tim kiem nhi phan
if (goc == NULL)
return goc;
if (x < goc->so)
goc->trai = xoa(goc->trai, x);
else
if(x > goc->so)
goc->phai = xoa(goc->phai, x);
else //Xoa nut goc
{
// nut goc khong co 2 nut con khac rong
if( (goc->trai == NULL) || (goc->phai == NULL) )
{
struct CCB *temp = goc->trai ? goc->trai:goc->phai;
// Khong co nut con
if (temp == NULL)
{
temp = goc;
goc = NULL;
}
else // Co 1 nut con
*goc = *temp; // Copy nut khong rong len nut goc
free(temp);
}
else
{ // nut co 2 nut con:
// lay nut co khoa nho nhat o cay con phai
struct CCB* temp = nutNhoNhat(goc->phai);
// Copy du lieu tu temp lên goc
goc->so = temp->so;
// Xoa nut temp nam o cay con phai nut goc
goc->phai = xoa(goc->phai, temp->so);
}
}
// Neu cay co 1 nut thi dung
if (goc == NULL)
return goc;
// 2: Cap nhat chieu cao cua nut
goc->cao = 1 + max(chieuCao(goc->trai), chieuCao(goc->phai));
// 3: Lay he so can bang
int cb = layCanBang(goc);
// Xet 4 truong hop khong can bang
// Truong hop Trai-Trai
if (cb > 1 && layCanBang(goc->trai) >= 0)
return quayPhai(goc);
// Truong hop Trai-Phai
if (cb > 1 && layCanBang(goc->trai) < 0)
{
goc->trai = quayTrai(goc->trai);
return quayPhai(goc);
}
// Truong hop Phai-Phai
if (cb < -1 && layCanBang(goc->phai) <= 0)
return quayTrai(goc);
// Truong hop Phai-Trai
if (cb < -1 && layCanBang(goc->phai) > 0)
{
goc->phai = quayPhai(goc->phai);
return quayTrai(goc);
}
return goc;
}
main()
{
struct CCB *goc = NULL;
int i, k, n = 100000;
for(i=1; i<=n; i++)
{
goc = them(goc, i);
}
printf("Chieu cao cay: %d\n",goc->cao);
for(i=1; i<=n/2; i++)
{
k = rand();
goc = xoa(goc, i);
}
printf("Chieu cao cay sau khi xoa: %d\n",goc->cao);
}
Puzzled Penguin