fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <math.h>
  5.  
  6. struct nod
  7. {
  8. 	void *info;
  9. 	struct nod *ant, *prox;
  10. };
  11. typedef struct nod Nod;
  12.  
  13. struct listad
  14. {
  15. 	Nod *ini;
  16. 	Nod *fim;
  17. };
  18. typedef struct listad Listad;
  19.  
  20. struct pagina
  21. {
  22. 	bool folha;
  23. 	int qtdeChaves;
  24. 	struct pagina *pai;
  25. 	Listad *listaChaves;
  26. 	struct pagina *direita;
  27. };
  28.  
  29. struct chave
  30. {
  31. 	int valorChave;
  32. 	struct pagina *filho;
  33. };
  34.  
  35. struct arvoreb
  36. {
  37. 	struct pagina *raiz;
  38. 	int ordem;
  39. 	int altura;
  40. };
  41.  
  42. typedef struct pagina Pagina;
  43. typedef struct chave Chave;
  44. typedef struct arvoreb Arvoreb;
  45.  
  46. Listad *cria_listad()
  47. {
  48.  
  49. 	Listad *L = (Listad *)malloc(sizeof(Listad));
  50. 	L->fim = L->ini = NULL;
  51. 	return L;
  52. }
  53.  
  54. Nod *cria_nod(void *info)
  55. {
  56. 	Nod *novo = (Nod *)malloc(sizeof(Nod));
  57. 	novo->ant = novo->prox = NULL;
  58. 	novo->info = info;
  59. 	return novo;
  60. }
  61.  
  62. Listad *insere_inicio_listad(Listad *L, void *info)
  63. {
  64. 	Nod *novo = cria_nod(info);
  65.  
  66. 	if (L == NULL)
  67. 	{
  68. 		L = cria_listad();
  69. 		L->ini = L->fim = novo;
  70. 	}
  71. 	else
  72. 	{
  73. 		if (L->ini == NULL)
  74. 			L->ini = L->fim = novo;
  75. 		else
  76. 		{
  77. 			novo->prox = L->ini;
  78. 			L->ini->ant = novo;
  79. 			L->ini = novo;
  80. 		}
  81. 	}
  82. 	return L;
  83. }
  84.  
  85. Listad *insere_fim_listad(Listad *L, void *info)
  86. {
  87. 	Nod *novo = cria_nod(info);
  88.  
  89. 	if (L == NULL)
  90. 	{
  91. 		L = cria_listad();
  92. 		L->ini = L->fim = novo;
  93. 	}
  94. 	else
  95. 	{
  96. 		if (L->ini == NULL)
  97. 			L->ini = L->fim = novo;
  98. 		else
  99. 		{
  100. 			novo->ant = L->fim;
  101. 			L->fim->prox = novo;
  102. 			L->fim = novo;
  103. 		}
  104. 	}
  105. 	return L;
  106. }
  107.  
  108. Nod *remove_inicio_listad(Listad *L)
  109. {
  110. 	Nod *aux = NULL;
  111. 	if (L != NULL && L->fim != NULL) // caso haja elemento
  112. 	{
  113. 		aux = L->ini;
  114. 		if (L->ini == L->fim)
  115. 		{
  116. 			L->ini = L->fim = NULL;
  117. 		}
  118. 		else
  119. 		{
  120. 			L->ini = L->ini->prox;
  121. 			L->ini->ant = NULL;
  122. 		}
  123. 	}
  124. 	return aux;
  125. }
  126.  
  127. Nod *remove_fim_listad(Listad *L)
  128. {
  129. 	Nod *aux = NULL;
  130. 	if (L != NULL && L->fim != NULL) // caso haja elemento
  131. 	{
  132. 		aux = L->fim;
  133. 		if (L->ini == L->fim)
  134. 		{
  135. 			L->ini = L->fim = NULL;
  136. 		}
  137. 		else
  138. 		{
  139. 			L->fim = L->fim->ant;
  140. 			L->fim->prox = NULL;
  141. 		}
  142. 	}
  143. 	return aux;
  144. }
  145.  
  146. Listad *libera_listad(Listad *L)
  147. {
  148. 	Nod *aux;
  149. 	while (L->ini != NULL)
  150. 	{
  151. 		aux = L->ini;
  152. 		L->ini = L->ini->prox;
  153. 		free(aux);
  154. 	}
  155. 	L->fim = NULL;
  156. 	free(L);
  157. 	return NULL;
  158. }
  159.  
  160. Listad *divide_lista(Listad *L, int qtde)
  161. {
  162. 	Listad *nova_lista = cria_listad();
  163. 	Nod *aux;
  164. 	int i;
  165. 	for (i = 0, aux = L->ini;
  166. 		 i < qtde;
  167. 		 i++, aux = aux->prox)
  168. 		;
  169.  
  170. 	nova_lista->ini = aux;
  171. 	nova_lista->fim = L->fim;
  172. 	L->fim = aux->ant;
  173.  
  174. 	aux->ant = NULL;
  175. 	L->fim->prox = NULL;
  176.  
  177. 	return nova_lista;
  178. }
  179.  
  180. Arvoreb *cria_arvoreb(int ordem)
  181. {
  182. 	Arvoreb *T = malloc(sizeof(Arvoreb));
  183. 	T->altura = 0;
  184. 	T->ordem = ordem;
  185. 	T->raiz = NULL;
  186. 	return T;
  187. }
  188.  
  189. Pagina *cria_pagina()
  190. {
  191. 	Pagina *nova = malloc(sizeof(Pagina));
  192. 	nova->folha = true; // se é ou não uma folha
  193. 	nova->qtdeChaves = 0;
  194. 	nova->pai = NULL;
  195. 	nova->direita = NULL;
  196. 	nova->listaChaves = cria_listad();
  197. 	return nova;
  198. }
  199.  
  200. Chave *cria_chave(int nova_chave)
  201. {
  202. 	Chave *nova = malloc(sizeof(Chave));
  203. 	nova->filho = NULL;
  204. 	nova->valorChave = nova_chave;
  205. 	return nova;
  206. }
  207.  
  208. Chave *getChave(Nod *aux)
  209. {
  210. 	return (aux->info);
  211. }
  212.  
  213. Pagina *encontra_folha(Arvoreb *T, int nova_chave)
  214. {
  215. 	Pagina *aux_pg = T->raiz;
  216. 	Nod *aux_no = NULL;
  217.  
  218. 	while (!aux_pg->folha) //(aux_pg->folha == 0) //nao é folha
  219. 	{
  220. 		aux_no = aux_pg->listaChaves->ini;
  221. 		while (aux_no != NULL && nova_chave > getChave(aux_no)->valorChave)
  222. 			aux_no = aux_no->prox;
  223.  
  224. 		if (aux_no == NULL)
  225. 			aux_pg = aux_pg->direita;
  226. 		else
  227. 			aux_pg = getChave(aux_no)->filho;
  228. 	}
  229. 	return aux_pg;
  230. }
  231.  
  232. Pagina *insere_chave_na_pagina(Pagina *pagina1, Chave *nova_chave)
  233. {
  234.  
  235. 	if (pagina1 == NULL)
  236. 	{
  237. 		pagina1 = cria_pagina();
  238. 	}
  239. 	Nod *aux = pagina1->listaChaves->ini;
  240.  
  241. 	if (aux == NULL)
  242. 	{
  243. 		pagina1->listaChaves = insere_inicio_listad(pagina1->listaChaves, nova_chave);
  244. 	}
  245. 	else
  246. 	{
  247. 		if (nova_chave->valorChave < getChave(aux)->valorChave)
  248. 		{
  249. 			pagina1->listaChaves = insere_inicio_listad(pagina1->listaChaves, nova_chave);
  250. 		}
  251. 		else if (nova_chave->valorChave > getChave(pagina1->listaChaves->fim)->valorChave)
  252. 		{
  253. 			pagina1->listaChaves = insere_fim_listad(pagina1->listaChaves, nova_chave);
  254. 		}
  255. 		else // inserir ordenado
  256. 		{
  257. 			while (nova_chave->valorChave > getChave(aux)->valorChave)
  258. 			{
  259. 				aux = aux->prox;
  260. 			}
  261. 			Nod *novo_no = cria_nod(nova_chave);
  262. 			novo_no->prox = aux;
  263. 			novo_no->ant = aux->ant;
  264. 			aux->ant->prox = novo_no;
  265. 			aux->ant = novo_no;
  266. 		}
  267. 	}
  268. 	pagina1->qtdeChaves++;
  269. 	return pagina1;
  270. }
  271.  
  272. Pagina *cria_nova_raiz(Chave *chave_subir, Pagina *filho_esq, Pagina *filho_dir)
  273. {
  274. 	Pagina *nova_raiz = cria_pagina();
  275. 	nova_raiz = insere_chave_na_pagina(nova_raiz, chave_subir);
  276. 	chave_subir->filho = filho_esq;
  277. 	nova_raiz->direita = filho_dir;
  278. 	filho_dir->pai = filho_esq->pai = nova_raiz;
  279. 	nova_raiz->folha = false;
  280. 	return nova_raiz;
  281. }
  282.  
  283. Pagina *divide_pagina(Pagina *pagina_inserir)
  284. {
  285. 	Nod *aux_no;
  286. 	Pagina *pai;
  287. 	Pagina *nova_pagina = cria_pagina();
  288. 	int qtde_chaves_lista = ceil(pagina_inserir->qtdeChaves / 2.0);
  289.  
  290. 	// atualizar a nova pagina
  291. 	nova_pagina->listaChaves = divide_lista(pagina_inserir->listaChaves, qtde_chaves_lista);
  292. 	nova_pagina->folha = pagina_inserir->folha;
  293. 	nova_pagina->qtdeChaves = floor(pagina_inserir->qtdeChaves / 2.0);
  294. 	nova_pagina->direita = pagina_inserir->direita;
  295. 	nova_pagina->pai = pagina_inserir->pai;
  296.  
  297. 	// atualizar pagina dividida
  298. 	pagina_inserir->qtdeChaves = qtde_chaves_lista;
  299.  
  300. 	pai = pagina_inserir->pai;
  301.  
  302. 	// quem vai apontar para a nova página
  303. 	if (pagina_inserir->pai != NULL)
  304. 	{
  305. 		aux_no = pai->listaChaves->ini;
  306. 		while (aux_no != NULL && getChave(aux_no)->filho != pagina_inserir)
  307. 			aux_no = aux_no->prox;
  308. 		if (aux_no == NULL)
  309. 			pai->direita = nova_pagina;
  310. 		else
  311. 			getChave(aux_no)->filho = nova_pagina;
  312. 	}
  313.  
  314. 	if (!nova_pagina->folha)
  315. 	{
  316. 		aux_no = nova_pagina->listaChaves->ini;
  317. 		while (aux_no != NULL)
  318. 		{
  319. 			getChave(aux_no)->filho->pai = nova_pagina;
  320. 			aux_no = aux_no->prox;
  321. 		}
  322.  
  323. 		nova_pagina->direita->pai = nova_pagina;
  324. 		// a direita da página que foi dividida
  325. 		// precisa apontar para o mesmo lugar que
  326. 		// a chave anterior a ela aponta
  327. 		pagina_inserir->direita = getChave(pagina_inserir->listaChaves->fim)->filho;
  328. 	}
  329.  
  330. 	// chave a subir, mudar filho
  331. 	getChave(pagina_inserir->listaChaves->fim)->filho = pagina_inserir;
  332.  
  333. 	return nova_pagina;
  334. }
  335.  
  336. bool direita_da_pag(Pagina *pagina_inserir, int ordem)
  337. {
  338. 	bool deu = true;
  339. 	if (pagina_inserir->pai->listaChaves->fim != NULL)
  340. 	{
  341. 		Nod *aux_no = pagina_inserir->pai->listaChaves->fim;
  342. 		if (getChave(aux_no)->filho->qtdeChaves < ordem - 1)
  343. 		{
  344. 			Nod *removido = remove_inicio_listad(pagina_inserir->listaChaves);
  345. 			insere_fim_listad(getChave(aux_no)->filho->listaChaves, removido->info);
  346. 			int aux = getChave(getChave(aux_no)->filho->listaChaves->fim)->valorChave;
  347. 			int aux2 = getChave(aux_no)->valorChave;
  348. 			getChave(getChave(aux_no)->filho->listaChaves->fim)->valorChave = aux2;
  349. 			getChave(aux_no)->valorChave = aux;
  350. 			pagina_inserir->qtdeChaves--;
  351. 			getChave(aux_no)->filho->qtdeChaves++;
  352. 			deu = false;
  353. 		}
  354. 	}
  355. 	return deu;
  356. }
  357.  
  358. bool direita_normal(Pagina *pagina_inserir, int ordem, Nod *aux_no)
  359. {
  360. 	bool deu = true;
  361. 	if (getChave(aux_no->prox)->filho->qtdeChaves < ordem - 1)
  362. 	{
  363. 		Nod *fim = remove_fim_listad(pagina_inserir->listaChaves);
  364. 		insere_inicio_listad(getChave(aux_no->prox)->filho->listaChaves, fim->info);
  365. 		int aux = getChave(aux_no)->valorChave;
  366. 		int aux2 = getChave(getChave(aux_no->prox)->filho->listaChaves->ini)->valorChave;
  367. 		getChave(aux_no)->valorChave = aux2;
  368. 		getChave(getChave(aux_no->prox)->filho->listaChaves->ini)->valorChave = aux;
  369. 		pagina_inserir->qtdeChaves--;
  370. 		getChave(aux_no->prox)->filho->qtdeChaves++;
  371. 		deu = false;
  372. 	}
  373. 	return deu;
  374. }
  375.  
  376. bool direita_geral(Pagina *pagina_inserir, int ordem, Nod *aux_no)
  377. {
  378. 	bool deu = true;
  379. 	if (pagina_inserir->pai->direita->qtdeChaves < ordem - 1)
  380. 	{
  381. 		Nod *fim = remove_fim_listad(pagina_inserir->listaChaves);
  382. 		insere_inicio_listad(pagina_inserir->pai->direita->listaChaves, fim->info);
  383. 		int aux = getChave(pagina_inserir->pai->direita->listaChaves->ini)->valorChave;
  384. 		int aux2 = getChave(aux_no)->valorChave;
  385. 		getChave(pagina_inserir->pai->direita->listaChaves->ini)->valorChave = aux2;
  386. 		getChave(aux_no)->valorChave = aux;
  387. 		pagina_inserir->qtdeChaves--;
  388. 		pagina_inserir->pai->direita->qtdeChaves++;
  389. 		deu = false;
  390. 	}
  391. 	return deu;
  392. }
  393.  
  394. bool esquerda_normal(Pagina *pagina_inserir, int ordem, Nod *aux_no)
  395. {
  396. 	bool deu = true;
  397. 	if (getChave(aux_no->ant)->filho->qtdeChaves < ordem - 1 && aux_no->ant != NULL)
  398. 	{
  399. 		Nod *inicio = remove_inicio_listad(pagina_inserir->listaChaves);
  400. 		insere_fim_listad(getChave(aux_no->ant)->filho->listaChaves, inicio->info);
  401. 		int aux = getChave(getChave(aux_no->ant)->filho->listaChaves->fim)->valorChave;
  402. 		int aux2 = getChave(aux_no->ant)->valorChave;
  403. 		getChave(getChave(aux_no->ant)->filho->listaChaves->fim)->valorChave = aux2;
  404. 		getChave(aux_no->ant)->valorChave = aux;
  405. 		pagina_inserir->qtdeChaves--;
  406. 		getChave(aux_no->ant)->filho->qtdeChaves++;
  407. 		deu = false;
  408. 	}
  409. 	return deu;
  410. }
  411.  
  412. bool confere_filhos(Pagina *pagina_inserir, int ordem)
  413. {
  414. 	Nod *aux_no = pagina_inserir->pai->listaChaves->ini;
  415. 	bool confere = false;
  416. 	while (aux_no != NULL && getChave(aux_no)->filho != pagina_inserir)
  417. 		aux_no = aux_no->prox; // achou o pai
  418. 	if (aux_no == NULL)
  419. 	{ // esta na direita da pagina
  420. 		confere = direita_da_pag(pagina_inserir, ordem);
  421. 	}
  422. 	else
  423. 	{
  424. 		if (aux_no->prox != NULL) // insere na direita
  425. 			confere = direita_normal(pagina_inserir, ordem, aux_no);
  426. 		if (!confere)
  427. 		{ // esquerda ou direita geral e nao deu certo na direita normal
  428. 			if (aux_no->prox == NULL)
  429. 			{ // direita geral
  430. 				confere = direita_geral(pagina_inserir, ordem, aux_no);
  431. 			}
  432. 			else if (aux_no->ant != NULL)
  433. 			{ // esquerda
  434. 				confere = esquerda_normal(pagina_inserir, ordem, aux_no);
  435. 			}
  436. 		}
  437. 	}
  438. 	return confere;
  439. }
  440.  
  441. Arvoreb *insere_arvoreb(Arvoreb *T, int nova_ch, int *qnt_divisao)
  442. {
  443. 	bool tem_chave_para_inserir = true;
  444. 	Pagina *nova_pagina;
  445. 	Chave *nova_chave = cria_chave(nova_ch), *chave_subir;
  446. 	Nod *aux;
  447. 	bool confere = false;
  448. 	// arvore for vazia
  449. 	if (T == NULL || T->raiz == NULL)
  450. 	{
  451. 		T = cria_arvoreb(T->ordem);
  452. 		T->raiz = insere_chave_na_pagina(T->raiz, nova_chave);
  453. 	}
  454. 	else
  455. 	{
  456. 		Pagina *pagina_inserir = encontra_folha(T, nova_ch);
  457. 		while (tem_chave_para_inserir)
  458. 		{
  459. 			pagina_inserir = insere_chave_na_pagina(pagina_inserir, nova_chave);
  460. 			// Chave *ch_subir = chave que vai subir
  461.  
  462. 			if (pagina_inserir->qtdeChaves < T->ordem) // nao estorou
  463. 			{
  464. 				tem_chave_para_inserir = false;
  465. 			}
  466.  
  467. 			else // estorou
  468. 			{
  469. 				if (pagina_inserir->folha && pagina_inserir->pai != NULL)
  470. 					tem_chave_para_inserir = confere_filhos(pagina_inserir, T->ordem);
  471.  
  472. 				if (tem_chave_para_inserir) // se nao conseguiu inserir na direita ou na esquerda divide
  473. 				{
  474. 					nova_pagina = divide_pagina(pagina_inserir);
  475. 					(*qnt_divisao)++;
  476. 					aux = remove_fim_listad(pagina_inserir->listaChaves);
  477. 					pagina_inserir->qtdeChaves--;
  478. 					chave_subir = aux->info;
  479. 					free(aux);
  480.  
  481. 					if (pagina_inserir->pai == NULL) // folha é a raiz
  482. 					{
  483. 						T->raiz = cria_nova_raiz(chave_subir, pagina_inserir, nova_pagina);
  484. 						T->altura++;
  485. 						tem_chave_para_inserir = false;
  486. 					}
  487. 					else
  488. 					{
  489. 						pagina_inserir = pagina_inserir->pai;
  490. 						nova_chave = chave_subir;
  491. 					}
  492. 				}
  493. 			}
  494. 		}
  495. 	}
  496. 	return T;
  497. }
  498.  
  499. void em_ordem(Pagina *raiz)
  500. {
  501. 	Nod *aux;
  502. 	if (raiz != NULL)
  503. 	{
  504. 		aux = raiz->listaChaves->ini;
  505. 		while (aux != NULL)
  506. 		{
  507. 			em_ordem(getChave(aux)->filho);
  508. 			printf("%d ", getChave(aux)->valorChave);
  509. 			aux = aux->prox;
  510. 		}
  511. 		em_ordem(raiz->direita);
  512. 	}
  513. }
  514.  
  515. void libera_arvore(Pagina *raiz)
  516. {
  517. 	Nod *aux;
  518. 	if (raiz != NULL)
  519. 	{
  520. 		aux = raiz->listaChaves->ini;
  521. 		while (raiz->listaChaves->ini != NULL)
  522. 		{
  523. 			em_ordem(getChave(aux)->filho);
  524. 			aux = raiz->listaChaves->ini;
  525. 			raiz->listaChaves->ini = raiz->listaChaves->ini->prox;
  526. 			free(aux->info);
  527. 			free(aux);
  528. 		}
  529. 		raiz->listaChaves->fim = NULL;
  530. 		free(raiz->listaChaves);
  531. 		em_ordem(raiz->direita);
  532. 		free(raiz);
  533. 	}
  534. }
  535.  
  536. int main()
  537. {
  538. 	Arvoreb *arvore = NULL;
  539. 	Arvoreb *arvore_normal = NULL;
  540. 	int ordem ;
  541. 	int entrada;
  542. 	int qnt_divisao = 0;
  543. 	int qnt_divisao_normal = 0;
  544.  
  545. 	arvore = cria_arvoreb(ordem);
  546. 	arvore_normal = cria_arvoreb(ordem);
  547.     scanf("%d", &ordem);
  548. 	while (entrada != -1)
  549. 	{
  550. 		scanf("%d", &entrada);
  551. 		if (entrada != -1)
  552. 		{
  553. 			arvore = insere_arvoreb(arvore, entrada, &qnt_divisao);
  554. 		}
  555. 	}
  556. 	printf("%d %d\n", qnt_divisao, arvore->altura);
  557. 	return 0;
  558. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
4

50 30 40 44 88 95 25 91 31 52 20 60 70 74 78 79 22 28 33 39 98 85 86 87 90 92 93 94 35 32 -1
stdout 
0 0
https://ideone.com/5XbK71
language:
C (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!