Съдържание
- Определение - Какво означава самобалансиращо дърво за двоично търсене?
- Въведение в Microsoft Azure и Microsoft Cloud | В това ръководство ще научите какво представлява компютърните изчисления и как Microsoft Azure може да ви помогне да мигрирате и стартирате бизнеса си от облака.
- Техопедия обяснява самобалансиращо дърво за двоично търсене
Определение - Какво означава самобалансиращо дърво за двоично търсене?
Самобалансиращо бинарно дърво за търсене е вид структура от данни, която се самонастройва, за да осигури последователни нива на достъп до възел. В самобалансиращо бинарно дърво за търсене връзките от горния възел към допълнителни възли се сортират и пренастройват така, че дървото да е равномерно, а линиите на траекторията на търсене за всеки краен възел са равни по дължина.
Самобалансиращото дърво на двоичното търсене е също така известно като балансирано дърво или дърво с балансирано по височина двоично търсене.
Въведение в Microsoft Azure и Microsoft Cloud | В това ръководство ще научите какво представлява компютърните изчисления и как Microsoft Azure може да ви помогне да мигрирате и стартирате бизнеса си от облака.
Техопедия обяснява самобалансиращо дърво за двоично търсене
Като цяло бинарно дърво за търсене предоставя структура от данни с един възел в горната част и един или два възла, свързани към него на всяко следващо ниво. Двоичните дървета за търсене поддържат три операции - операторите могат да вмъкват компоненти, да изтриват компоненти или да търсят някакво число или друго съдържание на възли. Част от ползата от бинарните дървета за търсене е, че системата може да сортира, за да игнорира половината от дървото на всяко ниво, което води до по-ефективни натоварвания за търсене.
Положителният аспект на самобалансиращото се двоично дърво за търсене е, че достъпът до възел е равен - например, вместо да се налага да преминавате пет стъпки от едната страна на дървото или три стъпки от другата страна на дървото, заради самостоятелността -настроена структура на възел, търсенето ще извърши само определен брой стъпки (n) към всеки даден краен възел. Това се постига чрез отделяне на отделни връзки на възел и замяната им с бинарни, за да се съкратят конкретни крайници на дървото.
Недостатъкът на самобалансиращо бинарно търсене три е, че той работи само ако връзките на възлите са „ниво-агностични“ - с други думи, ако отделен възел може да бъде пренастроен на предварително ниво, за да се съкрати клона на дървото , Например, ако самобалансиращо бинарно дърво за търсене е съставено с дадено число в горната част и две следващи числа от двете страни и има верига от три допълнителни числа с връзки с един възел, корекцията на дървото ще бъде поставена петият възел заедно с третия възел вместо четвъртия възел, така че третият възел да има два свързващи възли вместо един. Ако обаче структурата на данните трябва да идентифицира конкретно съдържание на възел като свързано в конкретна връзка родител / дете, приспособяването на тези възли да съвпада с равномерността на структурата на дървото няма да работи.