This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

1 Binary Tree

A binary tree is one in which each node has at most two children. The leaf node of a binary tree has 0 byte points, and the root or internal node has one or two child nodes.

Storage structure:

Public class TreeNode {// private Object data; // leftChild pointer private TreeNode leftChild; // Private TreeNode rightChild; }Copy the code

1.1 inclined tree

  • Left-oblique tree: all nodes have only a left subtree
  • Right-slant tree: all nodes have only a right subtree

1.2 Full binary tree

All branches of a binary tree have left subtrees and right subtrees, and all leaf nodes exist only at the bottom level.

1.3 Complete binary trees

If the depth of the binary tree is k, the number of layers of the binary tree reaches the maximum number of nodes from 1 to K-1, and all nodes at the k layer are concentrated on the left, which is a complete binary tree. A complete binary tree is derived from a full binary tree. A full binary tree must be a complete binary tree, but a complete binary tree is not necessarily a full binary tree.

2 Binary Search Tree

A binary search tree, also known as a binary search tree, is either an empty tree or a binary tree with the following properties:

  • If the left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root
  • If the right subtree is not empty, then all nodes in the right subtree have a value greater than its root
  • Its left and right subtrees are also binary search trees

The efficiency of summary

  • Access/find: The best time complexityO(logN), the worst time complexityO(N)
  • Insert/Delete: The best time complexityO(logN), the worst time complexityO(N)

3 Balanced Binary Tree (AVL Tree)

Binary search trees can be as efficient as sequential search in the worst case, which is unacceptable. It is also proved that the tree structure has a great impact on the search efficiency of some keywords when the stored data is large enough. Of course, the main reason for this is that BST is not balanced (the height difference between the left and right subtrees is too large). In this case, we need to change the unbalanced tree into a balanced tree through certain algorithms. Thus, the AVL tree was born.

Balanced binary trees are called balanced binary search (sort) trees, or AVL trees. The height is logN. Is essentially a binary search tree, AVL tree properties:

  • It is aA hollow treeorThe height difference between the left and right subtreesThe absolute value of phi does not exceed phi1
  • The left and right subtrees are also a balanced binary tree

In the figure below, the left height of the root node is 3, because there are at most 3 edges on the left; The height on the right is 2, so it’s off by 1. The left side of node 50 to the left of the root node is one edge with a height of 1, and the right side has two edges with a height of 2, separated by 1.

The efficiency of summary

  • Search: Time complexity remains atO(logN)There is no worst-case scenario
  • Insert: The insert operation is required at most1Sub rotation, the time complexity isO(logN)Or so
  • Delete: The deletion is costly and requires a long timeO(2logN)