• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Binary sort tree

define

Left subtree node < root node value < right subtree node. For middle order traversal of binary sorting tree, an increasing sequence can be obtained, as shown in the following figure :1, 2, 3, 4, 6, 8Copy the code

Delete binary sort tree

2) If z has only one left or right subtree, let the subtree of Z replace the position of Z (replaced by children) 3) If Z has left and right subtrees, find the first child to fill itCopy the code

Figure 2

Figure 3

Average search efficiency of binary sort tree 

The search efficiency of the figure above is ASL=(1+2*2+3*4+4*3)/10=2.9, that is, the total number of nodes in each layer multiplied by the number of layers is averagedCopy the code

Balanced binary trees

The absolute value of the height difference between the left and right subtrees of any node is no more than 1, such a binary tree is called 'balanced binary tree '; The height difference between the left and right subtrees is called the node's 'balance factor'.Copy the code
  • –> Balance as follows

  • –> Imbalances are as follows

Balanced binary tree insertion

The following figure shows RR right single rotation

Below is LL left single rotation

The following figure shows LR rotated left and then right

The following figure shows RL rotated right and then left

Huffman tree

Nodes in a tree are often assigned a value of some meaning called ‘weight ‘; The sum of the weighted path lengths of all leaf nodes in the tree is called the tree’s ‘weighted path length –>WPL’

The following figure shows the weighted path calculation

  • (a) WPL = 7 x 2 + 5 * 2 + 2 * 2 + 4 x 2 = 36
  • (b) WPL = 7 * 3 + 5 * 3 + 4 * 2 + 1 * 2 = 46
  • (c) WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35

The construction of Huffman tree

  • Choose a binary tree with the lowest weight of two nodes in the forest
  • Merge two binary trees and add a new node as the ‘root of the new binary tree’ with the weight ‘sum of the weights of the left and right children’

Huffman coding

If none of the codes is a ‘prefix’ of the other, such codes are called ‘prefix codes’