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.

اخر الاخبار

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

جولة تفقدية لمتابعة خطة تنظيم مداخل المعزّين المشاركين في عزاء ركضة طويريج

لتعزيز التعاون الأكاديمي والبحثي.. جامعة الكفيل توقع اتفاقيتي توأمة مع جامعتين عراقيتين

المجمَع العلميّ يواصل إقامة مجلسه العزائي بذكرى شهادة الإمام الحسين (عليه السلام) في النجف الأشرف

قسم حفظ النظام يواصل تنفيذ خطته لتنظيم سير المواكب والزائرين في شهر المحرم

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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