1. Basic concepts of trees

  • A tree can have nodes, roots, parents, children, siblings

  • Empty tree: A tree with no nodes

  • Root node: A tree has only one node, the root node

  • Trees can have left subtrees, right subtrees

  • Degree of nodes: is the number of subtrees

  • Degree of tree: the medium maximum of all nodes

  • Leaf node: node with degree 0

  • Non-leaf node: a node whose degree is not 0

  • Layer tree: The root node is at the first layer, the children of the root node are at the second layer, and so on
  • Depth of nodes: The total number of nodes on a unique path from the root node to the current node
  • Node height: The total number of nodes along the path from the current node to the farthest leaf node
  • Tree depth: the maximum depth of all nodes
  • Tree height: The maximum height of all nodes
  • The depth of the tree is equal to the height of the tree
  1. Ordered tree: A tree in which the children of any node have a sequential relationship
  2. Unordered tree: There is no sequential relationship between the children of any node in the tree

2. Binary tree

2.1. Characteristics of binary trees

  1. Each node has a maximum degree of 2 (a maximum of 2 subtrees)
  2. Left and right subtrees are ordered
  3. Even if a node has only one subtree, distinguish between the left and right subtrees
  4. A binary tree is an ordered tree

2.2. Properties of binary trees

  1. The i-th layer of a nonempty binary tree with at most 2^ (i-1) nodes (I >= 1)
  2. At most 2^ h-1 nodes in a binary tree of height H (h >= 1)
  3. For any non-empty binary tree, if the number of leaf nodes is N0 and the number of nodes with degree 2 is n2, then: n0 = n2 + 1
  4. Assuming that the number of nodes with degree 1 is N1, then the total number of nodes in the binary tree is n = N0 + N1 + n2
  5. The number of edges of the binary tree T = n1 + 2*n2 = n-1 = N0 + N1 + n2-1
  6. So n0 is equal to n2 plus 1

2.3. True binary trees

  • All nodes have a degree of either 0 or 2

2.4. Full binary tree

  1. Full binary tree: The degree of the last node is 0, and the degree of the other nodes is 2
  2. In a binary tree of the same height, a full binary tree has the largest number of leaf nodes and the largest number of total nodes
  3. A full binary tree is always a true binary tree, and a true binary tree is not always a full binary tree

Assume the height of the full binary tree is h(h >= 1)

The number of nodes at layer I is: 2 ^ (i-1)

Number of leaf nodes: 2 ^ (H-1)

Total number of nodes n

N = 2^h – 1 = 2^0 + 2^1 + 2^2 +… + 2^(h – 1)

h = log2(n + 1)

2.5. Complete binary trees

  1. Complete binary tree: Nodes are numbered from top to bottom and from left to right. All their numbers can correspond to numbers in the full binary tree of the same height
  2. The leaf nodes only appear in the last 2 layers, with the last 1 layer of leaf nodes aligned to the left
  3. Complete binary tree A full binary tree from the root node to the penultimate level
  4. A full binary tree is always a complete binary tree, and a complete binary tree is not always a full binary tree

2.5.1. Properties of complete binary trees

  1. Nodes of degree 1 have only left subtrees
  2. Nodes of degree 1 are either 1 or 0
  3. A complete binary tree with the same number of nodes has the smallest height

2.6, binary tree traversal

2.6.1, preorder traversal

Address: leetcode-cn.com/problems/bi…

  • Access order: The root node is visited first, the left subtree is traversed first, and the right subtree is traversed before

    Public void preorderTraversal() {preorderTraversal(root); } private void preorderTraversal(Node node) { if (node == null) return; System.out.println(node.element); preorderTraversal(node.left); preorderTraversal(node.right); }

    // Non-recursive, using a stack implementation

    class Solution { public List preorderTraversal(TreeNode root) { List res = new ArrayList(); preorder(root, res); return res; }

    public void preorder(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}
Copy the code

    }

2.6.2, middle-order traversal

