Binary Tree

A binary tree is a tree-like structure that is rooted and in which each vertex has at most two children and each child of a vertex is designated as its left or right child (West 2000, p. 101). In other words, unlike a proper tree, the relative positions of the children is significant.

Dropping the requirement that left and right children are considered unique gives a true tree known as a weakly binary tree (in which, by convention, the root node is also required to be adjacent to at most one graph vertex).

The height of a binary tree is the number of levels within the tree. The numbers of binary trees of height , 2, ... nodes are 1, 3, 21, 651, 457653, ... (OEIS A001699). A recurrence equation giving these counts is

(1)

with .

The number of binary trees with  nodes are 1, 2, 5, 14, 42, ... (OEIS A000108), which are the Catalan number .

For a binary tree of height  with  nodes,

(2)

These extremes correspond to a balanced tree (each node except the tree leaves has a left and right child, and all tree leaves are at the same level) and a degenerate tree (each node has only one outgoing branch), respectively.

For a search of data organized into a binary tree, the number of search steps  needed to find an item is bounded by

(3)

Partial balancing of an arbitrary tree into a so-called AVL binary search tree can improve search speed.

---

REFERENCES

Lucas, J.; Roelants van Baronaigien, D.; and Ruskey, F. "Generating Binary Trees by Rotations." J. Algorithms 15, 343-366, 1993.

Ranum, D. L. "On Some Applications of Fibonacci Numbers." Amer. Math. Monthly 102, 640-645, 1995.

Ruskey, F. "Information on Binary Trees." http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html.Ruskey, F. and Proskurowski, A. "Generating Binary Trees by Transpositions." J. Algorithms 11, 68-84, 1990.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 35, 1990.

Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 177-178, 1997.

Sloane, N. J. A. Sequences A000108/M1459, A001190/M0790, and A001699/M3087 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 101, 2000.

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تختتم مشاركتها في تقديم الخدمات لزائري مرقد الإمامين العسكريين (عليهما السلام)

وفد متحف الكفيل يطلع على الفنون التراثية والحرف الأصيلة في ورش مدينة أصفهان

قسم الشؤون الفكرية يواصل ترميم وثائق نادرة لحماية الذاكرة الوطنية

العتبة العباسية المقدسة تواصل إقامة مجلسها العزائي بذكرى شهادة الإمام الهادي (عليه السلام)

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength