جستجو سه‌تایی کیست؟ توضیح بده.
جستجو سه‌تاییدر علوم کامپیوتر رویه ی جستجو ترنری مهارتی برای پیدا کردن مقدار بیشینه یا کمینه در توابع أکید است. در این رویه مشخص می‌کنیم که مقدار بیشینه یا کمینه تابع نمی‌تواند در یک سوم ابتدا یا انتهای دامنه ی تابع وجود داشته باشد. سپس همین شیوه را بر روی دو سوم باقی‌مانده به کار می‌بریم. جستجو سه‌تایی نمونه‌ای از روش الگوریتم تقسیم و حل است(الگوریتم جستجو را ببینید.)Ternary searchتابع.فرض کنید ما به دنبال بیشینۀ formula_1 هستیم و می دانیم این مقدار بین formula_2 و formula_3 قرار دارد. برای این که الگوریتم قابل اعمال باشند، یک مقدار formula_4 باید وجود داشته باشد به طوری که: الگوریتم.تابع اکید formula_1 را روی بازۀ formula_12 در نظر بگیرید. دو نقطه ی formula_13 و formula_14 را در این بازه انتخاب می‌کنیم.بنابراین formula_15در این صورت سه حالت وجود دارد :این فرایند تا زمانی ادامه پیدا می‌کند که بازۀ حاصل از مقدار ثابت از پیش تعیین شده کوچکتر شود.انتخاب نقاط formula_13 و formula_14 : زمان اجرا. T(n) = T(2/3 * n) + c (Θ(log nرویۀ بازگشتی.def ternarySearch(f, left, right, absolutePrecision): #left and right are the current bounds; the maximum is between them if (right - left) &lt;absolutePrecision: return (left + right)/2 leftThird = (2*left + right)/3 rightThird = (left + 2*right)/3 if f(leftThird)&gt; f(rightThird): return ternarySearch(f, leftThird, right, absolutePrecision) else: return ternarySearch(f, left, rightThird, absolutePrecision)Ternary searchدرخت جستجوی سه‌تایی.درخت جستجوی سه‌تایی یکی از جالب‌ترین داده‌ساختارهادر زمینه دانش خوداست، زیرا این درخت ذخیره‌سازی بهینه را با سریع پیدا کردن ترکیب می‌کندو توانایی جستجوی پیشوندرا نیز دارد.قسمتی از نظریه.درخت جستجو سه تایی کمی پیچیده‌تر از درخت جستجو دوتایی است. علاوه بر درخت جستجوی دودویی، اشاره گر سومی در هر گره وجود دارد. زمانی که بر روی درخت حرکت می‌کنیم، این اشاره‌گرهنگامی که مقداری که مقایسه می‌شود؛ با مقدار گره برابر باشد، استفاده می‌گردد.در نتیجه این درخت سه اشاره‌گر چپ، راست، و برابر دارد. که در شکل زیر مشاهده می‌کنید.شکل زیر درخت جستجو سه تایی رشته‌های "as", "at", "cup", "cute", "he", "i" and "us" را نشان می‌دهد: c a u h t t e u s p e i sپیاده‌سازی.پیاده‌سازی تابع search :def search(string) return false unless (string &amp;&amp; !string.empty? &amp;&amp; self.value) head, tail = string.partition if head &lt;self.value return @left.search(string) if @left elsif head == self.value return true if !tail &amp;&amp; self.ending? return @equal.search(tail) if @equal elsif head&gt; self.value return @right.search(string) if @right endendپیاده‌سازی کلاس string :def search(string)class String def partition [head, tail] end # First character. def head (self.length&gt;= 1) ? self[0].chr : nil end # Cut the first character from the string and return the tail. def tail (self.length&gt;= 2) ? self[1..-1] : nil endendپیاده‌سازی کلاس درخت جستجوی سه‌تایی :class Tst def initialize @left = @equal = @right = nil @ending = false end def insert(string) raise ArgumentError unless string.is_a?(String) head, tail = string.partition if self.value.nil? # self.value ? self.value = head # self.value ? end if head &lt;self.value @left = Tst.new unless @left @left.insert(string) elsif head == self.value if tail @equal = Tst.new unless @equal @equal.insert(tail) else self.ending_here() end elsif head&gt; self.value @right = Tst.new unless @right @right.insert(string) end end def search(string) return false unless (string &amp;&amp; !string.empty? &amp;&amp; self.value) head, tail = string.partition if head &lt;self.value return @left.search(string) if @left elsif head == self.value return true if !tail &amp;&amp; self.ending? return @equal.search(tail) if @equal elsif head&gt; self.value return @right.search(string) if @right end end alias :«:insert alias :[] :search protected def value @value end def value=(value) raise ArgumentError unless acceptable?(value) @value = value end def acceptable?(value) value.is_a?(String) &amp;&amp; value.length == 1 end def ending_here @ending = true end def ending? @ending endend