“Tree Searching”的概念、定义、习题解题方法及翻译-数学辞典

单词

Tree Searching

释义

Tree Searching

N.B. A detailed on-line essay by S. Finchwas the starting point for this entry.

In database structures, two quantities are generally of interest: the average number of comparisons required to

: 1. Find an existing random record, and
: 2. Insert a new random record into a data structure.

Some constants which arise in the theory of digital tree searching are

			(1)
			(2)

Erdös (1948) proved that

is Irrational. The expected number of comparisons for a successful search is

			(3)
			(4)

and for an unsuccessful search is

			(5)
			(6)

Here

, and

are small-amplitude periodic functions,and Lg is the base 2 Logarithm. The Variance for searching is

(7)

and for inserting is

(8)

The expected number of pairs of twin vacancies in a digital search tree is

(9)

where

			(10)
			(11)
			(12)
			(13)

and


			(14)

(Flajolet and Sedgewick 1986). The linear Coefficient of

fluctuates around

(15)

which can also be written

(16)

(Flajolet and Richmond 1992).

References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/bin/bin.html

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/dig/dig.html

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/qdt/qdt.html

Flajolet, P. and Richmond, B. ``Generalized Digital Trees and their Difference-Differential Equations.'' Random Structures and Algorithms 3, 305-320, 1992.

Flajolet, P. and Sedgewick, R. ``Digital Search Trees Revisited.'' SIAM Review 15, 748-767, 1986.

Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, pp. 21, 134, 156, 493-499, and 580, 1973.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。