Trees and code Fano

Содержание и основные понятия

Back to the table of contents
Chapter 13 Page 4 of 6
Trees and code Fano
The twin trees are the mathematical basis for uneven coding, and Fano's condition guarantees absolute decoding.
tree
knot
sheet
Fano
BST
bypass
1. Types of trees
Information technology
tree
- a hierarchical structure of data consisting of:
knots
(upper) connected
ribs
The top knot is called
root
, lower--
leaves
.
Main tree types
Binary tree
- each node has no more than 2 descendants (left and right)
Full binary tree
- all levels fully filled
Binary Search Tree (BST)
- Left descendant < parent, right > parent
AVL wood
== sync, corrected by elderman ==
Huffman Tree
- optimum prefix coding
Coding Tree
- leaves = symbols, ribs = 0/1
Comparison of tree species
Binary
7
3
9
1
5
Total binary
7
3
9
1
5
8
10
BST (search)
7
3
9
1
5
10
Code
B
A
C
D
0
1
0
1
1
Any 2 descendants
All levels complete
Left < root < right
Leaves = symbols, ribs = 0/1
2. Tree Terminology
Basic concepts
Host (node)
- an element of a tree that stores data and links to descendants
root (root)
- the top knot of the tree, has no parent
Leaf
- No offspring.
Parent
- a node with offspring
descendant (child)
- a knot connected to the parent
Brothers (siblings)
- joint parent knots
Support (subtree)
— Part of the tree with the offspring of the knot
Levels and depths
Level (level)
- distance from the root (creature = level 0)
Depth depth
- number of ribs from root to node
Height
- maximum tree depth
Width
- No. of nodes at the level
Binary tree anatomy
Level 0
Level 1
Level 2
Level 3
50
KING
30
parent
70
sheet
20
parent
40
sheet
80
sheet
10
sheet
25
sheet
Left descendant of the root
Right descendant of the root
♪ Brothers (siblings)
♪ Brothers (siblings)
Height = 3
Binary tree properties
Maximum knot level
k
: 2
k
Maximum knots in tree height
h
: 2
h+1
− 1
Minimum height of tree
n
knots:
Number of leaves in complete tree: (n+1)/2
Interactive properties of trees
Max knots at k: 2
k
Highlight the level -- see how many knots there are on it.
Max knots in tree h: 2
h+1
− 1
Set the height - see how many knots the tree holds
Level k:
0
→ 2
0
=
1
Height h:
0
→ 2
1
−1 =
1
3. Where trees are used
File Systems
C:\
Users
Windows
doc.txt
photo.jpg
System32
folder and file hierarchy
Directorates and files are organized into a hierarchical tree. The root is a root folder.
C:\
), leaves are files.
Example:
C:\Users\Documents\file.txt
- from root to leaf.
Databases
[10|20|30]
[5|8]
[35|40]
5,6,7
8,9
20,25
31,33
38,39
41,50
B-wood (wind = 3)
The B-woods and B+-trees index the records by searching for O(log n). Each node is the index page.
Example:
PostgreSQL uses B+woods for indices.
Data compression
A
B
C
D
0
1
0
1
0
1
00
01
10
11
Haffman tree
Haffman's tree encodes the symbols of the variable length: frequent with short codes, rare with long ones.
Example:
ZIP, JPEG, MP3 uses Huffman.
DOM (Document Object Model)
<html>
<head>
<body>
<title>
<div>
<p>
HTML document tree
HTML Document - Tree:
<html>
- root,
<body>
,
<head>
— descendants, text — leaves.
Example:
document.querySelector()
It's going around the DOM tree.
Artificial intelligence
T < 30?
T < 20?
T < 35?
cold
heat
Hot.
Okay, okay.
Yes
None
Decision tree (classification)
Trees of solutions, minimax, alpha-beta cut-off, are algorithms for games and classification.
Example:
The chess engine bypasses the motion tree.
Network protocols
A
B
C
D
E
F
Noose!
ostrich tree (STP)
Spanning Tree Protocol (STP) prevents loops in the Ethernet networks, building a tail tree.
Example:
Switchboards use STP for reservation.
4. Interactive Binary Search Tree (BST)
In BST, the left progeny is always smaller than the parent, the right one is larger. This provides a quick search: O(log n) in a balanced tree.
5. Animation of the round-up of wood
There are three main ways to go around the tree:
In-order (symmetrical)
♪ Left to right
Left support ♪ root ♪ Right support
Application:
Collection of a sorted list from BST
Pre-order (direct)
♪ Top-down contour
The root of the left is supported by the right.
Application:
Copying of wood, Serialization
Post-order (return)
♪ Down the contour ♪
Left support ♪ Right support ~ root
Application:
Wood removal, size calculation
6. Fano condition
Fano's direct condition
No code is the beginning of another code.
Absolute decoding
No lookahead.
Example:
A=0, B=10, C=110 is implemented (prefix code)
Counterfeit:
A=0, B=01 - violated (0 - early 01)
Reverse Fano
No code is the end of another code; it also guarantees certainty when decoded from right to left.
Example:
A=0, B=01, C=11 is executed (suffix code)
🔍
Checking Fano conditions
7. Coding and decoding through wood
📤
Coder: letter ~ bits
📥
Decoder: bits ~ letter
📝
OGE/EGB task bank
Do the task. Choose the answer or enter the number.
08
Mini test
🎯
Check yourself out: 5 questions
0 / 500 XP
0/5