Preuve qu'un arbre de recherche binaire construit aléatoirement a une hauteur logarithmique

Comment prouvez-vous que la hauteur attendue d'un arbre de recherche binaire construit de façon aléatoire avec nœuds est ? Il y a une preuve dans CLRS Introduction to Algorithms (chapitre 12.4), mais je ne la comprends pas.O ( log n $n$$O(\log n)$

Réfléchissons d'abord intuitivement à cela. Dans le meilleur des cas, l'arbre est parfaitement équilibré; dans le pire des cas, l'arbre est entièrement déséquilibré:

À partir du nœud racine , cet arbre de gauche a deux fois plus de nœuds à chaque profondeur successive, de sorte que l'arbre a n = ∑ h i = 0 2 i = 2 h + 1 - 1 nœuds et une hauteur h (qui est en ce cas 3). Avec un peu de maths, n ≤ 2 h + 1 - 1 → h ≤ ⌈ log 2 ( n + 1 ) - 1 ⌉ ≤ ⌊ l $p$$n=\sum_{i=0}^{h}2^i =2^{h+1}-1$$h$ , c'est-à-dire qu'il a unehauteur O ( log n ) . Pour l'arbre entièrement déséquilibré, la hauteur de l'arbre est simplement n - 1 → O ( n ) . Nous avons donc nos limites.$n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$$O(\log n)$$n-1\rightarrow O(n)$

Si nous construisions un arbre équilibré à partir d'une liste ordonnée , nous choisirions l'élément central comme nœud racine. Si nous construisons au hasard un arbre, l'un des n nœuds est également susceptible d'être choisi et la hauteur de notre arbre est: h e i g h t t r e e = 1 + max ( h e i g h t l e f t s u b t r $\{ 1,2,\dots,n\}$$n$ Nous savons que dans un arbre de recherche binaire, le sous-arbre gauche ne doit contenir que des clés inférieures au nœud racine. Ainsi, si nous choisissons au hasard l'élément i t h , le sous-arbre gauche ai-1éléments et le sous-arbre droit an-iéléments, donc de manière plus compacte: h n =1+max( h i

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$$n-i$. À partir de là, il est logique que si chaque élément est également susceptible d'être sélectionné, la valeur attendue n'est que la moyenne de tous les cas (plutôt qu'une moyenne pondérée). D'où:E[ h n ]=$h_n=1+\max (h_{i-1},h_{n-i})$$\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

Comme je suis sûr que vous l'avez remarqué, j'ai légèrement dévié de la façon dont CLRS le prouve, car CLRS utilise deux techniques de preuve relativement courantes qui sont déconcertantes pour les non-initiés. La première consiste à utiliser des exposants (ou logarithmes) de ce que nous voulons trouver (dans ce cas, la hauteur), ce qui rend les mathématiques un peu plus propres; la seconde consiste à utiliser des fonctions d'indicateur (que je vais juste ignorer ici). Le CLRS définit la hauteur exponentielle comme , donc la récurrence analogue est Y n = 2 × max ( Y i - 1 , Y n - i$Y_n=2^{h_n}$$Y_n=2\times\max (Y_{i-1},Y_{n-i})$.

En supposant l'indépendance (que chaque tirage d'un élément (parmi les éléments disponibles) pour être la racine d'un sous-arbre soit indépendamment de tous les tirages précédents), nous avons toujours la relation: pour lequel j'ai fait deux étapes: (1) déplacer le

$$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$ extérieur parce que c'est une constante et l'une des propriétés des sommations est que∑ici=c∑ii, et (2) déplacer les 2 à l'extérieur car c'est aussi une constante et l'une des propriétés des valeurs attendues estE[ax]=aE[x]. Maintenant, nous allons remplacer lafonctionmaxpar quelque chose de plus grand car sinon la simplification est difficile. Si nous argumentons pourXnon négatif,Y:E[max(X,$\frac{1}{n}$$\sum_i ci=c\sum_i i$$\operatorname{E}[ax]=a\operatorname{E}[x]$$\max$$X$$Y$ , puis: E [ Y n ] ≤ $\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$ telle sorte que la dernière étape découle de l'observation que pouri=1,Yi-1=Y0etYn-i=Yn-1et va tout le chemin versi=n,Yi-1=Yn-1etYn $$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$ $i=1$$Y_{i-1}=Y_{0}$$Y_{n-i}=Y_{n-1}$$i=n$$Y_{i-1}=Y_{n-1}$ , donc chaque terme Y 0 à Y n - 1 apparaît deux fois, nous pouvons donc remplacer la somme totale par une somme analogue. La bonne nouvelle est que nous avons une récurrenceE[ Y n ]≤$Y_{n-i}=Y_{0}$$Y_0$$Y_{n-1}$; la mauvaise nouvelle, c'est que nous ne sommes pas beaucoup plus loin que là où nous avons commencé.$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

À ce stade, CLRS tire une preuve d'induction $\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$$\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$$n^3$$Y_n=2^{h_n}$$h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$$n^k$$k$

$$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n)$$