Проверка сбалансированности бинарного дерева

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

Здравствуйте! Задача из контеста для обучению си. Как ясно из названия, нужно проверить сбалансированность дерева, а именно на вход поступает некоторая последовательность натуральных чисел и завершается последовательность нулем. Нужно построить из чисел дерево, если число уже добавлено, то добавлять его не надо. Дерево называется сбалансированным, если для каждой вершины, высота правого и левого поддерева отличаются не больше чем на один. Я вроде как написал программу, делающую проверку, но на контесте 3 из 9 теста превышают допустимое время выполнения, остальные работают верно. Прошу вас дать наводки связи с чем это может быть связано и где искать ошибки в моем коде?
Я сначала объясню, как работает код в моем представлении, а потом отправлю сам код.
Реализуется структура данных struct Node. Реализуются базовые функции добавления числа в дерево, и удаления дерева. Также реализуются две функции: одна из них определяет высоту узла, другая определяет длину минимального пути от узла до конца дерева. Потом идет функция проверки узла, которая возвращает ноль, если разница между высотой и минимальным путем больше 1, и возвращает единицу в обратном случае. Также она может вернуть -1 если дерево пустое. Следующая функция финальная, она является произведением(искусства(нет)) проверок каждого узла, и если хотя бы в одном будет ноль, то соответственно все произведение будет 0. И в функции main() я написал что если это проверка равно 0, то печатать «NO», а если не 0, то печатать «YES». Код работает для 6 тестов из 9, в остальных 3 превышает максимальное время выполнения. Заранее благодарен за любую помощь, а также неплохо было бы услышать мнения, как можно было бы оптимизировать код, и как лучше было бы реализовать.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137

#include #include typedef int Data; struct Node { Data val; // данные в узле struct Node * left; // левый ребенок struct Node * right; // правый ребенок }; void tree_destroy(struct Node * tree); void insert(struct Node **p, Data x); void insert(struct Node **p, Data x) { if (*p == NULL) { *p = (struct Node*)malloc(sizeof(struct Node)); (*p)->val = x; (*p)->left = NULL; (*p)->right = NULL; } else { if (x > (*p)->val) { insert(&((*p)->right), x); } if (x  (*p)->val) insert(&((*p)->left), x); } } void tree_destroy(struct Node * tree) { if (tree == NULL) { return; } else { tree_destroy(tree->left); tree_destroy(tree->right); free(tree); } } int max(int a, int b) { int c = a; if (a > b) c = a; if (b > a) c = b; if (a == b) c = a; return c; } int min(int a, int b) { int c = a; if (a  b) c = a; if (b  a) c = b; if (a == b) c = a; return c; } int height(struct Node *tree) { int i = 0; if (tree == NULL) return 0; if (tree != NULL) { i = max(height(tree->left), height(tree->right)) + 1; } return i; } int minheight(struct Node *tree) { int i = 0; if (tree == NULL) return 0; if (tree != NULL) { i = min(height(tree->left), height(tree->right)) + 1; } return i; } int check_node(struct Node *tree) { int c = -1; if (tree != NULL) { if (height(tree) - minheight(tree) > 1) { c = 0; } else { c = 1; } } return c; } int check(struct Node *tree) { int t = 1; if (height(tree) == 3) { t = check_node(tree); } if (height(tree) > 3) t = check(tree->left)*check(tree->right); return t; } int main() { int i = 0, a; struct Node *root = NULL; int p; scanf("%d", &p); insert(&root, p); while (p != 0) { scanf("%d", &p); if (p>0) insert(&root, p); } if (check(root) == 0) { printf("NO"); } else { printf("YES"); } tree_destroy(root); return 0; }

Источник

Сбалансированное бинарное дерево в Python

В этой статье мы будем изучать сбалансированные бинарные деревья, и мы постараемся реализовать программу в Python, чтобы определить, сбалансирован ли двоичное дерево или нет. Чтобы прочитать эту статью, вы должны быть знакомы с концепцией бинарных деревьев.

Что такое сбалансированное бинарное дерево?

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

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

Как проверить, является ли бинарное дерево сбалансировано или нет?

Согласно определению высота левого поддерева и правого поддерева не должна превышать одного на любом узле.

Поэтому, если мы рассмотрим дерево, которое будет сбалансировано на любом узле, нам придется найти высоту его левого подделка и правого подмаревки.

Тогда мы проверим разницу в высотах. Если разница выйдет больше 1 на любом узле, мы объявим, что дерево не сбалансировано. Ниже приведен алгоритм для этой процедуры:

