Why use binary search if there’s ternary search?

by

Actually, people do use k-ary trees for arbitrary k.

This is, however, a tradeoff.

To find an element in a k-ary tree, you need around k*ln(N)/ln(k) operations (remember the change-of-base formula). The larger your k is, the more overall operations you need.

The logical extension of what you are saying is “why don’t people use an N-ary tree for N data elements?”. Which, of course, would be an array.

Related Contents:

  1. Skip List vs. Binary Search Tree
  2. Find kth smallest element in a binary search tree in Optimum way
  3. B-tree faster than AVL or RedBlack-Tree? [closed]
  4. The best way to calculate the height in a binary search tree? (balancing an AVL-tree)
  5. Check if a binary tree is a mirror image or symmetric
  6. How to implement a queue using two stacks?
  7. What is the difference between tree depth and height?
  8. How to find the lowest common ancestor of two nodes in any binary tree?
  9. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  10. How to create the most compact mapping n → isprime(n) up to a limit N?
  11. Red black tree over avl tree
  12. What is the advantage to using Bloom filters?
  13. How to implement a binary tree?
  14. design a stack such that getMinimum( ) should be O(1)
  15. How to determine if binary tree is balanced?
  16. Check if two linked lists merge. If so, where?
  17. Why does Dijkstra’s algorithm use decrease-key?
  18. Hash table runtime complexity (insert, search and delete)
  19. Most efficient way to store thousand telephone numbers
  20. Suffix tree and Tries. What is the difference?
  21. Algorithms based on number base systems? [closed]
  22. Choice of programming language for learning data structures and algorithms [closed]
  23. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  24. Algorithm for autocomplete?
  25. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  26. Why are Fibonacci numbers significant in computer science?
  27. Storing 1 million phone numbers [closed]
  28. Binary Trees vs. Linked Lists vs. Hash Tables
  29. Difference between back tracking and dynamic programming
  30. How do you validate a binary search tree?
  31. Reverse the ordering of words in a string
  32. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  33. Javascript data structures library [closed]
  34. How does 3D collision / object detection work?
  35. Good algorithm and data structure for looking up words with missing letters?
  36. How to implement 3 stacks with one array?
  37. Why is O(n) better than O( nlog(n) )?
  38. Algorithm/Data Structure Design Interview Questions [closed]
  39. Hashing a Tree Structure
  40. Finding anagrams for a given word
  41. What exactly is augmenting path?
  42. Applications of red-black trees
  43. Which data structures and algorithms book should I buy? [closed]
  44. Hash table vs Balanced binary tree [closed]
  45. Strategy to find your best route via Public Transportation only?
  46. find the max difference between j and i indices such that j > i and a[j] > a[i] in O(n)
  47. What is the difference between an on-line and off-line algorithm?
  48. Rebalancing an arbitrary BST?
  49. Trie complexity and searching
  50. Computing set intersection in linear time?

Leave a Comment