Как создать левое каноническое дерево двоичного поиска?

Question

Я изучаю структуру данных, и мне нужно построить левое каноническое двоичное дерево поиска, также известное как левое сбалансированное двоичное дерево поиска.

Пример:

Я понятия не имею, где и как начать строить это дерево. Может ли кто-нибудь показать мне, как это сделать. Возможно, на простом примере с элементами из 1, 2, 3, ... до 10.

Answer 1

На практике мы сначала находим наибольшую мощность двух M = 2^n, так что M ≤ N, где N - число элементы мы хотите вставить. Дерево будет удерживать элементы M - 1 на всех уровнях, исключая самый нижний. Сам самый нижний уровень будет содержать элементы M, разделенные между M/2 в левом поддереве и M/2 в правом поддереве.

Вычислим остальное R = N - (М - 1), а затем, если R ≤ M/2

LT = (M − 2)/2 + R 
RT = (M − 2)/2 

еще, если R> M/2

LT = (M − 2)/2 + M/2 
RT = (M − 2)/2 + R − M/2 

---

ПРИМЕР:

В примере (2, 3, 7, 9, 11) мы имеем N = 5 элементов и M = 4, поэтому R = 5- (4-1) = 2. Следовательно, LT равно 3, а RT равно 1. Следовательно, 9 становится срединным элементом, используемым в качестве корневого узла, а 2,3,7 помещается в левое поддерево, тогда как 11 становится правильным деревом. Мы рекурсивно вычисляем все дерево.

Источник: http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/2535/pdf/imm2535.pdf

ВАШ ПРИМЕР:

У Вас есть элементы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

N = 10 
M = 2^n where M ≤ N 
M = 8 
R = 10 - (8 - 1) = 3 

Таким образом, действует 3 ≤ M/2.

LT = (M - 2)/2 + R 
LR = 6 
RT = (M - 2)/2 
RT = 3 

Таким образом, в левом поддереве есть элементы 1, 2, 3, 4, 5, 6. В правом поддереве элементы 8, 9, 10 и 7 представляет собой средний показатель.

Проведем корневой узел 7.

---

Мы делаем то же самое, то для LT элементов 1, 2, 3, 4, 5, 6.

N = 6 
M = 2^n where M ≤ N 
M = 4 
R = 6 - (4 - 1) = 3 

Таким образом, 3 ≤ M/2 не действует.

LT = (M - 2)/2 + M/2 
LT = 3 
RT = (M - 2)/2 + R - M/2 
RT = 2 

В левом поддереве есть элементы 1, 2, 3. В правом поддереве являются элементы 5, 6 и 4, средний.

Мы рисуем 4 как левый ребенок из 7.

---

Мы делаем то же самое, то для LT элементов 1, 2, 3 элемента 1, 2, 3, 4, 5, 6.

N = 2 
M = 2^n where M ≤ N 
M = 2 
R = 3 - (2 - 1) = 2 

Таким образом, 2 ≤ M/2 не является действительным ,

LT = (M - 2)/2 + M/2 
LT = 1 
RT = (M - 2)/2 + R - M/2 
RT = 1 

В левом поддереве есть элемент 1. В правом поддереве есть элемент 3 и 2 является медианным.

Проведем 2 в левом ребенке 4.

---

Логически затем, 1 оставляют ребенок 2 и 3 является правильным ребенком 2.

По правилу, если есть только два элемента , правый элемент является медианным (корневой узел). Таким образом, 6 - правильный ребенок из 4 и 5 - левый ребенок из 6.

Мы делаем то же самое для RT (справа детей корневого узла 7) с элементами 8, 9, 10, где 9 является медианным, а 8 - левым дочерним из 9 и 10 является правильным ребенком из 9.

Окончательное дерево должно выглядеть следующим образом.