Прэфікснае дрэва

З Вікіпедыі, свабоднай энцыклапедыі

У інфарматыцы, прэфікснае дрэва — гэта ўпарадкаванае дрэва, якое выкарыстоўваецца як мноства ці асацыятыўны масіў, ключамі якога звычайна з’яўляюцца радкі. У адрозненне ад двайковых дрэваў, у вузлах дрэва не захоўваецца ключ, звязаны с вузлом. Замест гэтага кожнаму вузлу адпавядае агульны прэфікс ключоў (і ў вузле захоўваецца толькі адна літара, калі ключы — радкі). Каб атрымаць значэнне прэфікса ці ключа, якое адпавядае дадзенаму вузлу, трэба прайсці шлях ад кораня да гэтага вузла і злучыць усе літары. Адпаведна, усе нашчадкі вузла маюць агульны прэфікс, звязаны з гэтым вузлом. Корань дрэва звязаны з пустым радком. Звычайна значэнні звязаны толькі з лістамі дрэва і з некаторымі ўнутранымі вузламі, якія адпавядаюць поўным ключам, а не проста прэфіксам.

Спасылкі[правіць | правіць зыходнік]