Trees versus other data structures

Array:

  • Advantages: The main advantage of arrays is that they can be accessed efficiently by subscript values.
  • Disadvantages: Arrays require a lot of displacement when inserting and deleting data (when inserting to the first or middle position), which is inefficient.

List:

  • Advantages: The insertion and deletion operation of linked list is very efficient.
  • Disadvantages: Inefficient lookups require you to start from scratch by accessing each data item in the linked list until you find it.

And even though insert and delete operations are efficient, if you want to insert and delete data in the middle, you still need to find the corresponding data all over again.

Hash table:

  • Advantages: Hash table insert/query/delete efficiency is very high
  • Disadvantages: low space utilization, array is used at the bottom, elements in the hash table are unordered, cannot traverse the elements in the hash table in a fixed order, cannot quickly find the maximum or minimum values in the hash table such special values.

Tree structure:

  • The tree structure also combines the advantages of the above data structure (of course, the advantages are not superior to other data structures, such as the efficiency of hash tables in general), and also makes up for the disadvantages of the above data structure. For example, high space utilization, high search efficiency, easy to delete and add, can quickly find the maximum and minimum value, etc..

The understanding of the tree

The term

  • Degree: the number of subtrees of nodes.
  • Degree of tree: The maximum degree of any node in the tree.
  • Leaf: node of degree 0 (also called Leaf node).
  • Parent: A node with a child tree is the Parent of the root of its child tree
  • Child: if A is the parent of B, B is called the Child of A. Children are also called children.
  • Siblings: Nodes that have the same parent are siblings to each other.
  • Path and path length: the path from node N1 to nk is a sequence of nodes n1, n2… Nk, ni is the parent of Ni plus one. The number of edges contained in a path is the length of the path.
  • The number of layers of any other node is the number of layers of its parent node plus 1.
  • Tree Depth: The maximum level of any node in a tree is the Depth of the tree.

Binary tree

All trees can essentially be modeled using binary trees

  • The definition of binary tree
    • Binary trees can be empty, that is, they have no nodes.
    • If not empty, it consists of the root node and two disjoint binary trees called its left subtree TL and its right subtree TR.
  • Properties of binary trees
    • The maximum number of nodes at the i-layer of a binary tree is: 2^(i-1), I >= 1;
    • The maximum number of nodes in a binary tree with depth of K is: 2^ k-1, k >= 1;
    • For any non-empty binary tree T, if n0 represents the number of leaf nodes and n2 is the number of non-leaf nodes with degree 2, then the relation n0 = n2 + 1 is satisfied.

Special binary tree

  • Perfect binary tree: A full binary tree is one in which each node has 2 children except the lowest leaf node.
  • Complete binary tree: the number of nodes reaches the maximum except for the last layer of the binary tree. And the last layer of leaves from left to right continuously exist, only a few nodes on the right are missing.

Storage of binary trees

Common ways are arrays and linked lists

  • An array of
    • Complete binary tree: top down, left to right
    • Incomplete binary tree: to complete the binary tree can be stored according to the above scheme, but will cause a large space waste
  • Using linked lists (the most common form of binary trees)
    • Each node is encapsulated into a node containing stored data, a reference to the left node, and a reference to the right node

Binary search tree

define

  • Binary search tree is a binary tree, can be empty; If it is not empty, it satisfies the following properties:
    • All keys of a non-empty left subtree are less than their root key.
    • All keys of a non-null right subtree are greater than those of its root.
    • The left and right subtrees themselves are binary search trees.

features

  • Binary search trees are characterized by the fact that relatively small values are always stored on the left node and relatively large values are always stored on the right node.

Binary search tree encapsulation

The implementation of insert, search, order traversal, order traversal, order traversal, return the maximum value, delete nodes and other operations.

class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(key) {let newNode = newNode (key); // Check whether the root node is null if (this.root == null) {this.root = newNode; } else { this.insertNode(this.root, newNode); } } insertNode(node, If (newNode.key > node.key) {if (node.right == null) {node.right = newNode; } else { this.insertNode(node.right, newNode); } } else { if (node.left == null) { node.left = newNode; } else { this.insertNode(node.left, newNode); }}} / / sequence traversal first preOrderTraversal () {enclosing preOrderTraversalNode (enclosing root); } preOrderTraversalNode(node) { if (node ! = null) { console.log(node.key); this.preOrderTraversalNode(node.left); this.preOrderTraversalNode(node.right); }} / / sequence traversal midOrderTraversal () {enclosing midOrderTraversalNode (enclosing root); } midOrderTraversalNode(node) { if (node ! = null) { this.midOrderTraversalNode(node.left); console.log(node.key); this.midOrderTraversalNode(node.right); After}} / / sequence traversal postOrderTraversal () {enclosing postOrderTraversalNode (enclosing root); } postOrderTraversalNode(node) { if (node ! = null) { this.postOrderTraversalNode(node.left); this.postOrderTraversalNode(node.right); console.log(node.key); }} search(key) {let node = this.root; while (node ! = null) { if (key > node.key) { node = node.right; } else if (key < node.key) { node = node.left; } else { return true; } } return false; Remove (key) {let parent = null; let current = this.root; let isLeftChild = true; While (current. Key! = key) { parent = current; if (key > current.key) { current = current.right; isLeftChild = false; } else { current = current.left; isLeftChild = true; } if (current == null) { return false; If (current == null && current. Right == null) {if (current == this.root) {this.root = null; } else if (isLeftChild) { parent.left = null; } else { parent.right = null; Else if (current == null) {if (current == this.root) {this.root = current. Right; } else if (isLeftChild) { parent.left = current.right; } else { parent.right = current.right; } } else if ((current.right = null)) { if (current == this.root) { this.root = current.left; } else if (isLeftChild) { parent.left = current.left; } else { parent.right = current.left; Succeeded = this.getantecedent (current); if (current == root) { this.root = successor; } else if (isLeftChild) { parent.left = successor; } else { parent.right = successor; } successor.left = current.left; }} getforerunner (delNode) {// Set variables to save temporary information let forerunner = delNode; let successorParent = delNode; let current = delNode.right; While (current! = null) { successorParent = successor; successor = current; current = current.left; } // Determine if the found successor is the right child of delNode if (succeeded! = delNode.right) { successorParent.left = successor.right; successor.right = delNode.right; } return successor; } // test let BST = new BinarySearchTree(); bst.insert(11); bst.insert(7); bst.insert(15); bst.insert(5); bst.insert(3); bst.insert(9); bst.insert(8); bst.insert(10); bst.insert(13); bst.insert(12); bst.insert(14); bst.insert(20); bst.insert(18); bst.insert(25); bst.insert(6); console.log(bst); bst.midOrderTraversal(); // bst.postOrderTraversal(); // console.log(bst.search(11)); // console.log(bst.search(2)); bst.remove(18); bst.midOrderTraversal();Copy the code

Delete operation roadmap

  1. Find nodes
  • Returns false if no node is found
  • There are three ways to find it:
    • This node is a leaf node
    • This node has one child node
    • This node has two children
  1. Remove nodes
  • It is relatively simple to delete nodes that are leaf nodes and have only one child node. Here only analyze the deletion of nodes with two child nodes.
  • If the node we are removing has two children, or even children with children, in which case we need to find a node from the child below to replace the current node.
  • How do I find this node?
    • A node slightly smaller than current must be the maximum value of the left subtree of current.
    • A node slightly larger than current must be the minimum of the right subtree of current.
  • Precursor & successor

In a binary search tree, these two special nodes have two special names.

  • Nodes slightly smaller than current are called precursors of current nodes.
  • Nodes slightly larger than current are called successors of current nodes.

In order to be able to delete current with two child nodes, either find its precursor or its successor.

Refer to coderwhy's data structure and algorithm recordsCopy the code