Применение модели бинарного дерева в практических проектах

[Высший класс облачных вычислений] Обмен технологиями

Время публикации: 2017.04.14

Поделился: Хейно

Тема: «Применение модели бинарного дерева в практических проектах»

[TOC]

Прежде всего, я извиняюсь перед всеми за то, что не делюсь контентом в облачных вычислениях. Мой контент основан на исследованиях системы пирамиды одного продукта в недавних аутсорсинговых проектах, и я надеюсь дать вам некоторые преимущества.

Обзор

Пирамида — это название бинарного дерева в индустрии продаж. Могут быть и другие, такие как правильный треугольник или большой треугольник и маленький треугольник, но оно неотделимо от модели бинарного дерева.

Почему пирамида является моделью бинарного дерева

1. Во-первых, каждому узлу пирамиды нужен вышестоящий, а верхний уровень не нужен.

2. Каждый узел пирамиды может и может размещать не более двух подчиненных

3. Внутренние узлы всей пирамиды с увеличением количества слоев показывают порядок 2 в n-й степени.

   Уровень 1 $2^0$

   Уровень 2 $2^1$
   ….
   Слой n $2^{n-1}$

   Недостатки и преимущества бинарных деревьев

4. Преимущества: можно рассчитать каждый узел, количество каждого узла можно рассчитать и быстро позиционировать, даже если каждый уровень не заполнен персоналом.

5. Недостатком является то, что под каждым узлом находится не более 2 подчиненных узлов.

   Вычислительная модель бинарного дерева

   

Модель алгоритма бинарного дерева

1. Метки четырех углов Каждый узел имеет определение Определить четыре угла

左上角表示层级 
右上角表示邀请人 
左下角表示左编号
右下角表示右编号

Общее общее определение определяет только два: левое кодирование и правое кодирование.

1. Спецификация уровня для этого уровня, тогда его номер уровня равен n-1

2. Приглашающий основан на реальной ситуации, то есть А приглашает F, тогда правый верхний угол F помечен как A

3. Левая кодировка и правая кодировка За исключением того, что левая кодировка первого слоя всегда равна 1, при добавлении узла будут добавлены другая левая кодировка и правая кодировка, а правая кодировка и левая кодировка за каждым узлом будут изменены.+2 действие

Пример схемы модели алгоритма бинарного дерева

Полная графика алгоритмов

Алгоритм двоичного дерева Алгоритм кодирования левого и правого узла

1. Алгоритм значения слоя в левом верхнем углу узла — $n-1$, первый слой — $1-1 = 0$ и так далее.

2. Расчет кодировки левого и правого нижних углов, когда есть только один узел А, это означает верхний уровень, левая кодировка равна 1, а правая кодировка равна 2. Если добавляется один человек, он будет помещен в нижний левый узел этого узла по умолчанию, а еще один добавляется как нижний правый узел. Во-первых, при добавлении нижнего левого узла вновь добавленный нижний левый узел представляет собой левый код родителя + 1, поэтому левый код нижнего левого узла A узла B равен 2. В это время B находится внизу, а правый код из B - левый код + 1 = 3. Правое кодирование A - это правое кодирование B + 1 = 4. Когда добавляется нижний правый узел C из A (в это время должен быть нижний левый узел), тогда левое кодирование C является правым кодированием левого узла + 1 = 4, C является нижним, правое кодирование C является его собственным левым кодированием + 1 = 5, правое кодирование A является правым кодированием C + 1... и так далее, мы можем видеть, что каждый раз, когда добавляется узел A, правая кодировка будет Add 2, после добавления узла все значения левой и правой кодировки больше или равны левой кодировке стоимость добавленного узла +2;

3. Вычисление слоя Слой фактически невозможно получить методом 1 в то время, потому что добавляется новый узел, компьютер не получит этот слой. Мы можем вычислять такие слои двумя способами:
   1. Подсчитайте количество узлов между ним и верхним уровнем Это можно увидеть в конкретном алгоритме запада.
   2. Прочитайте слой его родительского узла, затем +1
4. Итак, давайте сначала посмотрим, как рассчитать общее количество узлов и получить информацию о каждом узле.
   Предположим, мы поместили эту информацию в базу данных и определили несколько таких полей.user,puser,layer,left,rightСоответствует текущему человеку, приглашающему, уровню, левой кодировке, правой кодировке соответственно.
   тогда мы можем пройти'select user from table where left >=1 and right <= 12[A对应的right值]Чтобы получить все узлы, конечно, вы также можете пройтиselect * from tableПолучить все узлы, запросив данные, мы можемcount()Получите сразу длину массива, затем получите все узлы и общее количество узлов
   Есть два способа рассчитать количество узлов,
   1. Если мы уже знаем, что левое и правое значения A равны 1 и 12, то мы можем легко использовать 12/2=6, чтобы получить результат данных.
   2. Если мы получим информацию об узле самого низкого уровня, мы можем получить количество всех узлов на $2^{layer+1}-1$.
5. Как рассчитать количество узлов в ветке, информация о каждом узле
   Все еще следуя предположению 4, он рассчитывается в соответствии с информацией полного графа алгоритма бинарного дерева в графическом примере. Как узнать, сколько узлов и информации об узлах имеется в ветвях B и F?
   1. Введение: подсчитайте количество узлов под B с помощью [правого кода B] 5-[левого кода B] 2, а затем вычтите [я] 1 = 1, чтобы получить. Граф в примере имеет только один узел, но он остается таким же, когда узлов больше.Вы можете сами посчитать количество узлов под C.
   2. С приведенным выше введением давайте посмотрим, как получить информацию об узле.select * from table where left>=1 and left <=3 and right >=4 and right<=12Мы можем легко запросить информацию об узле,
   3. Конечно, мы также можем получить количество узлов, вычитая слои, например [слой F] 2-[слой A] 0 +1 = 3, но этот метод не может получить информацию об узле.
6. Как рассчитать общее количество приглашенных для А
   Обычно мы имеем дело с количеством приглашений отдельно в другой таблице, но в текущем допущении 4 мы можем подсчитать количество действительных приглашений.select * from table where puser='A' and left >1 and left <12; Просто получите информацию о приглашающем. (Здесь есть скрытый принцип, который относится к системе распределения, и люди, которых вы приглашаете, могут быть только в узлах ниже вас)
   более простой способselect * from table where puser='A'
7. Для расчета заполненности некоторые системы продаж после использования системы приглашения формулируют специальные правила, например, пирамида пользователей должна быть трехуровневой. То есть он должен охватить $2^0+2^1+2^2+2^3=2^{3+1}-1=15$ человек. Как его рассчитать здесь можно рассчитать по слоям, взяв за пример А,select count(user) as num from table where layer between 0 and 3 and left >=1 and right <=12может быть получен.

Суммировать

Вышеупомянутый контент часто используется в реальной разработке модели бинарного дерева системы продаж.Спасибо, что изучили этот алгоритм со мной.Он ограничен личным уровнем и глубиной исследования.Если есть какие-либо недостатки или ошибки, пожалуйста, исправьте меня и покритикуйте .

---

Hainuo@Cloud Computing высший класс