Binary tree
01. What is a binary tree
Definition: a tree structure in which each node can have at most two child nodes
Features:

Usually subtrees are called “left subtrees” and “right subtrees”

Any tree can be turned into a binary tree
02. Complete binary trees
Definition: The depth of a binary tree is K, except for the KTH layer, the number of nodes of other layers (1 ~ K1) reaches the maximum number, and all nodes of the KTH layer are continuously concentrated on the left.
Features:
 A complete binary tree of depth K has at least 2^(k1) nodes and at most 2^k1 nodes
Full binary tree
Definition: if the depth of a binary tree is K, the tree with 2^(k1) nodes at the k level is full binary.
Features:

All internal nodes have two children, and the leaf nodes are all at the bottom level;

The number of nodes in the k layer is: 2^(k1);

The sum of points is 2 to the k minus 1, and the sum of points must be odd
04. Why define such a special binary tree?
Because a full binary tree can be stored in an array, it doesn’t waste memory space.
If the index of root node A is 0, its left child is (2 * 0 + 1) and its right child is (2 * 0 + 2). Similarly, after 0 is replaced by variable I, the left and right children of each node can be derived. There is no need to define special node classes and use two left and right Pointers to point to the left and right children, which is also a more efficient storage scheme. This extends to a binary heap, which is always a complete binary tree that conforms to the properties of a heap, so its optimal storage solution is an array
const tree = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'];
Copy the code
05. Binary tree traversal
There are four modes of sequential traversal in binary tree: first order traversal (left and right root), middle order traversal (left root and right root), second order traversal (left and right root), and layer traversal.
I. Sequential traversal (root left and right)
Traversal rules:

First access the root

The left subtree is then traversed in order

