preface

  • Data structure and algorithm have been ready to learn for a long time. Recently, I spent nearly three months of fragmented time to learn data structureconcept, as well asimplementation.
  • I talk about it as a trilogyI met–master–The linesOf course I’m still inI metThis paper mainly records the recent learning results and my thinking about it
  • Let’s start with the importance of understanding data structures and algorithms
  • Data structure I think it’s aThought model“, more abstract.
  • Maybe you have worked for 1-2 years and feel that the curD of your business is too simple, or you want to enter bat or other big factories as an intern during the algorithm competition in school
  • Then it may be integrated into the studyThe data structureAs well asalgorithmAnd the ones after thatDesign patternsIn the atmosphere
  • Because of itsabstractandThe base applicationIt is highly flexible, so it takes some time to learn, understand and apply (brush LeetCode)
  • Some people may ask what is the use of learning this? Work is hardly needed.
  • It is difficult to use, but the business of big factory business post why can ask these questions? Is it wrapped or? I think so, but not quite
  • First of all, if you can think of learning this means that you are interested in programming, which is of course very important. Otherwise, I don’t think you can go on this road very long, because writing code is very boring, unless you can get pleasure from it.
  • Second, its logical abstraction is very strong, you can master and use it shows that your logical thinking ability is not bad, spend more time on it, of course
  • To sum up, I think big factory wants to recruit a group of people who love programming and have strong logical thinking ability to improve work quality and efficiency.

I’d like to give you a little chicken soup before we start

The success or beauty that you aspire to has to be achieved day in and day out against laziness. All the way up is tortuous and difficult. And those easy roads, mostly downhill. Please believe that it is because of the seemingly hard work, dedication and persistence that you become a better version of yourself. — People’s Daily

What is a data structure?

  • Official definition: None
  • Folk definition:
    • “A data structure is a data object and the relationships that exist between an instance of that object and the data elements that make up the instance. These connections can be made by defining related functions.” — “Data Structure, Algorithm and Application”
    • “Data structures are physical implementations of ADT (Abstract Data Type).” — “Data Structure and Algorithm Analysis”
    • “A data structure is a way of storing and organizing data in a computer. Often, carefully chosen data structures lead to algorithms with optimal efficiency.” — Chinese Wikipedia

Data structures are used in daily life

E.g. A large library contains a large number of books, and we should not only put the books in, but also be able to take them out at the right time. Book placement should make two related operations convenient to achieve:

  • Operation 1: How to insert new book?
  • Operation 2: How to find a given book?

Various ways of placing books:

  • Method 1: Leave it anywhere
    • Operation 1: Put where there is space.
    • Operation 2: Find a book, tired to death.
  • Method 2: In alphabetical order according to the title of the book
    • Operation 1: enter a new “True Story of AH Q”, according to the alphabetical order to find the position, insert.
    • Operation 2: binary search method.
  • Method 3: Divide your bookshelves into sections and store them in alphabetical order by category
    • Operation 1: first set the category, binary search to determine the position, move out of the vacancy.
    • Operation 2: first set the category, then binary search.

Conclusion:

  • Problem solvingThe efficiency ofAccording to the dataorganizationThe relevant.
  • The amount of data stored in a computer is much larger, much more data than the books in a library.
  • In what waywayCome,storageandorganizationCan our data be used more conveniently?
  • That’s where the data structure comes in.

What is an Algorithm?

  • A finite set of instructions, the description of each instruction independent of language.
  • Receive some input (in some cases no input is required).
  • Generate output.
  • Must terminate after finite steps.

Popular understanding of algorithms

  • Is the solution/step logic of the problem.
  • The realization of data structure is inseparable from algorithm.

Algorithm of case

Suppose there is an overhead line between Shanghai and Hangzhou, the length of the overhead line is 1,000,000 meters, one day one meter of the overhead line breaks down, please come up with an algorithm, can quickly locate the problem everywhere.

  • Linear search
    • Start from the starting point of Shanghai one meter one meter investigation, and eventually will be able to find the line segment that went wrong.
    • But if the line segment is on the other end, we need to do 1,000,000 sweeps, which is the worst case, 500,000 sweeps on average.
  • Binary search
    • Start the investigation from the middle position, and see if the problem is from Shanghai to the middle position, or from the middle to Hangzhou.
    • Find the corresponding problem, and then separate from the middle position, re-lock the general distance.
    • Worst-case scenario, how many times will it take? The worst case scenario is 20 times to find the problem.
    • How do you figure that out? Log (1000000, 2), base two, logarithm of 1000000 ≈ 20.