Algorithm CheckBalancedBinaryTree: Input: Root Node of the binary tree. Output:True if binary tree is balanced and False otherwise. Start. 0.If tree is empty, return True. 1. Check the height of left sub-tree. 2.Check the height of right sub-tree. 3.If difference in height is greater than 1 return False. 4.Check if left sub-tree is balanced. 5.Check if right sub-tree is balanced. 6. If left sub-tree is balanced and right sub-tree is also balanced, return True. End

Мы выяснили алгоритм для проверки, если бинарное дерево сбалансировано, но мы не знаем, как рассчитать высоту дерева и подделки. Таким образом, мы сначала реализуем программу, чтобы найти высоту дерева, если узел корневого узла, а затем мы реализуем вышеуказанный алгоритм.

Как найти высоту сбалансированного бинарного дерева?

Чтобы найти высоту бинарного дерева, мы можем просто помнить следующие пункты.

• Если корень пуст, то высота дерева будет 0.
• Если root не пустой, то высота дерева будет равна максимальной высоте левого подделка корневого и правого подделка корня, добавленного 1.

Имея в виду вышеуказанные точки, алгоритм нахождения высоты дерева:

• Высота алгоритма (дерево):
• Вход: root дерева
• Выход: высота дерева
• Начинать.
• 1. Если корень нет, возврат 0.
• 2.Нажмите высоту левого подделки .//Height(root.leftChild)
• 3.Вы высота правого поддерева .//Height(root.rightChild)
• 4.Видите максимальное значение в 2 и 3 и добавьте 1 к нему.
• Конец

Теперь мы реализуем вышеуказанный алгоритм и выполните его для следующего бинарного дерева.

Программа найти высоту бинарного дерева

Ниже приведен код для поиска высоты бинарного дерева.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValuehright: return hleft+1 else: return hright+1 root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing the height of the binary tree.") print(height(root)) 

Output: Printing the height of the binary tree. 3

Теперь мы знаем, как найти высоту бинарного дерева. Таким образом, мы теперь будем реализовать алгоритм, чтобы проверить, является ли двоичное дерево сбалансировано или не для указанного выше двоичного дерева.

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

Следующая программа была реализована для проверки, если бинарное дерево сбалансировано или нет.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValuehright: return hleft+1 else: return hright+1 def CheckBalancedBinaryTree(root): #if tree is empty,return True if root==None: return True #check height of left subtree lheight= height(root.leftChild) rheight = height(root.rightChild) #if difference in height is greater than 1, return False if(abs(lheight-rheight)>1): return False #check if left subtree is balanced lcheck=CheckBalancedBinaryTree(root.leftChild) #check if right subtree is balanced rcheck=CheckBalancedBinaryTree(root.rightChild) #if both subtree are balanced, return True if lcheck==True and rcheck==True: return True root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing True if binary tree is balanced:") print(CheckBalancedBinaryTree(root)) 

Output: Printing True if binary tree is balanced: True

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

Заключение

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

Читайте ещё по теме:

Источник

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

Всем привет, дана такая задача: нужно реализовать класс Бинарного дерева поиска и проверить его на сбалансированность. Как известно дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1. У меня уже есть работающий код, но он относительно медленный. Нужно его оптимизировать. Можете помочь с этим, уже который день не могу решить эту задачу как подобает

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include #include using namespace std; struct node { int info; node* l, * r; }; void push(int a, node** t) { if ((*t) == NULL) { (*t) = new node; (*t)->info = a; (*t)->l = (*t)->r = NULL; return; } if (a > (*t)->info) push(a, &(*t)->r); else push(a, &(*t)->l); } int max(int x, int y) { return (x >= y) ? x : y; } int height(node* node) { if (node == NULL) return 0; return 1 + max(height(node->l), height(node->r)); } int AVL(node* root) { if (root == NULL) return 1; int lh = height(root->l); int rh = height(root->r); if (abs(lh - rh)  1 && AVL(root->l) && AVL(root->r)) return 1; return 0; } int main() { node* tree = NULL; vector int> v; int tmp = 1; while (tmp) { cin >> tmp; if (tmp) push(tmp, &tree); } if (AVL(tree)) cout  <"YES"; else cout  <"NO"; return 0; }

Input: 7 3 2 1 9 5 4 6 8 0
Output: YES

Input: 5 1 4 2 7 6 8 0
Output: NO

Источник