Stack Overflow
Stack Overflow

Questions tagged [ternary-tree]

Ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right".

Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child. Ternary trees are used to implement Ternary search trees and Ternary heaps.

35 questions
43
votes
15 answers

Why use binary search if there's ternary search?

I recently heard about ternary search in which we divide an array into 3 parts and compare. Here there will be two comparisons but it reduces the array to n/3. Why don't people use this much?
mousey
  • 11,601
  • 16
  • 52
  • 59
11
votes
3 answers

How do you perform a deep copy of a ternary tree in Go?

I'm attempting to perform a deep copy of the following struct: // Ternary Tree type Tree struct { Left *Tree Mid *Tree Right *Tree Value interface{} Parent *Tree Orientation string IsTerminal bool Type string } The…
Adam Soffer
  • 1,614
  • 5
  • 20
  • 36
10
votes
4 answers

Balancing a ternary search tree

How does one go about 'balancing' a ternary search tree? Most tst implementations don't address balancing, but suggest inserting in an optimal order (which I can't control.)
uroc
  • 3,993
  • 3
  • 21
  • 18
6
votes
2 answers

Ternary Search Tree

struct Ternary { char current; bool wordend; Ternary* left; Ternary* mid; Ternary* right; Ternary(char c='@',Ternary* l=NULL, Ternary* m=NULL, Ternary* r=NULL,bool end=false) { wordend=end; current=c; …
CoderXX
  • 81
  • 1
  • 4
3
votes
3 answers

Case Insensitive Ternary Search Tree

I had been using Ternary Search Tree for a while, as the data structure to implement a auto complete drop down combo box. Which means, when user type "fo", the drop down combo box will display foo food football The problem is, my current used of…
Cheok Yan Cheng
  • 47,586
  • 132
  • 466
  • 875
2
votes
1 answer

Find minimun Vertext-Cover using a ternary tree

I found some algorithms to find a minimun Vertex-Cover like using a binary search tree but I read that using a ternary tree is even better. But i can't find any info about it or think of an algorithm for it. Does somebody know how it can be done?
Emanuel Dementei
  • 23
  • 4
2
votes
1 answer

Majority tree evaluation

Consider a complete ternary tree of depth h, composed of a root attached to three complete ternary trees of depth h - 1. There are n = 3^h leaves and each leaf has a boolean value associated to it. Each internal node, including the root, equals the…
Die5
  • 23
  • 3
2
votes
3 answers

Haskell: Find a value in a Ternary Tree and the tree is not sorted

For now I have the tree data type: data TernaryTree a = EmptyTree | Node a (TernaryTree a) (TernaryTree a) (TernaryTree a) deriving (Show) And I am trying to create a function that can loop up a value in the…
Avioddddd
  • 21
  • 3
2
votes
3 answers

Iterate all coprime pairs using constant space?

I can generate all coprime pairs by following the ternary-tree algorithm listed on wikipedia: https://en.wikipedia.org/wiki/Coprime_integers Quickly: Start with two coprime branches: (2,1), (3,1), then iterate: Branch 1: (2m-n,m) Branch 2:…
user318904
  • 2,968
  • 4
  • 28
  • 37
2
votes
0 answers

A loop that will read a text file and add the info into nodes and then to a tree

I am creating a program that reads a text file and sets the info from it into nodes in a ternary tree. I have created the addNode method already but now I am working on the method that will read the imported textile and extract the correct info, set…
Angela Castello
  • 63
  • 5
2
votes
2 answers

How to convert the below recursive functions to for loop iterations

Iterator words = treeSearch.getItems().iterator(); int addCount = 0; while (words.hasNext()) { numWords++; rootNode = add(objectToReference, addCount++, (ITreeSearch) words.next(), 0, rootNode); } //Add to the Tree private TernaryTreeNode…
Navaneeth Sen
  • 6,315
  • 11
  • 53
  • 82
1
vote
1 answer

Ternary tree time complexity

I've an assignment to explain the time complexity of a ternary tree, and I find that info on the subject on the internet is a bit contradictory, so I was hoping I could ask here to get a better understanding. So, with each search in the tree, we…
Jskoven
  • 31
  • 1
1
vote
1 answer

Haskell: ternary tree average, with nested `where`

I was trying to calculate the average of a ternary tree. It seems not possible to finish it inside one function. Is there any way to solve this question, or it's necessary to use two functions? Thanks. -- define a tree data Ttree t = Nil | Node3 t…
Woden
  • 1,054
  • 2
  • 13
  • 26
1
vote
1 answer

Divide and Conquer Ternary Tree Search

I am trying to solve an exercise where you are given a perfect ternary tree in which each node contains an integer. We want to calculate how many internal nodes meet these specifications: The number of the node is larger than all its children It's…
Chris Costa
  • 653
  • 4
  • 15
1
vote
0 answers

Depth of ternary tree - MLM Level

I am working on a MLM in php where every node can have only 3 children. the MLM have N Levels. the Level of any parent node will be equal to the lowest level of its child node + 1. child at depth n has Level = 1. function calculate_level($starId=0)…
dfeast
  • 36
  • 1
  • 4
1
2 3