1
$\begingroup$

I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable to least. The number of items is fixed. The current implementation can be seen at https://dfdx.us/core-values-quiz/.

What matters most is minimizing the number of comparisons the user needs to input, or, more accurately, minimizing the amount of time the user requires to make each comparison times the number of comparisons.

Currently I offer two sorting methods: Quicksort and insertion into a binary tree. Compared to a self-balancing BST, Quicksort will always require more comparisons, but because each consecutive comparison is against a single item (the partition item), the brain doesn't need to make much of a context switch and can answer the questions quicker. The binary search tree will present fewer questions that take longer. I let the user decide which method they want to use, given the pros and cons of each.

Since the comparisons required to rebalance the tree are handled by the computer, and not the user, those comparisons don't need to be optimized at all, only the number of comparisons required to determine the relative position within the current tree. I believe this optimization is equivalent to, between each item's insertion, balancing the tree as perfectly as possible. That is, requiring the strictest balancing constraint.

The best algorithm I've tested is the AVL tree. While the AVL tree is pretty terrible for insertion/deletion times for most applications, it has a decent balancing constraint which results in great look-up speeds. The rebalancing between each insertion/deletion is what makes it unperformant, but since, compared to human input, those comparisons are negligible, it is very good for my situation.

My situation requires one more constraint: the user must never be presented with the same comparison twice. For the AVL tree, rebalancing breaks this constraint, so I've just memoized all of the user's answers in a dictionary. I can't imagine a situation in which this case couldn't be handled with that memoziation, but I figured I'd mention it nonetheless.

I really have two questions:

  1. Am I right with my assertion that balancing the tree as perfectly as possible guarantees the fewest number of prompts to the user?

  2. Is there a better balancing algorithm than an AVL tree?

Given that before the quiz begins, the items' order is randomized, even using a non-auto-balancing BST should result in a roughly balanced tree. I could see an argument being made that perfectly rebalancing after every insertion could actually produce a greater number of prompts, since each one will have as close to lg(n) prompts as possible; a slightly less balanced tree could potentially have a few "lucky" insertions that require a few less than lg(n), and a few "unlucky" insertions that require more, but that the lucky ones will, on average, outweigh the unlucky ones. (I hope that made sense.)

Improve this question
$\endgroup$
5
  • $\begingroup$ "Currently I offer two sorting methods: Quicksort and insertion into a binary tree". What is "insertion into a binary tree"? Did you mean forest? $\endgroup$
    – John L.
    May 8, 2019 at 1:02
  • $\begingroup$ "Balancing the tree as perfectly as possible guarantees the fewest number of prompts to the user". Where did you get this principle from? The usual guideline for requiring less number of comparisons is to make the remaining cases evenly split after each comparison. $\endgroup$
    – John L.
    May 8, 2019 at 1:06
  • $\begingroup$ @Apass.Jack what? Binary search trees let you insert new items into them. I don't know what you're talking about. And remaining cases splitting evenly IS what balancing a binary tree would do. $\endgroup$
    – dx_over_dt
    May 8, 2019 at 1:25
  • $\begingroup$ Now I see what you mean. I was tipped off balance when I see insertion alone. Have you considered merge-insertion? $\endgroup$
    – John L.
    May 8, 2019 at 1:47
  • $\begingroup$ Interesting. I may code that one up and run some simulations. $\endgroup$
    – dx_over_dt
    May 8, 2019 at 1:51

1 Answer 1

Reset to default
1
$\begingroup$

I realized, considering that memory and processing constraints are negligible in my situation, that it is trivial to produce a new, perfectly balanced tree from an in-order traversal of the unbalanced tree, where perfectly balanced means that the max depth of a leaf node is at most one more than the minimum depth of a leaf node.

For that matter, a tree isn't even necessary. Using a binary search over an ordered array to determine where to insert each new element is more efficient than using a binary search tree at all. Given that my input set is a fixed 58 items, using JavaScript's Array.prototype.splice() function is more than performant enough, and makes the code trivial, as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.