As you can see, there are many ways to solve a problem, but a good algorithm is vastly more efficient than a bad one.

A representation of algorithm complexity

O is big O

symbol The name of the
O(1) The constant
O(log(
n n ))		 The logarithmic
O(
n n )		 linear
O(
n n log(
n n ))		 Linear and logarithmic products
O(
n n Squared)		 square
O(
2 n 2^{n} )		 index

Derive the representation of big O:

  1. Replace all addition constants in running time with constant 1
  2. In the modified run times function, onlyKeep the highest order terms
  3. If the highest exists and is not 1, the constant multiplied by the term is removed

If the time complexity of an algorithm is expressed as O(2 NNN ²+10000), count as O(2 NNN ²), omit 2 times and constant

The data structure

An array of

Array encapsulation in common languages (such as Java’s ArrayList)

  • An array of common languagesCan'tstoreDifferent data
  • Common languages do not automatically change array sizes (requiredcapacity)
  • The middle insert and delete performance of arrays in common languages is low

How is the underlying JavaScript array implemented?

  • www.voidcanvas.com/javascript-…
  • Originally implemented based on linked lists, many improvements have been made to allocate contiguous arrays of memory space

The stack structure

A stack is an operation-constrained linear table LIFO (Last in First out), based on arrays

Common operations on the stack

  • Push () adds a new element to the top of the stack.

  • Pop () removes the element at the top of the stack and returns the removed element.

  • Peek () returns the element at the top of the stack without making any changes to the stack (this method does not remove the element at the top of the stack, only returns it).

  • IsEmpty () returns true if there are no elements in the stack, false otherwise.

  • Size () returns the number of elements in the stack. This method is similar to the length property of an array.

  • ToString () returns the contents of the stack as a string

  • LIFO (Last in First out) is the last entry, the first to pop out of the stack space. Similar to the dinner tray, the last tray, often take out the first use.

  • The restriction is that only one end of the table can be inserted and deleted. This end is called the top of the stack, and the other end is called the bottom of the stack.

  • Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element.

  • To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element.

Code implementation


class Stack {
    public stack: any[]
    constructor() {
        this.stack = []
    }

    /** * push element * to the top of stack@param ele 
     */
    push(ele: any) {
        this.stack.push(ele)
    }

    /** * remove element */ from top of stack
    pop(): any {
        return this.stack.pop()
    }

    /** * returns the top element *@returns  {any}  * /
    peek(): any {
        const index = this.stack.length - 1
        return this.stack[index]
    }

    /** * whether the stack is empty *@returns {boolean}  * /
    isEmpty(): boolean {
        return this.stack.length === 0
    }

    /** * returns the number of stack elements *@returns {number}  * /
    size(): number {
        return this.stack.length
    }

    /** * returns the number of stack elements *@returns {string}  * /
    toString(): string {
        return this.stack.join("")}}Copy the code

Common topic

  1. Binary conversion
  2. Effective brackets

The queue

A Queue is a linear list with limited operations. It is characterized by first in, first out. (FIFO: First In First Out) based on arrays

Common operations on queues

  • enqueue(element)Adds one (or more) new items to the end of the queue.
  • dequeue()Removes the first item in the queue and returns the removed element.
  • front()Returns the first element in the queue – the first to be added and the first to be removed. No changes are made to the queue (no elements are removed, only element information is returned, very similar to the Map class peek method).
  • isEmpty()Return true if there are no elements in the queue, false otherwise.
  • size()Returns the number of elements contained in the queue, similar to the length property of an array.
  • toString()Converts the contents of the queue to a string.

Code implementation

class Queue {
    public items: any[]
    constructor() {
        this.items = []
    }

    /** * push one or more * into the queue@param ele 
     */
    enqueue(. ele:any) {
        this.items.push(... ele) }/** * Removes the queue header element *@returns {any} Removed item */
    denqueue(): any {
        return this.items.shift()
    }