Address: leetcode-cn.com/problems/bi…

  • Access order: traverses the left subtree first, then the root node, and finally the right subtree in middle order

    Public void inorderTraversal() {inorderTraversal(root); } private void inorderTraversal(Node node) { if (node == null) return; inorderTraversal(node.left); // System.out.println(node.element); inorderTraversal(node.right); } class Solution {public List inorderTraversal(TreeNode root) {List res = new ArrayList(); Deque stk = new LinkedList(); while (root ! = null || ! stk.isEmpty()) { while (root ! = null) { stk.push(root); root = root.left; } root = stk.pop(); res.add(root.val); root = root.right; } return res; }}

2.6.3, post-order traversal

Address: leetcode-cn.com/problems/bi…

  • Access order: the left subtree is traversed first, the right subtree is traversed later, and the root node is visited last

    Public void postorderTraversal() {postorderTraversal(root); } private void postorderTraversal(Node node) { if (node == null) return; postorderTraversal(node.left); postorderTraversal(node.right); System.out.println(node.element); } class Solution {public List postorderTraversal(TreeNode root) {List res = new ArrayList(); if (root == null) { return res; }

    Deque<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode prev = null; while (root ! = null || ! stack.isEmpty()) { while (root ! = null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { res.add(root.val); prev = root; root = null; } else { stack.push(root); root = root.right; } } return res; }Copy the code

    }

2.6.4, Sequence traversal

Address: leetcode-cn.com/problems/bi…

  • Each node is accessed from top to bottom and left to right

    public void levelOrderTraversal() { if (root == null) return; Queue<Node<E>> Queue = new LinkedList<>(); Queue.offer (root); // Join queue. // If the queue is not empty, loop while (! Queue. IsEmpty ()) {// add a new Node<E> Node = queue. Poll (); System.out.println(node.element); If (node.left! = null) { queue.offer(node.left); } // If (node.right! = null) { queue.offer(node.right); }}}Copy the code

3. Binary search tree

3.1. Thinking: Search for an integer among the integers of n dynamic arrays to see if it exists?

  1. Suppose we use a dynamic array to store elements, and start the search from the 0th position. The average time complexity is O(n).
  2. If maintaining an ordered dynamic array, using binary search, the worst time complexity is: O(logn)
  3. But the average complexity of adding and removing is order n.
  4. For this requirement, we can use binary search tree optimization

3.2. What is a binary search tree

  1. Binary search tree is a binary tree, a very widely used binary tree, also known as: binary search tree, binary sorting tree
  2. The value of any node is greater than the value of all nodes in its left subtree
  3. The value of any node is less than the value of all nodes in its right subtree
  4. Its left and right subtrees are also binary trees
  5. Binary search tree can greatly improve the efficiency of searching data

3.3 interface design and implementation of binary search tree

3.3.1, Adding a Node

  1. Find the parent node

  2. Creating a new node

  3. Parent. left = node or parent.right = node

Public void add(E element) {elementNotNullCheck(element); If (root == null) {root = new Node<>(element, null); size++; return; } Node<E> parent = root; Node<E> node = root; int cmp = 0; CMP = compare(element, node. Element); parent = node; If (CMP > 0) {node = node.right; } else if (CMP < 0) {// less than 0, put left node = node.left; } else {// equal node.element = element; return; } } while (node ! = null); Node<E> newNode = newNode <>(element, parent); If (CMP > 0) {// if (CMP > 0) {parent.right = newNode; } else {// Put the left node in the parent node parent.left = newNode; } size++; }Copy the code

3.3.2. Delete a node

  1. Delete leaf node:

node == node.parent.left , node.parent.left = null

node == node.parent.right , node.parent.right = null

node.parent == null , root = null

  1. Delete the node whose degree is 1

  • Replace the position of the original node with a child node

Child is node. Left or child is node. Right

Replace node position with child

  • If node is the left child

child.parent = node.parent

node.parent.left = child

  • If node is the right child node

child.parent = node.parent

node.parent.right = child

  • If it’s the root node

root = child

child.parent = null

3. Delete the node whose degree is 2

The value of the original node is overwritten by the value of the precursor or successor node

Then, delete the corresponding precursor or successor node

Private void remove(Node<E> Node) {if (Node == null) return; size--; If (node.hastwochildren ()) {// Find the node <E> s = succeeded (node); Node. element = s.lement; // Delete the successor node node = s; } // Delete node (the degree of node must be 1 or 0) node <E> replacement = node.left! = null ? node.left : node.right; if (replacement ! = null) {// node is a node with degree 1 // change parent replacement. If (node.parent == null) {// Node is a node with degree 1 and is the root node. Root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; }} else if (node.parent == null) {// node is a leaf node and a root node root = null; } else {if (node == node.parent. Left) {node.parent. Left = null; } else { // node == node.parent.right node.parent.right = null; }}}Copy the code

4. Balanced binary search tree

  1. Balancing a binary tree is essentially balancing the heights of the left and right subtrees of an ordinary binary tree
  2. When the number of nodes is fixed, the closer the height of the left and right subtrees are, the more balanced the binary tree will be
  3. Ideal balance: Like complete and full binary trees, the height is minimal

4.1. How to improve binary search tree?

  1. First, the order in which nodes are added and removed is unrestricted and can be considered random
  2. So after the node add, delete operation, try to make binary search tree restore balance
  3. If you continue to adjust the position of nodes, you can achieve the ideal balance, but the cost may be relatively large
  4. A more reasonable improvement plan is to achieve moderate balance with as few adjustment times as possible
  5. A moderately balanced binary tree can be called a balanced binary search tree
  6. The classic and common balanced binary search trees are: AVL tree, red black tree