Advertisement
Guest User

Tree structure thingy

a guest
Mar 24th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.13 KB | None | 0 0
  1. Log of adding every c-string that follows the structure { letter, '\0' }
  2. in decreasing order from o to a, with structures printed.
  3.  
  4. To find the right branch, move over one space from the start of the previous and move up until a vertical match happens. Vice versa left for down.
  5.  
  6. The skip list is a probabilistic list with structure:
  7. LEFT SENTINEL
  8. STUFF
  9. RIGHT SENTINEL
  10.  
  11. And a printing structure
  12. CONTENTS_count :: height
  13.  
  14. such that the height of a given "node" is determined by random chance (to get a node of height 7, you need to make the node and then win 6 coin flips, essentially).
  15.  
  16. o ----------------------------------
  17. AVL:
  18. o_2
  19.  
  20. BST:
  21. o_2
  22.  
  23. RBT:
  24. o_2!B
  25. NIL: BLACK
  26.  
  27. SKIP:
  28. LEFT_SENTINEL :: 1
  29. o_2 :: 1
  30. RIGHT_SENTINEL :: 1
  31.  
  32.  
  33.  
  34. n ----------------------------------
  35. AVL:
  36. o_2
  37. n_2
  38.  
  39. BST:
  40. o_2
  41. n_2
  42.  
  43. RBT:
  44. o_2!B
  45. n_2!R
  46. NIL: BLACK
  47.  
  48. SKIP:
  49. LEFT_SENTINEL :: 2
  50. n_2 :: 2
  51. o_2 :: 1
  52. RIGHT_SENTINEL :: 2
  53.  
  54.  
  55.  
  56. m ----------------------------------
  57. AVL:
  58. o_2
  59. n_2
  60. m_2
  61.  
  62. BST:
  63. o_2
  64. n_2
  65. m_2
  66.  
  67. RBT:
  68. o_2!R
  69. n_2!B
  70. m_2!R
  71. NIL: BLACK
  72.  
  73. SKIP:
  74. LEFT_SENTINEL :: 6
  75. m_2 :: 6
  76. n_2 :: 2
  77. o_2 :: 1
  78. RIGHT_SENTINEL :: 6
  79.  
  80.  
  81.  
  82. l ----------------------------------
  83. AVL:
  84. o_2
  85. n_2
  86. m_2
  87. l_2
  88.  
  89. BST:
  90. o_2
  91. n_2
  92. m_2
  93. l_2
  94.  
  95. RBT:
  96. o_2!B
  97. n_2!B
  98. m_2!B
  99. l_2!R
  100. NIL: BLACK
  101.  
  102. SKIP:
  103. LEFT_SENTINEL :: 6
  104. l_2 :: 1
  105. m_2 :: 6
  106. n_2 :: 2
  107. o_2 :: 1
  108. RIGHT_SENTINEL :: 6
  109.  
  110.  
  111.  
  112. k ----------------------------------
  113. AVL:
  114. o_2
  115. n_2
  116. m_2
  117. l_2
  118. k_2
  119.  
  120. BST:
  121. o_2
  122. n_2
  123. m_2
  124. l_2
  125. k_2
  126.  
  127. RBT:
  128. o_2!B
  129. n_2!B
  130. m_2!R
  131. l_2!B
  132. k_2!R
  133. NIL: BLACK
  134.  
  135. SKIP:
  136. LEFT_SENTINEL :: 6
  137. k_2 :: 2
  138. l_2 :: 1
  139. m_2 :: 6
  140. n_2 :: 2
  141. o_2 :: 1
  142. RIGHT_SENTINEL :: 6
  143.  
  144.  
  145.  
  146. j ----------------------------------
  147. AVL:
  148. o_2
  149. n_2
  150. m_2
  151. l_2
  152. k_2
  153. j_2
  154.  
  155. BST:
  156. o_2
  157. n_2
  158. m_2
  159. l_2
  160. k_2
  161. j_2
  162.  
  163. RBT:
  164. o_2!B
  165. n_2!B
  166. m_2!B
  167. l_2!R
  168. k_2!B
  169. j_2!R
  170. NIL: BLACK
  171.  
  172. SKIP:
  173. LEFT_SENTINEL :: 6
  174. j_2 :: 1
  175. k_2 :: 2
  176. l_2 :: 1
  177. m_2 :: 6
  178. n_2 :: 2
  179. o_2 :: 1
  180. RIGHT_SENTINEL :: 6
  181.  
  182.  
  183.  
  184. i ----------------------------------
  185. AVL:
  186. o_2
  187. n_2
  188. m_2
  189. l_2
  190. k_2
  191. j_2
  192. i_2
  193.  
  194. BST:
  195. o_2
  196. n_2
  197. m_2
  198. l_2
  199. k_2
  200. j_2
  201. i_2
  202.  
  203. RBT:
  204. o_2!B
  205. n_2!B
  206. m_2!B
  207. l_2!R
  208. k_2!R
  209. j_2!B
  210. i_2!R
  211. NIL: BLACK
  212.  
  213. SKIP:
  214. LEFT_SENTINEL :: 7
  215. i_2 :: 7
  216. j_2 :: 1
  217. k_2 :: 2
  218. l_2 :: 1
  219. m_2 :: 6
  220. n_2 :: 2
  221. o_2 :: 1
  222. RIGHT_SENTINEL :: 7
  223.  
  224.  
  225.  
  226. h ----------------------------------
  227. AVL:
  228. o_2
  229. n_2
  230. m_2
  231. l_2
  232. k_2
  233. j_2
  234. i_2
  235. h_2
  236.  
  237. BST:
  238. o_2
  239. n_2
  240. m_2
  241. l_2
  242. k_2
  243. j_2
  244. i_2
  245. h_2
  246.  
  247. RBT:
  248. o_2!B
  249. n_2!R
  250. m_2!B
  251. l_2!B
  252. k_2!B
  253. j_2!R
  254. i_2!B
  255. h_2!R
  256. NIL: BLACK
  257.  
  258. SKIP:
  259. LEFT_SENTINEL :: 7
  260. h_2 :: 1
  261. i_2 :: 7
  262. j_2 :: 1
  263. k_2 :: 2
  264. l_2 :: 1
  265. m_2 :: 6
  266. n_2 :: 2
  267. o_2 :: 1
  268. RIGHT_SENTINEL :: 7
  269.  
  270.  
  271.  
  272. g ----------------------------------
  273. AVL:
  274. o_2
  275. n_2
  276. m_2
  277. l_2
  278. k_2
  279. j_2
  280. i_2
  281. h_2
  282. g_2
  283.  
  284. BST:
  285. o_2
  286. n_2
  287. m_2
  288. l_2
  289. k_2
  290. j_2
  291. i_2
  292. h_2
  293. g_2
  294.  
  295. RBT:
  296. o_2!B
  297. n_2!R
  298. m_2!B
  299. l_2!B
  300. k_2!B
  301. j_2!R
  302. i_2!R
  303. h_2!B
  304. g_2!R
  305. NIL: BLACK
  306.  
  307. SKIP:
  308. LEFT_SENTINEL :: 7
  309. g_2 :: 3
  310. h_2 :: 1
  311. i_2 :: 7
  312. j_2 :: 1
  313. k_2 :: 2
  314. l_2 :: 1
  315. m_2 :: 6
  316. n_2 :: 2
  317. o_2 :: 1
  318. RIGHT_SENTINEL :: 7
  319.  
  320.  
  321.  
  322. f ----------------------------------
  323. AVL:
  324. o_2
  325. n_2
  326. m_2
  327. l_2
  328. k_2
  329. j_2
  330. i_2
  331. h_2
  332. g_2
  333. f_2
  334.  
  335. BST:
  336. o_2
  337. n_2
  338. m_2
  339. l_2
  340. k_2
  341. j_2
  342. i_2
  343. h_2
  344. g_2
  345. f_2
  346.  
  347. RBT:
  348. o_2!B
  349. n_2!B
  350. m_2!B
  351. l_2!B
  352. k_2!B
  353. j_2!B
  354. i_2!B
  355. h_2!R
  356. g_2!B
  357. f_2!R
  358. NIL: BLACK
  359.  
  360. SKIP:
  361. LEFT_SENTINEL :: 7
  362. f_2 :: 4
  363. g_2 :: 3
  364. h_2 :: 1
  365. i_2 :: 7
  366. j_2 :: 1
  367. k_2 :: 2
  368. l_2 :: 1
  369. m_2 :: 6
  370. n_2 :: 2
  371. o_2 :: 1
  372. RIGHT_SENTINEL :: 7
  373.  
  374.  
  375.  
  376. e ----------------------------------
  377. AVL:
  378. o_2
  379. n_2
  380. m_2
  381. l_2
  382. k_2
  383. j_2
  384. i_2
  385. h_2
  386. g_2
  387. f_2
  388. e_2
  389.  
  390. BST:
  391. o_2
  392. n_2
  393. m_2
  394. l_2
  395. k_2
  396. j_2
  397. i_2
  398. h_2
  399. g_2
  400. f_2
  401. e_2
  402.  
  403. RBT:
  404. o_2!B
  405. n_2!B
  406. m_2!B
  407. l_2!B
  408. k_2!B
  409. j_2!B
  410. i_2!B
  411. h_2!R
  412. g_2!R
  413. f_2!B
  414. e_2!R
  415. NIL: BLACK
  416.  
  417. SKIP:
  418. LEFT_SENTINEL :: 7
  419. e_2 :: 2
  420. f_2 :: 4
  421. g_2 :: 3
  422. h_2 :: 1
  423. i_2 :: 7
  424. j_2 :: 1
  425. k_2 :: 2
  426. l_2 :: 1
  427. m_2 :: 6
  428. n_2 :: 2
  429. o_2 :: 1
  430. RIGHT_SENTINEL :: 7
  431.  
  432.  
  433.  
  434. d ----------------------------------
  435. AVL:
  436. o_2
  437. n_2
  438. m_2
  439. l_2
  440. k_2
  441. j_2
  442. i_2
  443. h_2
  444. g_2
  445. f_2
  446. e_2
  447. d_2
  448.  
  449. BST:
  450. o_2
  451. n_2
  452. m_2
  453. l_2
  454. k_2
  455. j_2
  456. i_2
  457. h_2
  458. g_2
  459. f_2
  460. e_2
  461. d_2
  462.  
  463. RBT:
  464. o_2!B
  465. n_2!B
  466. m_2!B
  467. l_2!B
  468. k_2!B
  469. j_2!R
  470. i_2!B
  471. h_2!B
  472. g_2!B
  473. f_2!R
  474. e_2!B
  475. d_2!R
  476. NIL: BLACK
  477.  
  478. SKIP:
  479. LEFT_SENTINEL :: 7
  480. d_2 :: 1
  481. e_2 :: 2
  482. f_2 :: 4
  483. g_2 :: 3
  484. h_2 :: 1
  485. i_2 :: 7
  486. j_2 :: 1
  487. k_2 :: 2
  488. l_2 :: 1
  489. m_2 :: 6
  490. n_2 :: 2
  491. o_2 :: 1
  492. RIGHT_SENTINEL :: 7
  493.  
  494.  
  495.  
  496. c ----------------------------------
  497. AVL:
  498. o_2
  499. n_2
  500. m_2
  501. l_2
  502. k_2
  503. j_2
  504. i_2
  505. h_2
  506. g_2
  507. f_2
  508. e_2
  509. d_2
  510. c_2
  511.  
  512. BST:
  513. o_2
  514. n_2
  515. m_2
  516. l_2
  517. k_2
  518. j_2
  519. i_2
  520. h_2
  521. g_2
  522. f_2
  523. e_2
  524. d_2
  525. c_2
  526.  
  527. RBT:
  528. o_2!B
  529. n_2!B
  530. m_2!B
  531. l_2!B
  532. k_2!B
  533. j_2!R
  534. i_2!B
  535. h_2!B
  536. g_2!B
  537. f_2!R
  538. e_2!R
  539. d_2!B
  540. c_2!R
  541. NIL: BLACK
  542.  
  543. SKIP:
  544. LEFT_SENTINEL :: 7
  545. c_2 :: 1
  546. d_2 :: 1
  547. e_2 :: 2
  548. f_2 :: 4
  549. g_2 :: 3
  550. h_2 :: 1
  551. i_2 :: 7
  552. j_2 :: 1
  553. k_2 :: 2
  554. l_2 :: 1
  555. m_2 :: 6
  556. n_2 :: 2
  557. o_2 :: 1
  558. RIGHT_SENTINEL :: 7
  559.  
  560.  
  561.  
  562. b ----------------------------------
  563. AVL:
  564. o_2
  565. n_2
  566. m_2
  567. l_2
  568. k_2
  569. j_2
  570. i_2
  571. h_2
  572. g_2
  573. f_2
  574. e_2
  575. d_2
  576. c_2
  577. b_2
  578.  
  579. BST:
  580. o_2
  581. n_2
  582. m_2
  583. l_2
  584. k_2
  585. j_2
  586. i_2
  587. h_2
  588. g_2
  589. f_2
  590. e_2
  591. d_2
  592. c_2
  593. b_2
  594.  
  595. RBT:
  596. o_2!B
  597. n_2!B
  598. m_2!B
  599. l_2!B
  600. k_2!B
  601. j_2!B
  602. i_2!B
  603. h_2!R
  604. g_2!B
  605. f_2!B
  606. e_2!B
  607. d_2!R
  608. c_2!B
  609. b_2!R
  610. NIL: BLACK
  611.  
  612. SKIP:
  613. LEFT_SENTINEL :: 7
  614. b_2 :: 1
  615. c_2 :: 1
  616. d_2 :: 1
  617. e_2 :: 2
  618. f_2 :: 4
  619. g_2 :: 3
  620. h_2 :: 1
  621. i_2 :: 7
  622. j_2 :: 1
  623. k_2 :: 2
  624. l_2 :: 1
  625. m_2 :: 6
  626. n_2 :: 2
  627. o_2 :: 1
  628. RIGHT_SENTINEL :: 7
  629.  
  630.  
  631.  
  632. a ----------------------------------
  633. AVL:
  634. o_2
  635. n_2
  636. m_2
  637. l_2
  638. k_2
  639. j_2
  640. i_2
  641. h_2
  642. g_2
  643. f_2
  644. e_2
  645. d_2
  646. c_2
  647. b_2
  648. a_2
  649.  
  650. BST:
  651. o_2
  652. n_2
  653. m_2
  654. l_2
  655. k_2
  656. j_2
  657. i_2
  658. h_2
  659. g_2
  660. f_2
  661. e_2
  662. d_2
  663. c_2
  664. b_2
  665. a_2
  666.  
  667. RBT:
  668. o_2!B
  669. n_2!B
  670. m_2!B
  671. l_2!B
  672. k_2!B
  673. j_2!B
  674. i_2!B
  675. h_2!R
  676. g_2!B
  677. f_2!B
  678. e_2!B
  679. d_2!R
  680. c_2!R
  681. b_2!B
  682. a_2!R
  683. NIL: BLACK
  684.  
  685. SKIP:
  686. LEFT_SENTINEL :: 7
  687. a_2 :: 6
  688. b_2 :: 1
  689. c_2 :: 1
  690. d_2 :: 1
  691. e_2 :: 2
  692. f_2 :: 4
  693. g_2 :: 3
  694. h_2 :: 1
  695. i_2 :: 7
  696. j_2 :: 1
  697. k_2 :: 2
  698. l_2 :: 1
  699. m_2 :: 6
  700. n_2 :: 2
  701. o_2 :: 1
  702. RIGHT_SENTINEL :: 7
  703.  
  704.  
  705.  
  706. AVL: 0.513 seconds.
  707. BST: 0.513 seconds.
  708. RBT: 0.514 seconds.
  709. skip: 0.514 seconds.
  710. Base time: 0.515 seconds.
  711.  
  712. Letters used: 16
  713. Approximate reasonable height: 4
  714. Maximum reasonable AVL height: 5.76
  715.  
  716. AVL Height: 4
  717. BST Height: 15
  718. RBT Height: 6
  719.  
  720. AVL Word count: 15 (30)
  721. BST word count: 15 (30)
  722. RBT word count: 15 (30)
  723.  
  724. C:\Users\EsperJB\Desktop\EECS2510\DataStructureComparison\x64\Debug\BinarySearchComparison.exe (process 18508) exited with code -1073741819.
  725. Press any key to close this window . . .
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement