Дървовидни структури съществуват две дефиниции на дървовидна структура или дърво. Нерекурсивна
Изтегляне 1.39 Mb.
|
Свързани:
топологично сортиране на граф, пропускливост на мрежа, МПТПротоколПлан
| m/2<= i <= m
- За корена брой наследници i e 2 <= i <= m; - Всички пътища от корена до произволно листо имат еднаква дължина. Червено-черни дървета (Red-Black Trees) Червено-черно дърво се нарича балансирано (но не идеално балансирано!) двоично дърво за претърсване (ВST), в което всеки връх е означен или като червен, или като черен и допълнително са изпълнени следните свойства: 1. Всеки връх или е червен, или е черен; 2. Коренът е черен; 3. Всички външни възли (върхове със стойност NULL) са черни; 4. Ако даден връх е червен, то двата му наследника са черни, освен това всеки червен възел има черен родител; 5. Всички пътища от произволен връх Т до произволно листо от поддървото с корен Т съдържат еднакъв брой черни върхове. В нито един от пътищата на R-D-дърво няма два последователни червени възела! Кодове на Huffman Едно от приложенията на двоичните дървета е в компресирането на данни. ASCII кода на всеки символ ни дава точно 8 бита за записване (и съхраняване) на символа. Този код е пример за кодиране с фиксирана дължина на кода. Кодирането на Хафмън използува свойството, че не всички символи в предаван текст или кадър се появяват с еднаква честота. Например в кадър, обхващащ символни стрингове, определени символи ще се срещат по-често, отколкото други. Следователно, вместо да използуват символни кодове с фиксирана дължина, може да се приложи схема на кодиране с неравномерен(по дължина) код, при която по-често срещаните символи се кодират с по-къси думи. Този подход може да бъде класифициран като статистическо кодиране. Поради различния брой битове на символ трябва да се използуват бит-ориентирани протоколи за обмен. В началото символният стринг, подлежащ на предаване, се анализира и се определят типовете символи и относителната им честота на появяване. Операцията по кодирането включва след това създаването на небалансирано дърво, при което някои от разклоненията му са с кодови думи, по-къси от другите. Степента на разбалансираност е функция на относителната честота на срещане на символите:- колкото по-разпръснато е разпределението, толкова по-разбалансирано е дървото. Резултантното дърво е известно като дърво на кода на Хафмън. Хафмъновото(кодово) дърво е двоично дърво с разклонения (клони), на които са присвоени стойности 0 и 1. Базата на дървото, нормално геометричният му връх, е известна в практиката като коренен възел или корен, а точката, в която има разклонение, като наследник (възел-разклонение). Завършващата точка на клон се нарича лист(листов възел). Към него са присъединени символите, които се кодират. ** Алгоритъм на Хъфман за получаване на оптимално двоични дърво. 1. Всички срещащи се в текста символи са листа на дървото с тегла броя на срещанията на символа в текста; 2. Всички други възли на дървото имат тегла 0; 3. В началото разглеждаме всички листа като отделни дървета (Хъфманова гора); 4. Намираме две дървета с най-малки претеглени дължини; 5. Построяваме ново дърво, като създаваме нов възел (корен) с наследници - двете поддървета; 6. Пресмятаме претеглената дължина на новото дърво (сума от претеглените дължини на двете поддървета); 7. Отиваме на 4., ако имаме поне 2 дървета. Кодирането на символите от текста (листа на дървото) се получава от единствения път до корена. Проследяваме пътя от корена до върха и при отиване в ляв наследник кодираме с 0, а при отиване на десен наследник - с 1. Кодираният текст получаваме, като редица от кодовете на отделните символи. За да можем да декодираме текста, е необходимо да имаме кодирания текст и Хъфмановото дърво, с което са кодирани символите на текста. Движим се от корена на дървото до достигане на листо - наляво или надясно в зависимост от прочетения код. Записваме символа от листото и тръгваме пак от корена. Изтегляне 1.39 Mb. Сподели с приятели:
|