Деревья. Лекция №5

1.

Кафедра
статистики и
кибернетики
Department of statistics and
cybernetics
Лекция №5
«Деревья»
Лектор: Вадим Владимирович Демичев
доцент, кандидат экономических наук
Москва, 14.12.2022

2.

Деревья
ДЕМИЧЕВ В.В.
2

3.

Древо семьи
ДЕМИЧЕВ В.В.
3

4.

Дерево принятия решений
ДЕМИЧЕВ В.В.
4

5.

Дерево принятия решений
ДЕМИЧЕВ В.В.
5

6.

Бинарное дерево
ДЕМИЧЕВ В.В.
6

7.

Обязательные свойства бинарного дерева
ДЕМИЧЕВ В.В.
7

8.

Соблюдение свойств
ДЕМИЧЕВ В.В.
8

9.

Узел дерева
ДЕМИЧЕВ В.В.
9

10.

Обозначения
ДЕМИЧЕВ В.В
.
10

11.

Способы обхода дерева
ДЕМИЧЕВ В.В.
11

12.

Способы обхода дерева
ДЕМИЧЕВ В.В.
12

13.

Вставка новых узлов в дерево
ДЕМИЧЕВ В.В.
13

14.

Удаление узлов из дерева
ДЕМИЧЕВ В.В.
14

15.

Удаление узлов из дерева (Ситуация 1)
ДЕМИЧЕВ В.В.
15

16.

Удаление узлов из дерева (Ситуация 2)
ДЕМИЧЕВ В.В.
16

17.

Удаление узлов из дерева (Ситуация 3)
ДЕМИЧЕВ В.В.
17

18.

Удаление узлов из дерева (Ситуация 3)
ДЕМИЧЕВ В.В.
18

19.

Пример
ДЕМИЧЕВ В.В.
19

20.

Пример
ДЕМИЧЕВ В.В.
20

21.

Пример
ДЕМИЧЕВ В.В.
21

22.

Пример
ДЕМИЧЕВ В.В.
22

23.

Пример
ДЕМИЧЕВ В.В.
23

24.

Пример
ДЕМИЧЕВ В.В.
24

25.

Пример
ДЕМИЧЕВ В.В.
25

26.

Пример
ДЕМИЧЕВ В.В.
26

27.

Сортировка деревом
ДЕМИЧЕВ В.В.
27

28.

Одинаковые узлы – разная высота
ДЕМИЧЕВ В.В.
28

29.

Пример
ДЕМИЧЕВ В.В.
29

30.

Пример
ДЕМИЧЕВ В.В.
30

31.

Одинаковые узлы – разная высота
ДЕМИЧЕВ В.В.
31

32.

Пример
ДЕМИЧЕВ В.В.
32

33.

АВЛ деревья
ДЕМИЧЕВ В.В.
33

34.

Узлы
ДЕМИЧЕВ В.В.
34

35.

Высота
35

36.

Вычислить высоту
ДЕМИЧЕВ В.В.
36

37.

АВЛ дерево?
ДЕМИЧЕВ В.В.
37

38.

АВЛ дерево?
ДЕМИЧЕВ В.В.
38

39.

АВЛ дерево?
ДЕМИЧЕВ В.В.
39

40.

Левый поворот
ДЕМИЧЕВ В.В.
40

41.

Правый поворот
ДЕМИЧЕВ В.В.
41

42.

Двойное левое вращение
ДЕМИЧЕВ В.В.
42

43.

Двойное правое вращение
ДЕМИЧЕВ В.В.
43

44.

Пример добавления узлов (Добавление 4 – 5 – 7)
ДЕМИЧЕВ В.В.
44

45.

После левого поворота
ДЕМИЧЕВ В.В.
45

46.

Добавление 2
ДЕМИЧЕВ В.В.
46

47.

Балансировка?
ДЕМИЧЕВ В.В.
47

48.

Добавляем 1
ДЕМИЧЕВ В.В.
48

49.

Балансировка?
ДЕМИЧЕВ В.В.
49

50.

После правого поворота
ДЕМИЧЕВ В.В.
50

51.

Добавляем 3
ДЕМИЧЕВ В.В.
51

52.

Балансировка?
ДЕМИЧЕВ В.В.
52

53.

После двойного правого поворота
ДЕМИЧЕВ В.В.
53

54.

Добавляем 6
ДЕМИЧЕВ В.В.
54

55.

Балансировка?
ДЕМИЧЕВ В.В.
55

56.

Результат
ДЕМИЧЕВ В.В.
56

57.

Пример удаления узлов
ДЕМИЧЕВ В.В.
57

58.

Удаляем 4
ДЕМИЧЕВ В.В.
58

59.

Сбалансировано?
ДЕМИЧЕВ В.В.
59

60.

Результат правого поворота
ДЕМИЧЕВ В.В.
60

61.

Удаляем 8
ДЕМИЧЕВ В.В.
61

62.

Сбалансировано?
ДЕМИЧЕВ В.В.
62

63.

Удаляем 6
ДЕМИЧЕВ В.В.
63

64.

Сбалансировано?
ДЕМИЧЕВ В.В.
64

65.

После левого поворота
ДЕМИЧЕВ В.В.
65

66.

Удаляем 5
ДЕМИЧЕВ В.В.
66

67.

Сбалансировано?
ДЕМИЧЕВ В.В.
67

68.

Удаляем 2
ДЕМИЧЕВ В.В.
68

69.

Сбалансировано?
ДЕМИЧЕВ В.В.
69

70.

После двойного левого поворота
ДЕМИЧЕВ В.В.
70

71.

Удаляем 1
ДЕМИЧЕВ В.В.
71

72.

Сбалансировано?
ДЕМИЧЕВ В.В.
72

73.

Удаляем 7
ДЕМИЧЕВ В.В.
73

74.

Сбалансировано?
ДЕМИЧЕВ В.В.
74

75.

После левого поворота
ДЕМИЧЕВ В.В.
75

76.

Вопросы
ДЕМИЧЕВ В.В.
76