Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Log of adding every c-string that follows the structure { letter, '\0' }
- in decreasing order from o to a, with structures printed.
- 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.
- The skip list is a probabilistic list with structure:
- LEFT SENTINEL
- STUFF
- RIGHT SENTINEL
- And a printing structure
- CONTENTS_count :: height
- 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).
- o ----------------------------------
- AVL:
- o_2
- BST:
- o_2
- RBT:
- o_2!B
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 1
- o_2 :: 1
- RIGHT_SENTINEL :: 1
- n ----------------------------------
- AVL:
- o_2
- n_2
- BST:
- o_2
- n_2
- RBT:
- o_2!B
- n_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 2
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 2
- m ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- BST:
- o_2
- n_2
- m_2
- RBT:
- o_2!R
- n_2!B
- m_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 6
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 6
- l ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- BST:
- o_2
- n_2
- m_2
- l_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 6
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 6
- k ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- RBT:
- o_2!B
- n_2!B
- m_2!R
- l_2!B
- k_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 6
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 6
- j ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!R
- k_2!B
- j_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 6
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 6
- i ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!R
- k_2!R
- j_2!B
- i_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- h ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- RBT:
- o_2!B
- n_2!R
- m_2!B
- l_2!B
- k_2!B
- j_2!R
- i_2!B
- h_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- g ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- RBT:
- o_2!B
- n_2!R
- m_2!B
- l_2!B
- k_2!B
- j_2!R
- i_2!R
- h_2!B
- g_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- f ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!B
- i_2!B
- h_2!R
- g_2!B
- f_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- e ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!B
- i_2!B
- h_2!R
- g_2!R
- f_2!B
- e_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- e_2 :: 2
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- d ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!R
- i_2!B
- h_2!B
- g_2!B
- f_2!R
- e_2!B
- d_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- d_2 :: 1
- e_2 :: 2
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- c ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!R
- i_2!B
- h_2!B
- g_2!B
- f_2!R
- e_2!R
- d_2!B
- c_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- c_2 :: 1
- d_2 :: 1
- e_2 :: 2
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- b ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- b_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- b_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!B
- i_2!B
- h_2!R
- g_2!B
- f_2!B
- e_2!B
- d_2!R
- c_2!B
- b_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- b_2 :: 1
- c_2 :: 1
- d_2 :: 1
- e_2 :: 2
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- a ----------------------------------
- AVL:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- b_2
- a_2
- BST:
- o_2
- n_2
- m_2
- l_2
- k_2
- j_2
- i_2
- h_2
- g_2
- f_2
- e_2
- d_2
- c_2
- b_2
- a_2
- RBT:
- o_2!B
- n_2!B
- m_2!B
- l_2!B
- k_2!B
- j_2!B
- i_2!B
- h_2!R
- g_2!B
- f_2!B
- e_2!B
- d_2!R
- c_2!R
- b_2!B
- a_2!R
- NIL: BLACK
- SKIP:
- LEFT_SENTINEL :: 7
- a_2 :: 6
- b_2 :: 1
- c_2 :: 1
- d_2 :: 1
- e_2 :: 2
- f_2 :: 4
- g_2 :: 3
- h_2 :: 1
- i_2 :: 7
- j_2 :: 1
- k_2 :: 2
- l_2 :: 1
- m_2 :: 6
- n_2 :: 2
- o_2 :: 1
- RIGHT_SENTINEL :: 7
- AVL: 0.513 seconds.
- BST: 0.513 seconds.
- RBT: 0.514 seconds.
- skip: 0.514 seconds.
- Base time: 0.515 seconds.
- Letters used: 16
- Approximate reasonable height: 4
- Maximum reasonable AVL height: 5.76
- AVL Height: 4
- BST Height: 15
- RBT Height: 6
- AVL Word count: 15 (30)
- BST word count: 15 (30)
- RBT word count: 15 (30)
- C:\Users\EsperJB\Desktop\EECS2510\DataStructureComparison\x64\Debug\BinarySearchComparison.exe (process 18508) exited with code -1073741819.
- Press any key to close this window . . .
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement