Двоична купчина срещу двоично дърво C++

Търсенето в постоянно време на минимума и максимума се постига чрез съхраняване на препратки към най-левия и най-десния възли на RB-дървото в структурата на заглавката на картата. Ето коментар fот изходния код на RB- дърво, шаблон, от който се извлича изпълнението на std::set, std::map и std::multimap:

заглавната клетка се поддържа с връзки не само към корена, но също и към най-левия възел на дървото, за да се даде възможност за постоянно време begin(), и към най-десния възел на дървото, за да се даде възможност за линейно представяне на времето, когато се използва с алгоритмите за общ набор ( set_union и т.н.)

Компромисът тук е, че тези указатели трябва да се поддържат, така че операциите за вмъкване и изтриване ще трябва да извършат друга „операция за поддръжка“. Вмъкванията и изтриванията обаче вече се извършват в логаритмично време, така че няма допълнителни асимптотични разходи за поддържане на тези указатели.

Поне в типична реализация std::set (и std::map) ще бъдат имплементирани като резбовано двоично дърво¹. С други думи, всеки възел съдържа не само указател към неговите (до) две деца, но също така към предишния и следващия възел по ред. След това самият клас set има указатели не само към корена на дървото, но и към началото и края на списъка с нишки от възли.

За търсене на възел по ключ се използват нормалните двоични указатели. За преминаване на дървото в ред се използват указателите на резби.

Това наистина има редица недостатъци в сравнение с двоичната купчина. Най-очевидният е, че той съхранява четири указателя за всеки елемент от данни, където двоичната купчина може да съхранява само данни, без указатели (връзките между възлите са имплицитни в позициите на данните). В екстремен случай (напр. std::set<char>) това може да доведе до използване на много повече място за съхранение за указателите, отколкото за данните, които всъщност ви интересуват (напр. на 64-битова система, можете да получите 4 указателя от 64 бита всеки, за съхраняване на всеки 8-битов знак). Това може да доведе до лошо използване на кеша, което (от своя страна) намалява скоростта.

В допълнение, всеки възел обикновено ще бъде разпределен индивидуално, което може да намали локалността на препратката доста зле, като отново навреди на използването на кеша и допълнително намали скоростта.

Като такова, въпреки че резбованото дърво може да намери минимума или максимума, или да премине към следващия или предишния възел в O(1) и да търси всеки даден елемент в O(log N), константите могат да бъдат значително по-високи от това, същото с купчина. В зависимост от размера на елементите, които се съхраняват, общото използвано хранилище може да бъде значително по-голямо, отколкото при купчина (най-лошият случай е очевидно, когато във всеки възел се съхраняват само малко данни).

_{1. С прилагане на някакъв алгоритъм за балансиране - най-често червено-черно, но понякога AVL дървета или B-дървета. Могат да се използват произволен брой други балансирани дървета (напр. алфа-балансирани дървета, k-съседни дървета, двоични b-дървета, общи балансирани дървета).}

Не съм експерт по картите, но връщането на първия елемент от карта ще се счита за нещо като „корен“. винаги има указател към него, така че времето за търсене ще бъде моментално. Същото ще важи и за BSTree, тъй като очевидно има основен възел, след това 2 възела извън него и т.н. ).

O(log(N)) обикновено се използва само за получаване на оценка на най-лошия сценарий. Така че, ако имате напълно небалансирано BSTree, всъщност ще имате O(N), така че ако търсите последния възел, трябва да направите сравнение с всеки възел.

Не съм много сигурен в последното ви твърдение, въпреки че картата е различна от самобалансиращо се дърво, те се наричат ​​AVL дървета (или така са ме учили). Картата използва „ключове“, за да организира обектите по определен начин. Ключът се намира чрез сериализиране на данните в число и числото в по-голямата си част се поставя в списък.