    /** * returns the first element in the queue *@returns {any}* /
    front(): any {
        return this.items[0]}/** * whether the stack is empty *@returns {boolean} * /
    isEmpty(): boolean {
        return this.items.length === 0
    }

    /** * returns the number of stack elements *@returns {number}  * /
    size(): number {
        return this.items.length
    }

}
Copy the code

Priority queue

In fact, it is said that you can jump the queue so inherit the queue and increase the queue jumping function

Code implementation

class PriorityQueue extends Queue {
    // ele element order weight queue-jumping operation
    priorityEnqueue({ ele, order }: { ele: string, order: number }) {
        if (this.isEmpty()) {
            this.enqueue({ ele, order })
        }
        else {
            // This flag indicates whether the conditions within the loop are met -> that is, the needs to be inserted first
            // If the last one does not match, insert it directly to the end
            let flag = false
            for (let i = 0; i < this.items.length; i++) {
                if (this.items[i].order >= order) {
                    this.items.splice(i, 0, { ele, order })
                    flag = true
                    break}}// Indicates that the current order is larger than the previous order and is inserted directly to the end
            if(! flag) {this.enqueue({ ele, order })
            }
        }
    }
}
Copy the code

Singly linked list

A picture is worth a thousand words

Common operations in linked lists

  • Append (Element) adds a new item to the end of the list.

  • Insert (position, element) Inserts a new item into a specific position in the linked list.

  • Get (position) Gets the element at the corresponding position.

  • IndexOf (element) returns the indexOf the element in the linked list. Returns -1 if the element is not in the list.

  • Update (position, element) Modifies the element at a position.

  • RemoveAt (position) removes an item from a specific position in the linked list.

  • Remove (element) Removes an item from the list.

  • IsEmpty () returns trun if the list contains no elements, false if the list length is greater than zero.

  • Size () returns the number of elements the list contains, similar to the length property of an array.

  • ToString () Since the linked list item uses the Node class, we need to override the default toString method inherited from JavaScript objects to print only the value of the element.

    A linked list is a really fun data structure, why is it fun, because a lot of it lets us manipulate Pointers, the implementation of a linked list is based on objects, one-way lists are like a train of heads one after the other until it’s null

Code implementation

class Node {
 public ele: any;
 public next: any;
 constructor(ele: any) {
   // Save the element
   this.ele = ele;
   this.next = null; }}class LinkedList {
 public length: number;
 public head: any;
 constructor() {
   this.head = null;
   this.length = 0;
 }

 /** * add element * to the list@param ele* /
 append(ele: any) :void {
   const newNode = new Node(ele);
   // New a node when the current node is null
   if (this.head === null) {
     this.head = newNode;
   } else {
     // if head is not null, the length of the list is not 1
     let cur = this.head;
     while (cur.next) {
       cur = cur.next;
     }
     cur.next = newNode;
   }
   this.length++;
 }

 /** * insert element *@param The position location *@param Elements of ele *@returns* /
 insert(position: number.ele: any) :void {
   // Cross the line
   if (position > this.length || position < 0) return;
   const newNode: any = new Node(ele);
   // ==0 indicates to add in the header
   if (position === 0) {
     // Point next in the header to the current list
     newNode.next = this.head;
     this.head = newNode;
   } else {
     let i: number = 0;
     let cur: any = this.head;
     // List front node
     let pre = null;
     while (i++ < position) {
       pre = cur;
       // List next
       cur = cur.next;
     }
     pre.next = newNode;
     newNode.next = cur;
   }
   this.length++;
 }

 / * * * *@param The index position * /
 get(index: number) :any {
   if (index > this.length - 1 || index < 0) return;
   else {
     let i = 0;
     let cur = this.head;
     while (i++ < index) {
       cur = cur.next;
     }
     returncur; }}/ * * * *@param ele
  * @returns The index * /
 indexOf(ele: any) :number {
   if (this.isEmpty()) return -1;
   let i = 0;
   let cur = this.head;
   while (cur) {
     if (cur.ele === ele) break;
     cur = cur.next;
     i++;
   }
   return cur === null ? -1 : i;
 }

 /** * Update ele * for a location list@param position
  * @param ele* /
 update(position: number.ele: any) :void {
   /** * method 1 */
   this.removeAt(position);
   this.insert(position, ele);
 }

 /** ** removes * based on position@param position* /
 removeAt(position: number) :void {
   const length = this.length;
   let cur = this.head;
   if (position > length || position < 0) return;
   // Head is assigned null if the total length is 1 and needs to be removed
   else if (this.length === 1) {
     this.head = null;
   } else {
     // The pointer to head points to next of head
     if (position === 0) {
       if (cur && cur.next) {
         this.head = cur.next; }}else {
       let i = 0;
       let pre = null;
       while (i++ < position) {
         pre = cur;
         cur = cur.next;
       }
       pre.next = cur?.next;
     }
   }
   this.length--;
   return cur.ele;
 }

 /** * removes the element *@param ele* /
 remove(ele: any) :void {
   this.removeAt(this.indexOf(ele));
 }

 /** * whether the list is empty *@returns* /
 isEmpty(): boolean {
   return this.head === null;
 }

 /** * list size *@returns* /
 size(): number {
   return this.length; }}Copy the code

First, a node has two attributes: ele, the value of the current node. Next, Next points to the next node.

Two-way linked list

  • You can traverse from beginning to end, or from end to end.

  • The process of linking lists is two-way. The implementation principle is that a node has both a forward-connected reference and a backward-connected reference.

Common operations for bidirectional linked lists

  • append(element)Appends a new element to the end of the list.
  • insert(position, element)Inserts a new element at the specified position in the linked list.
  • getElement(position)Gets the element at the specified position.
  • indexOf(element)Returns the index of the element in the linked list. Returns -1 if the element is not in the list.
  • update(position, element)Modifies the element at the specified location.
  • removeAt(position)Removes the element at the specified position from the linked list.
  • remove(element)Removes the specified element from the linked list.
  • isEmpty()Returns if the list does not contain any elementstrun, if the list length is greater than 0false.
  • size()Returns the number of elements in the list, and the number of elements in the arraylengthProperties are similar.
  • toString()Because linked list entries use the Node class, we need to override the default inherited from JavaScript objectstoStringMethod to output only the value of the element.
  • forwardString()Returns the forward traversal node as a string.

Code implementation

import { LinkedList, Node } from "./linked_list";
class DoublyNode extends Node {
  public pre: any;
  constructor(ele: any) {
    super(ele);
    this.pre = null; }}/** * bidirectional list encapsulation */
class DoublyLikedList extends LinkedList {
  public tail: any;
  constructor() {
    super(a);/ / end nodes
    this.tail = null;
  }

  /** * insert * at the end@param ele* /
  append(ele: any) {
    const newNode = new DoublyNode(ele);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // Next of the tail equals the newly added node
      this.tail.next = newNode;
      // The front of the new node equals the tail of the previous node
      newNode.pre = this.tail;
      // Finally point the tail to the new node
      this.tail = newNode;
    }
    this.length++;
  }

  /** * inserts * at a position@param position
   * @param ele
   * @returns* /
  insert(position: number, ele: any) {
    if (position < 0 || position > this.length) return;

    const newNode = new DoublyNode(ele);
    // Insert in the header
    if (position === 0) {
      this.head.pre = newNode;
      newNode.next = this.head;
      this.head = newNode;
    } else if (position === this.length) {
      this.tail.next = newNode;
      newNode.pre = this.tail;
      this.tail = newNode;
    } else {
      let i = 0;
      let cur = this.head;
      let pre = null;
      while (i++ < position) {
        pre = cur;
        cur = cur.next;
      }
      pre.next = newNode;
      newNode.pre = pre;
      newNode.next = cur;
    }
    this.length++;
  }

  // Remove a position
  removeAt(position: number): any {
    if (position < 0 || position > this.length) return;
    let cur = this.head;
    if (position === 0) {
      this.head = this.head.next;
      // Set the header to null
      this.head.pre = null;
      if (this.length === 1) {
        this.tail = null; }}else if (position === this.length - 1) {
      cur = this.tail;
      // Set next to null
      this.tail.pre.next = null;
      // Point the tail to the top of the current tail
      // The equivalent of ignoring it means deleting it
      this.tail = this.tail.pre;
    } else {
      let i = 0;

      let pre = null;
      while (i++ < position) {
        pre = cur;
        cur = cur.next;
      }
      pre.next = cur.next;
      // The next layer above the current reference should be the last node removed by the current reference
      cur.next.pre = pre;
    }
    this.length--;
    return cur.ele;
  }

  /** * delete an element *@param ele* /
  remove(ele: any): any {
    const index = this.indexOf(ele);
    return this.removeAt(index);
  }

  forwardToString(): string {
    let currentNode = this.head;
    let result = "";
    while (currentNode) {
      result += currentNode.ele + "-";
      currentNode = currentNode.next;
    }
    return result.replace(/-$/g."")}}Copy the code

What is a bidirectional linked list diagram has been clear, is a previous layer

DoublyNode inherits from Node node,DoublyLikedList inherits from LinkedList. Through analysis, many methods can be shared, such as size,getElement and so on

The insert node and delete node of bidirectional linked list is also the most interesting, 4 reference operation, of course, in the insert and delete operation, need to consider the head, tail, middle and other three cases

Binary tree

If each node in the tree can have at most two children, such a tree is called a binary tree;

features

  • The maximal node tree of the i-th layer of a binary tree is: 2i−12^{i-1}2i−1, I >= 1;
  • The maximum number of nodes in a binary tree with depth of K is 2k2^{k} 2K-1, k >= 1;
  • For any nonempty binary tree, if n0Represents the number of leaf nodes, n2Represents the number of non-leaf nodes with degree 2, so the two satisfy the relation: n0 = n2+ 1; As shown in the figure below: H, E, I, J, G are leaf nodes, with a total of 5. A, B, C and F are non-leaf nodes with degree 2, and the total number is 4. Meet n0 = n2Plus one.

The term is commonly used

  • Degree of a node: the number of subtrees of a node. For example, Degree of node B is 2.
  • Degree of tree: the maximum degree of all nodes of the tree, such as the degree of the tree is 2;
  • Leaf node (Leaf node) : node with degree 0 (also known as Leaf node), such as H and I in the figure above;
  • Parent node: The node whose degree is not 0 is called the Parent node. For example, node B is the Parent node of nodes D and E.
  • Child: if B is the parent of D, D is the Child of B;
  • Sibling node: nodes with the same parent node are siblings. For example, B and C in the figure above, D and E are siblings.
  • Path and path length: Path refers to the channel from one node to another node. The number of edges contained in the path is called path length. For example, the path length of A->H is 3.
  • Node Level: the root node is at layer 1, and the number of layers of any other node is the number of layers of its parent node plus 1. For example, the level of nodes B and C is 2.
    • Tree Depth: The maximum level of all nodes of a tree is the Depth of the tree, as shown in the figure, which is 4.

Use linked list representation

Each Node is encapsulated into a Node, which contains stored data, a reference to the left Node, and a reference to the right Node.

So this is like a linked list? Compared with linked list, tree is to improve the search efficiency of data. The time complexity of simple linked list is O(n), so the concept of binary search tree is changed, and the time complexity is O(logn).

Binary search tree

Binary Search Tree (BST), also known as Binary sort Tree and Binary Search Tree.

A binary search tree is a binary tree that can be null.

If it is not empty, the following properties are satisfied:

  • Condition 1: All keys of a non-empty left subtree are less than the keys of its root node. For example, the key values of all non-empty left subtrees of node 6 are less than 6.
  • Condition 2: All keys of a non-empty right subtree are greater than those of its root node; For example, the key values of all non-empty right subtrees of node 6 are greater than 6.
  • Condition 3: left and right subtrees themselves are binary search trees;

As shown in the figure above, tree two and tree three meet three criteria to be a binary search tree, tree one does not meet condition three so it is not a binary search tree.

Summary: Binary search trees are mainly characterized by the fact that smaller values are always stored on the left node and relatively large values are always stored on the right node. This feature makes the query efficiency of binary search tree very high, which is the source of “search” in binary search tree.

Linear search

If you put all 15 in order

10 times to query data 10 in sorted array

In a binary search tree

  • First: compare 10 with root node 9. Since 10 > 9, 10 next compares with the right child node 13 of root node 9.
  • Second time: since 10 < 13, the next step of 10 is compared with the left child node 11 of parent node 13;
  • Third time: since 10 < 11, the next step of 10 is compared with the left child node 10 of parent node 11.
  • Fourth time: because 10 = 10, finally find data 10.

Code implementation

interface NodeInterface {
  key: number;
  left: NodeInterface | null;
  right: NodeInterface | null;
}

class Node {
  public key: any;
  public left: any;
  public right: any;
  constructor(key: any) {
    this.key = key;
    this.left = null;
    this.right = null; }}class SearchTree {
  private root: NodeInterface | null;
  constructor() {
    this.root = null;
  }

  preOverTreaverse() {

    this.preOrderTranverseNode(this.root)
  }

  // order traversal first
  preOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    console.log(node.key)
    this.preOrderTranverseNode(node.left)
    this.preOrderTranverseNode(node.right)
  }

  // middle order traversal
  inOrderTranverse() {
    this.inOrderTranverseNode(this.root)
  }

  // middle order traversal
  inOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    this.inOrderTranverseNode(node.left)

    console.log(node.key)
    this.inOrderTranverseNode(node.right)
  }

  // after the sequence traversal
  houOrderTranverse() {
    this.houOrderTranverseNode(this.root)
  }

  // after the sequence traversal
  houOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    this.houOrderTranverseNode(node.left)
    this.houOrderTranverseNode(node.right)
    console.log(node.key)

  }

  / / insert
  insertNode(node: NodeInterface, newNode: NodeInterface) {
    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)
      }

    }

  }

  insert(key: number) {
    var newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  min(): number | null {
    let node = this.root
    while(node? .left) { node = node.left }return node === null ? null : node.key
  }

  max(): number | null {
    let node = this.root
    while(node? .right) { node = node.right }return node === null ? null : node.key
  }

  search(key: number): boolean {
    return this.searchNode(this.root, key)
  }


  searchNode(node: NodeInterface | null.key: number): boolean {
    if (node === null) {
      return false
    }
    if (key > node.key) {
      return this.searchNode(node.right, key)
    }
    else if (key < node.key) {
      return this.searchNode(node.left, key)
    }
    else {
      return true}}remove(key: number) {
    if (this.root === null) return
    let cur = this.root
    let parent = null
    let isLeft = true
    while(cur.key ! == key) { parent = curif (key < cur.key) {
        if(cur.left ! = =null) {
          cur = cur.left
          isLeft = true}}else if (key > cur.key) {
        if(cur.right ! = =null) {
          cur = cur.right
          isLeft = false}}}// When the current node is a leaf node
    if (cur.left === null && cur.right === null) {
      if (parent === this.root) {
        this.root = null
      }
      else if (parent && isLeft) {
        parent.left = null
      }
      else if (parent) {
        parent.right = null}}// A binary tree with nondegree 2 has nodes on the left
    else if (cur.right === null) {
      if (this.root === cur) {
        this.root = cur.left
      }
      else if (isLeft && parent) {
        parent.left = cur.left
      }
      else if (parent) {
        parent.right = cur.left
      }
    }
    else if (cur.left === null) {
      if (this.root === cur) {
        this.root = cur.right
      }
      else if (isLeft && parent) {
        parent.left = cur.right
      }
      else if (parent) {
        parent.right = cur.right
      }
    }
    // Complete binary tree
    else {
      // 1
      let successor = this.getSuccessor(cur);

      // 2. Check whether the node is the root node
      if (cur === this.root) {
        this.root = successor;
      } else if (isLeft && parent) {
        parent.left = successor;
      } else {
        if (parent)
          parent.right = successor;
      }
      // change the subsequent left node to the deleted left nodesuccessor.left = cur.left; }}getSuccessor(delNode: NodeInterface) {
    // Define a variable to hold the follow-up to be found
    let successor = delNode;
    let current = delNode.right;
    let successorParent = delNode;

    // Loop to find the right subtree node of current
    while(current ! = =null) {
      successorParent = successor;
      successor = current;
      current = current.left;
    }

    // Determine whether the subsequent node is directly the right to delete the node
    if(successor ! == delNode.right) { successorParent.left = successor.right; successor.right = delNode.right; }returnsuccessor; }}Copy the code

Ps: the recursive idea of the tree and the deletion degree of 2 nodes is a key to understand it is very easy