Welcome once again to another chance to practice your programming skills.
Today we're going to take a look at a problem that's important for physical devices
like yearbooks in a school or phone books or really any sorted index.
The problem we're going to cover this time is how to organize
and search through sorted information.
The approach I want to take is to use a tree.
We've seen trees before in some computer science programming.
The particular kind of tree I'm going to focus on
is one that has 2 branches at every level.
Suppose I have a number of friends that I want to keep track of in my yearbook
or in a telephone book.
I could use a Python list to include all 4 of their names or all 4 of those elements.
And I can check to see if an element is in a list in Python just by using the keyword "in"--
putting the element on the left and the list on the right.
But we might wonder, "What is Python doing behind the scenes?"
"How is this implemented in practice?"
One way to do it--and the way we'll explore today--
is to build up a special kind of tree holding all of the information that I want to see.
I'm going to start with the first element of my list
and make it the root or the top of the tree.
Let me sketch out the rest so the tree is easier to see.
I've added the elements from my list--1, 2, 3 and 4--to this tree,
and I've put them in a special order corresponding to how they'd fall
in English alphabetical order.
So since the J in Jacob comes before the M in Margaret,
I've made Jacob the left child in Margaret.
Since the N in Nelson comes after the M in Margaret--j, k, l, m, n, o, p;
yes, I can remember the English alphabet--I've made it the right child.
And the A in Alice follows all the way down here to the left.
I'm going to construct a special tree to store information like this
that has a number of properties.
The first 2 just summarize or formalize this ordering intuition we had above.
Everything to the left of Margaret and all the way down
is less than or equal to--comes before in the alphabet,
is a smaller number than if I'm storing phone numbers instead--
the information stored at Margaret's node.
Jacob and Alice both come before Margaret in the alphabet, so they're both on the left.
And similarly, right subtrees contain only information that's greater than or equal to--
larger, later in the alphabet.
Nelson comes after Margaret, so it's here on the right.
And then finally--and this is really important--
both the left and the right subtrees also follow rules I, II, and III.
It is turtles all the way down.
That makes this tree something special in computer science:
a recursive data structure.
We've already seen recursive functions that are defined in terms of themselves.
Now I'm talking about a recursive way to lay out data that's defined in terms of itself.
ようこそ ここではプログラミングスキルを さらに磨いていきましょう
今回詳しく見ていく問題は
名簿や電話帳など整列された索引を持つ 物理デバイスにとって重要なものです
整列された情報をどのように編成し
検索するか考えてみましょう
問題を解くのに木を使います
木は以前にもプログラミングで見たことがあります
今回用いる木は
各段階に2本の枝があるものです
名簿や電話帳に連絡を取りたい友達が
4人いるとしましょう
Pythonではリストを使って 4人の名前つまり4つの要素を表せます
そしてinというキーワードを使って 要素を左にリストを右に書くと
そのリストに要素が含まれるか 調べることができます
しかしPythonは裏側で何をして
どう実装されているのか疑問です
今回見ていく方法は
特別な木を作って 全ての情報を保持しておくというものです
リストの最初の要素から始め
木の根を一番上とします
分かりやすいように残りを描いてみます
リストから1、2、3、4と要素を取り出し 木に加えました
この時アルファベット順に応じて
特別な順序で加えていきます
JacobのJはMargaretのMより前に来ますから
JacobはMargaretの左の子にします
NelsonのNはMargaretのMよりあとに来ます j、k、l、m、n、o、pなので
正しいですね Nelsonを右の子にします
AliceのAはずっと左へ下がります
このように複数の要素を情報として保持する木を
作っていきます
最初の2つは今の直観的な説明を 規則としてまとめたものです
まずMargaretの左の子はすべてアルファベット順で
Margaretのノードに保持された情報と
同じか前に来るものです
電話番号を整理するなら小さい番号になります
JacobとAliceはアルファベット順で Margaretより前なので左です
次に右の部分木にはアルファベット順で
同じか大きい情報しか来ません
NelsonはMargaretよりあとなので右に来ます
そして最後に重要な点ですが
左右の部分木は両方とも このI、II、IIIの規則に従います
同様にどんどん下につながっていきます
これによって木は専門用語でいう
再帰的データ構造となります
既に自身を用いて 定義された再帰関数について学びました
これから自身と同じ規則を使ってデータ構造を 定めた再帰的データ構造について話します
Bem vindo, masi uma vez, a outra chance de praticar suas habilidades de programação.
Hoje vamos dar uma olhada em um problema que é importante para dispositivos físicos,
como calendários de uma escola, ou catálogos de telefone, ou qualquer índice ordenado.
O problema de que vamos tratar é como organizar
e fazer busca em informação ordenada.
A abordagem que eu quero adotar é usar uma árvore.
Já vimos árvores antes, em algu outro curso de programação.
O tipo de árvore em que eu vou focar é
uma que tem dois ramos em cada nível.
Suponha que eu tenho um certo número de amigos, que eu quero guardar em meu calendário,
ou em meu caderno de telefones.
Eu poderia usar uma lista, em Pyton, para incluir esses 4 nomes, ou todos esses 4 elementos
E eu poderia verificar se um elemento está na lista, em Python, usando a palavra chave in --
colocando o elemento à esquerda e à lista à direta.
Mas, podemos nos perguntar: "O que Python esta'fazendo por trás disso?"
"Como isso é implementado, na prática?"
Uma maneira de fazer isso -- e a maneira que vamos explorar hoje --
é construir um tipo especial de árvore para armazenar toda a informação que eu quero ver.
Vou começar com o primeiro elemento da minha lista,
e fazê-lo a raiza, ou o topo, da árvore.
Deixe-me desenhar o resto,para que seja mais fácil ver a árvore.
Eu adicionei os elementos da minha lista -- 1, 2, 3, 4 -- a esta árvore,
e os coloquei em uma ordem especial, correspondendo a como eles ocorreriam,
em ordem alfabética.
Então, como o J, de Jacob, vem antes de M, de Margaret,
eu coloque Jacob como filha à esquerda de Margaret.
Como N, de Nelson, vem antes de M, de Margaret, -- j,k,l,m,n,o,p,
sim! eu me lembor do alfabeto inglês! -- eu o coloquei como filha à direita.
E o A, de alice, segue todo o caminho para a esquerda.
Vou construir uma árvore especial para armazenar informação, como esta,
que tem várias propriedades.
As 2 primeiras resumem, ou formalizam, essa intuição de ordem que vimos acima:
tudo o que está à esquerda de Margaret, em todo o caminho para baixo,
é menor ou igual -- vem antes no alfabeto,
ou é um número menor, se eu estiver armazenando números --
do que a informação armazenada no nodo de Margaret.
Jacob e Alice vêm, ambos, antes de Margaret, no alfabeto -- portanto estão ambos à esquerda.
De modo análogo, subárvores à direita contêm apenas informação maior ou igual --
maior, mais à frente no alfabeto.
Nelson vem depois de Margartet -- portanto está aqui, à direita.
Finalmente -- isso é realmente importante --
ambas as subárvores, à direita e à esquerda, seguem as regras I, II e III.
Isso funciona ao longo de todo o caminho.
Isso faz dessa 'rvore algo espevcial em ciência da computação:
é uma estrutura de dados recursiva.
Já vimos funções recursivas, que são definidas em termos de si próprias.
Agora estou falando de uma maneira recursiva de posicionar dados, que é definida em termos dela própria.