55:, 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.
26:
702:
The above picture is a balanced ternary search tree for the same set of 12 words. The low and high pointers are shown as angled lines, while equal pointers are shown as vertical lines. A search for the word "IS" starts at the root, proceeds down the equal child to the node with value "S", and stops
694:
each input word is shown beneath the node that represents it. In a tree representing words of lower case letters, each node has 26-way branching. Searches are very fast: A search for "IS" starts at the root, takes the "I" branch, then the "S" branch, and ends at the desired node. At every node, one
643:
is more complex than on external nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion or mid child.) A assigns its child to the new node and the new node
680:
that represents 12 two-letter words. All nodes on the left child have smaller values, while all nodes on the right child have greater values for all nodes. A search starts from the root. To find the word "ON", we compare it to "IN" and take the right branch. Every comparison could access each
690:
_ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ a b h i o t / \ / \ | / | \ /|\ | s t e y e n s t f n r o as at be by he in is it of on or to
698:
i / | \ / | \ b s o / | \ / \ | \ a e h n t n t | \ | / \ | s y e f r o \ t
388:
703:
there after two comparisons. A search for "AX" makes three comparisons to the first letter "A" and two comparisons to the second letter "X" before reporting that the word is not in the tree.
114:- Length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. In the example diagram, the tree has height of 2.
438:
631:
Say that the external node being added onto is node A. To add a new node after node A, A assigns the new node as one of its children and the new node assigns node A as its parent.
200:
462:
168:
603:
562:
527:
488:
108:- Length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
732:
259:
728:
668:
and A's parent to null. If it has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.
652:
Deletion is the process whereby a node is removed from the tree. Only certain nodes in a ternary tree can be removed unambiguously.
687:
Digital search tries to store strings character by character. The next picture is a tree that represents the same set of 12 words;
806:
16:
This article is about rooted trees with three children per node. For unrooted trees with three neighbors per node, see
644:
assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.
395:
52:
717:
684:
in / \ be of / \ / \ as by is or \ \ \ / \ at he it on to
127:
of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p.
17:
712:
59:
44:
780:
677:
36:
176:
727:
Two infinite ternary trees containing all primitive
Pythagorean triples are described in
619:
Nodes can be inserted into ternary trees in between three other nodes or added after an
750:
447:
153:
573:
538:
497:
467:
800:
661:
640:
620:
383:{\displaystyle M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}}
722:
665:
63:
623:. In Ternary trees, a node that is inserted is specified as to which child it is.
745:
84:- The node with no parents. There is at most one root node in a rooted tree.
25:
785:
664:), deletion is accomplished by setting the child of A's parent to
660:
Say that the node to delete is node A. If a node has no children (
24:
96:- Any node connected by a directed edge to its child or children.
134:
of a node is the number of descendants it has, including itself.
695:
accesses an array element, tests for null, and takes a branch.
779:
Price, H. Lee (2008). "The
Pythagorean Tree: A New Species".
202:
be the maximum number of nodes in a ternary tree of height h
102:- Any node connected to a parent node by a directed edge.
769:
Jon
Bentley and Bob Sedgewick (1998), Dr. Dobb's Journal
576:
541:
500:
470:
450:
398:
262:
179:
156:
597:
556:
521:
482:
456:
432:
382:
194:
162:
735:. The root node in both trees contains triple .
29:A simple ternary tree of size 10 and height 2.
8:
733:Formulas for generating Pythagorean triples
784:
575:
540:
499:
469:
449:
406:
399:
397:
356:
349:
340:
330:
319:
306:
261:
178:
155:
204:
120:- Nodes that share the same parent node.
78:- The link from the parent to the child.
762:
433:{\displaystyle {\frac {3^{h+1}-1}{2}}}
729:Tree of primitive Pythagorean triples
392:– Every tree of height h has at most
7:
58:Ternary trees are used to implement
14:
90:- Any node that has no children.
592:
577:
551:
542:
516:
501:
477:
471:
272:
266:
189:
183:
170:be height of a ternary tree.
1:
672:Comparison with other trees
656:Node with zero or one child
139:Properties of ternary trees
823:
15:
707:Examples of ternary trees
681:character of both words.
807:Trees (data structures)
676:The picture below is a
145:Maximum number of nodes
47:in which each node has
599:
558:
523:
484:
458:
434:
384:
335:
196:
164:
30:
600:
559:
524:
485:
459:
435:
385:
315:
197:
165:
28:
574:
539:
498:
468:
448:
396:
260:
195:{\displaystyle M(h)}
177:
154:
60:Ternary search trees
18:unrooted binary tree
718:Ternary binary tree
713:Ternary search tree
45:tree data structure
678:binary search tree
595:
570:is stored in TREE
554:
535:is stored in TREE
519:
494:is stored in TREE
480:
454:
430:
380:
192:
160:
31:
610:Common operations
457:{\displaystyle N}
428:
378:
254:
253:
163:{\displaystyle h}
814:
791:
790:
788:
776:
770:
767:
604:
602:
601:
598:{\displaystyle }
596:
563:
561:
560:
557:{\displaystyle }
555:
528:
526:
525:
522:{\displaystyle }
520:
489:
487:
486:
483:{\displaystyle }
481:
463:
461:
460:
455:
439:
437:
436:
431:
429:
424:
417:
416:
400:
389:
387:
386:
381:
379:
374:
367:
366:
350:
345:
344:
334:
329:
311:
310:
205:
201:
199:
198:
193:
169:
167:
166:
161:
37:computer science
822:
821:
817:
816:
815:
813:
812:
811:
797:
796:
795:
794:
778:
777:
773:
768:
764:
759:
742:
709:
700:
692:
685:
674:
658:
650:
637:
629:
617:
612:
572:
571:
537:
536:
496:
495:
466:
465:
446:
445:
402:
401:
394:
393:
352:
351:
336:
302:
258:
257:
175:
174:
152:
151:
141:
123:A node p is an
72:
21:
12:
11:
5:
820:
818:
810:
809:
799:
798:
793:
792:
771:
761:
760:
758:
755:
754:
753:
751:Tree structure
748:
741:
738:
737:
736:
725:
720:
715:
708:
705:
697:
689:
683:
673:
670:
657:
654:
649:
646:
641:internal nodes
636:
635:Internal nodes
633:
628:
627:External nodes
625:
616:
613:
611:
608:
607:
606:
594:
591:
588:
585:
582:
579:
565:
553:
550:
547:
544:
530:
518:
515:
512:
509:
506:
503:
479:
476:
473:
464:occupies TREE
453:
427:
423:
420:
415:
412:
409:
405:
377:
373:
370:
365:
362:
359:
355:
348:
343:
339:
333:
328:
325:
322:
318:
314:
309:
305:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
252:
251:
248:
244:
243:
240:
236:
235:
232:
228:
227:
224:
220:
219:
209:
191:
188:
185:
182:
159:
148:
147:
140:
137:
136:
135:
128:
121:
115:
109:
103:
97:
91:
85:
79:
71:
68:
33:
32:
13:
10:
9:
6:
4:
3:
2:
819:
808:
805:
804:
802:
787:
782:
775:
772:
766:
763:
756:
752:
749:
747:
744:
743:
739:
734:
730:
726:
724:
721:
719:
716:
714:
711:
710:
706:
704:
696:
688:
682:
679:
671:
669:
667:
663:
662:external node
655:
653:
647:
645:
642:
639:Insertion on
634:
632:
626:
624:
622:
621:external node
614:
609:
589:
586:
583:
580:
569:
566:
548:
545:
534:
531:
513:
510:
507:
504:
493:
474:
451:
443:
442:
441:
425:
421:
418:
413:
410:
407:
403:
390:
375:
371:
368:
363:
360:
357:
353:
346:
341:
337:
331:
326:
323:
320:
316:
312:
307:
303:
299:
296:
293:
290:
287:
284:
281:
278:
275:
269:
263:
249:
246:
245:
241:
238:
237:
233:
230:
229:
225:
222:
221:
217:
213:
210:
207:
206:
203:
186:
180:
171:
157:
146:
143:
142:
138:
133:
129:
126:
122:
119:
116:
113:
110:
107:
104:
101:
98:
95:
92:
89:
86:
83:
80:
77:
76:Directed Edge
74:
73:
69:
67:
65:
64:Ternary heaps
61:
56:
54:
50:
49:at most three
46:
42:
38:
27:
23:
22:
19:
774:
765:
723:Ternary heap
701:
693:
686:
675:
659:
651:
638:
630:
618:
567:
532:
491:
391:
255:
215:
211:
172:
149:
144:
131:
124:
117:
111:
105:
99:
93:
87:
81:
75:
57:
48:
41:ternary tree
40:
34:
746:Binary tree
568:Right Child
490:, then its
94:Parent Node
757:References
492:Left Child
444:If a node
100:Child Node
70:Definition
786:0809.4324
615:Insertion
533:Mid Child
511:−
419:−
369:−
317:∑
297:⋯
88:Leaf Node
801:Category
740:See also
648:Deletion
125:ancestor
731:and in
440:nodes.
118:Sibling
173:– Let
150:– Let
112:Height
51:child
781:arXiv
106:Depth
53:nodes
43:is a
666:null
132:size
130:The
82:Root
62:and
39:, a
250:40
242:13
35:In
803::
256:–
234:4
226:1
218:)
66:.
789:.
783::
605:.
593:]
590:1
587:+
584:k
581:3
578:[
564:.
552:]
549:k
546:3
543:[
529:.
517:]
514:1
508:k
505:3
502:[
478:]
475:k
472:[
452:N
426:2
422:1
414:1
411:+
408:h
404:3
376:2
372:1
364:1
361:+
358:h
354:3
347:=
342:i
338:3
332:h
327:0
324:=
321:i
313:=
308:h
304:3
300:+
294:+
291:9
288:+
285:3
282:+
279:1
276:=
273:)
270:h
267:(
264:M
247:3
239:2
231:1
223:0
216:h
214:(
212:M
208:h
190:)
187:h
184:(
181:M
158:h
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