The right subtree is then traversed in order
Implementation:
const root = { val: 'A', left: { val: 'B', left: { val: 'D', left: { val: 'H', }, right: { val: 'I', }, }, right: { val: 'E', }, }, right: { val: 'C', left: { val: 'F', right: { val: 'J', }, }, right: { val: 'G', }, }, } function preorder(root){ if(! Root){return} console.log(root.val) // Prints the current traversal of the node preorder(root.left) // Traverses the left subtree recursively preorder(root.right) // Traverses the right subtree recursively}Copy the code
Traversal result: ABDHIECFJG
Ii. Middle order traversal (left root right)
Traversal rules:

The left subtree is traversed in middle order

Accessing the root

Then the middle order traverses the right subtree
Implementation:
function midorder(root) { if(! Root) {return} midOrder (root.left) // Recursively traverse the left subtree console.log(root.val) // print the current traverse node midOrder (root.right) // recursively traverse the right subtree}Copy the code
Traversal result: HDIBEAFJCG
Iii. Postorder traversal (left and right roots)
Traversal rules:

Traverses the left subtree sequentially

Then the right subtree is traversed sequentially

Then access the root
Implementation:
function postorder(root) { if(! Root) {return} postorder(root.left) // Recursively traverses the left subtree postorder(root.right) // recursively traverses the right subtree console.log(root.val) // Prints the current traversed node}Copy the code
Traversal result: HDIBEACFJG
Iv. Sequence traversal
Traversal rule: Traversal from top to bottom, left to right.
Implementation:
function levelTraversal(root){ if(! root){ return []; } var queue = [root]; var result = []; while (queue.length! ==0){ var node = queue.shift(); result.push(node.val); if(node.left){ queue.push(node.left); } if(node.right){ queue.push(node.right); } } return result; }Copy the code
Traversal result: ABCDEFGHIJ
Binary search tree (BST)
01. Basic Concepts
Binary Search Tree BST (Binary Search/ Sort Tree), also known as Binary Search Tree, Binary Sort Tree, as the name implies, is a special Tree of Binary Tree, focusing on Search, the feature is to let the nodes in accordance with a certain law of data, so that the Search of a node is particularly efficient
Features:

The value of all nodes in the left subtree is less than or equal to its root

The value of all nodes in the right subtree is greater than or equal to its root
02. Code implementation
1, define,
First we define two classes, a node class and a tree class:
class TreeNode { constructor(val) { this.val = val; this.left = null; // This. Right = null; }} class BST {constructor() {this.root = null; // root}}Copy the code
2, new
When adding nodes, ensure that no matter how many nodes are added, the definition of the binary search tree (that is, the left is smaller than the right is larger) is not damaged.
Steps:

The new node is compared to the root node

If the new node is < the root node, point the root node to the left child of the root node and return to the first step

If the new node > root node, point the root node to the right child of the root node, return to the first step

If the root node does not exist, this is the location of the new node
class BST { ... Add (val) {const _helper = (node, val) => {if (node === null) {return new TreeNode(val); } if (node.val > val) {// If the current node value is larger than val, the new node should be placed in the left subtree of the node. // Return node; Else if (node.val < val) {node.right = _helper(node.right, val); // return node; } } this.root = _helper(this.root, val); // Return a new tree}}Copy the code
3, the query
Steps:

The new node is compared to the root node

If the new node is < the root node, point the root node to the left child of the root node and return to the first step

If the new node > root node, point the root node to the right child of the root node, return to the first step

If the new node === root, found!

If the root node does not exist, no node to be queried exists in the tree
class BST { ... Compare (val) {const _helper = (node, val) => {if (node === null) {return false; } if (node.val === val) {return true; } if (node.val > val) {return _helper(node.left, val); } else {return _helper(node.right, val); return _helper(node.right, val); } } return _helper(this.root, val); }}Copy the code
4, delete,

Leaf node: Delete it directly

Only one side has child node: Let the child node take the place of the deleted node

There are child nodes on both sides:

Find the maximum value replacement in the left subtree of the node to be deleted

Find the smallest value in the right subtree of the node to be deleted
class BST { ... Maxmum (node) {// Return the maximum node in the tree if (node.right === null) {return node; } return this.maxmum(node.right); } removeMax(node) {if (node.right === null) {const leftNode = node.left; node.left = null; return leftNode; } node.right = this.removeMax(node.right); return node; } remove(val) {const _helper = (node, val) => {if (node === null) {return node not found; } if (node.val === val) {// If (node.left === null) {const rightNode = node.right; node.right = null; return rightNode; } else if (node.right === null) {const leftNode = node.left; node.left = null; return leftNode; } else {// If there were children const succeeded = this.maxmum(node.left); Node.left = this.removemax (node.left); // And delete the biggest node in the left subtree. Left = node.left; Succeeded // Let the new node point to the previous left child. Right = node.right; // Let the new node point to the previous right child return antecedent; Else if (node.val > val) {node.left = _helper(node.left, val); return node } else { node.right = _helper(node.right, val); return node; } } this.root = _helper(this.root, val); }}Copy the code
3. The advantages and disadvantages
Advantages: Fast add, delete, and query speed, average time complexity is O(logn)
Disadvantages: Possible linear linked list structure, search time complexity becomes O(n)
Balanced binary tree (AVL)
01. Basic Concepts
Balanced binary tree (AVL) full name balanced binary search tree, is a selfbalanced tree, is upgraded from the above binary search tree.
On the basis of binary search tree, the balance stipulation is added: the height difference between the left subtree and the right subtree should not be more than 1, and the left and right subtrees are a balanced binary tree.
02. How to strike a balance?
By either left rotation or right rotation.
3. The advantages and disadvantages
Advantages: Solve the binary search tree degenerates into an approximate linked list, the worst search time complexity is O(logn).
Faults: because the left child of each node is balanced tree request tree and the height of the right subtree is poor at most equal to 1, this request is too strict, lead to every time to insert/delete nodes, will easily destroy the balance of balanced tree rule, then we need to frequently adjusted by lefthanded and a righthanded, the balance of the once again become a meet the requirements of the tree. Obviously, the performance of the balanced tree is compromised if it needs to be adjusted frequently in a scenario where insertions and deletions are frequent.