جستجو سه‌تایی

جستجو سه‌تایی
در علوم کامپیوتر رویه‌ی جستجو ترنری مهارتی برای پیدا کردن مقدار بیشینه یا کمینه در توابع اکید است. در این رویه مشخص می‌کنیم که مقدار بیشینه یا کمینه تابع نمی‌تواند در یک سوم ابتدا یا انتهای دامنه‌ی تابع وجود داشته باشد. سپس همین شیوه را بر روی دو سوم باقی‌مانده به کار می‌بریم. جستجو سه‌تایی نمومه‌ای از روش الگوریتم تقسیم و حل است(الگوریتم جستجو را ببینید.)
تابع
فرض کنید ما به دنبال بیشینه هستیم و می‌دانیم این مقدار بین و قرار دارد. برای این که الگوریتم قابل اعمال باشند، یک مقدار باید وجود داشته باشد به طوری که:
به ازای همه مقادیر و ، که داریم
به ازای همه مقادیر و ، که داریم
الگوریتم
تابع اکید را روی بازه در نظر بگیرید. دو نقطه‌ی و را در این بازه انتخاب می‌کنیم.
بنابراین در این صورت سه حالت وجود دارد :
اگر ، مقدار بیشینه نمی‌تواند دربازه سمت چپ واقع شود-- . این بدان معنی است که مقدار بیشینه در فاصله قرار دارد.
اگر ، مقدار بیشینه نمی‌تواند دربازه سمت راست واقع شود-- . این بدان معنی است که مقدار بیشینه در فاصله قرار دارد.
اگر ، این جستجو باید در بازه انجام شود. این حالت را می‌تونیم به هر یک از حالت‌های قبل برای ساده شدن رویه نسبت دهیم.
این فرایند تا زمانی ادامه پیدا می‌کند که بازه حاصل از مقدار ثابت از پیش تعیین شده کوچکتر شود.
انتخاب نقاط و :
m1 = l + (r-l)/3
m2 = r - (r-l)/3
زمان اجرا
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)
f(rightThird):
return ternarySearch(f, leftThird, right, absolutePrecision)
else:
return ternarySearch(f, left, rightThird, absolutePrecision)
درخت جستجوی سه‌تایی
درخت جستجوی سه‌تایی یکی از جالب‌ترین داده‌ساختارهادر زمینه دانش خوداست، زیرا این درخت ذخیره‌سازی بهینه را با سریع پیدا کردن ترکیب می‌کندو توانایی جستجوی پیشوندرا نیز دارد.
قسمتی از نظریه
درخت جستجو سه تایی کمی پیچیده‌تر از درخت جستجو دوتایی است. علاوه بر درخت جستجوی دودویی، اشاره گر سومی در هر گره وجود دارد. زمانی که بر روی درخت حرکت می‌کنیم، این اشاره‌گرهنگامی که مقداری که مقایسه می‌شود؛ با مقدار گره برابر باشد، استفاده می‌گردد.در نتیجه این درخت سه اشاره‌گر چپ، راست، و برابر دارد. که در شکل زیر مشاهده می‌کنید.
شکل زیر درخت جستجو سه تایی رشته‌های "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 -- !string.empty? -- self.value)
head, tail = string.partition
if head
self.value
return @right.search(string) if @right
end
end
پیاده‌سازی کلاس string :
def search(string)class String
def partition
head, tail
end
# First character.
def head
(self.length>= 1) ? self0.chr : nil
end
# Cut the first character from the string and return the tail.
def tail
(self.length>= 2) ? self : nil
end
end
پیاده‌سازی کلاس درخت جستجوی سه‌تایی :
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
self.value
@right = Tst.new unless @right
@right.insert(string)
end
end
def search(string)
return false unless (string -- !string.empty? -- self.value)
head, tail = string.partition
if head
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) -- value.length == 1
end
def ending_here
@ending = true
end
def ending?
@ending
end
end