Red and black tree

2-3 tree definition

A binary tree
A node can have up to 2 keys
The single-key node has 2 nodes
The double-bond node has 3 nodes

Left-leaning red-black tree definition

A binary tree
Nodes can be red or black
Only the left son can be a red node

The binary tree becomes a red-black tree with the additional information of node color, which is used to one-to-one correspond to a 2-3 tree

Left-leaning is to reduce the number of cases discussed and simplify the code (according to the book =-=)

Perfect balance is defined as a tree where each leaf node is the same distance from the root node

For simplicity, all of the following trees omit the perfectly balanced description

1. Insert operations

RotateL, rotateR, flipColors ensure that a red-black tree corresponds to a 2-3 tree.

2. Delete the vm

It is easy to delete three nodes but difficult to delete two nodes. Therefore, ensure that only three nodes are deleted.

2.1 Maximum Deletion

Deletion policy

Make sure to traverse nodes except the root nodehWhen,h 或 h.rightIn red
The current nodehIf the right node is empty, deleteh
Backtrack up to fix the temporary 4 nodes and the right red node caused by the downward recursion

2.2 Deleting the Minimum

Deletion policy

Make sure to traverse nodes except the root nodehWhen,h 或 h.leftIn red
The current nodehIf the left node of theh
Backtrack up to fix the temporary 4 nodes and the right red node caused by the downward recursion

2.3 Deleting Any

Deletion policy

Except for the root node, when recursing to the left, make sureh 或 h.leftAs the red; When you recurse to the right, make sureh 和 h.rightIn red
The current nodeh 的 keyEqual to deletekeyAnd,h.right 为 null“Is directly deletedh; ifh.rightDon’t fornull, the use ofh.rightMinimal element substitution in a subtreeh
Backtrack up to fix the temporary 4 nodes and the right red node caused by the downward recursion

3. Code

const RED = true;
const BLACK = false;

type RbtNodeProps = {
  key: any;
  val: any;
  left: RbtNode | null;
  right: RbtNode | null;
  color: boolean;
};

class RbtNode {
  key: any;
  val: any;

  left: RbtNode | null = null;
  right: RbtNode | null = null;
  color: boolean;

  constructor(props: RbtNodeProps) {
    this.key = props.key;
    this.val = props.val;
    this.left = props.left;
    this.right = props.right;
    this.color = props.color; }}// type RbtNode_LR = RbtNode & { left: RbtNode; right: RbtNode };
// type RbtNode_L = RbtNode & { left: RbtNode };
// type RbtNode_R = RbtNode & { right: RbtNode };

/* Q1: Why does insertion guarantee perfect balance between 2 and 3 trees? A1: By allowing the existence of double-bonded nodes (i.e. three nodes with three degrees), the degree of nodes is always increased by "expansion" during insertion, and then appropriate adjustment is made to make the tree meet the basic properties of 2-3 trees and perfectly balanced. When there are four nodes, the tree is made taller by proposing a "middle key" of four nodes to ensure that the definition of a 2-3 tree is met and perfectly balanced. */

export class Rbt {
  //#region root
  private root: RbtNode | null = null; // The root node is always black
  public getRoot() {
    return this.root;
  }
  //#endregion

  //#region get
  get(key: any) :any {
    return this._get(this.root, key);
  }
  private _get(h: RbtNode | null.key: any) :any {
    if (h === null) return null;

    if (key === h.key) return h.val;
    else if (key < h.key) return this._get(h.left, key);
    else return this._get(h.right, key);
  }
  //#endregion

  //#region min/max key
  min() {
    if (this.root === null) return null;
    return this._min(this.root);
  }
  private _min(h: RbtNode): any {
    if (h.left === null) return h.key;
    return this._min(h.left);
  }
  max() {
    if (this.root === null) return null;
    return this._max(this.root);
  }
  private _max(h: RbtNode): any {
    if (h.right === null) return h.key;
    return this._max(h.right);
  }
  //#endregion

  //#region put
  put(key: any, val: any) {
    this.root = this._put(this.root, key, val);

    // The root node is always black
    this.root.color = BLACK;
  }
  // Put a node to the subtree whose root node is h
  // Return the h node after put for post-rotation adjustment
  private _put(h: RbtNode | null.key: any.val: any): RbtNode {
    if (h === null) {
      return new RbtNode({
        // New nodes are always red, corresponding to the node expansion of the 23 tree
        key: key,
        val: val,
        left: null.right: null.color: RED,
      });
    }

    if (key < h.key) h.left = this._put(h.left, key, val);
    else if (key > h.key) h.right = this._put(h.right, key, val);
    else h.val = val;

    if (!this.isRed(h.left) && this.isRed(h.right)) h = this.rotateL(h);
    if (this.isRed(h.left) && h.left && this.isRed(h.left.left))
      h = this.rotateR(h);
    // If I move this line to the recursive putNode,
    // Then this left-leaning red-black tree will correspond to a two-three-four tree
    if (this.isRed(h.left) && this.isRed(h.right)) this.flipColors(h);

    return h;
  }
  //#endregion

  //#region delMin
  delMin() {
    if (this.root === null) return;

    this.root = this._delMin(this.root);
    if (this.root) this.root.color = BLACK;
  }
  private _delMin(h: RbtNode) {
    // When h.ft is null, it is illegal for h.ight not to be null
    // If h. light is null, you do not need to connect to H. light
    // return null to delete h
    if (h.left === null) return null;

    // Before recursively calling delMin
    // Make sure that h.left or H.left.left can be turned red
    if (!this.isRed(h.left) && !this.isRed(h.left.left))
      h = this.moveRedLeft(h);

    // delete recursively, assert that h.ft is not null,
    // Because h.fold does not start with null and moveRedLeft does not change h.fold to null
    h.left = this._delMin(h.left!) ;return this.fix(h);
  }
  // The function makes h.left. or h.left.left red
  private moveRedLeft(h: RbtNode) {
    // assert that h is red, h.left & H.right are black
    this.flipColors(h);
    // Because h.left! == null, for balance, assert that h.light must not be null
    if (this.isRed(h.right! .left)) { h.right =this.rotateR(h.right!) ; h =this.rotateL(h);
      this.flipColors(h);
    }
    return h;
  }
  //#endregion

  //#region delMax
  delMax() {
    if (this.root === null) return;

    this.root = this._delMax(this.root);
    if (this.root ! = =null) this.root.color = BLACK;
  }
  private _delMax(h: RbtNode) {
    // Before deleting, make sure h or H.light is red
    if (this.isRed(h.left)) h = this.rotateR(h);

    // h.light is the black null node,
    // So h is the red node
    // so h.ft must not be null, otherwise it is illegal
    // Therefore return null to delete
    if (h.right === null) return null;

    // Before recursively calling delMax
    // Make sure that h.light or H.light. right can become red nodes
    if (!this.isRed(h.right) && !this.isRed(h.right.left))
      h = this.moveRedRight(h);

    h.right = this._delMax(h.right!) ;return this.fix(h);
  }
  // The h.light or h.light. right function becomes a red node
  private moveRedRight(h: RbtNode) {
    this.flipColors(h);
    // h.light is not null, so assert that h.ft is not null
    if (this.isRed(h.left! .left)) { h =this.rotateR(h);
      this.flipColors(h);
    }
    return h;
  }
  //#endregion

  //#region del by key
  del(key: any) :void {
    if (this.root === null) return;

    this.root = this._del(this.root, key);
    if (this.root ! = =null) this.root.color = BLACK;
  }
  private _del(h: RbtNode, key: any): RbtNode | null {
    // The key is smaller than the key of the current node h
    // Make sure that h.left or h.left.left can become red
    if (key < h.key) {
      // If h.lift is null, the node corresponding to the key does not exist
      // The current h node does not need to do anything and does not continue recursion
      if(h.left ! = =null) {
        if (!this.isRed(h.left) && !this.isRed(h.left.left))
          h = this.moveRedLeft(h);

        h.left = this._del(h.left!, key);
      }
    }
    // key >= Key of current node H
    // (if key = h.key, whether h. light is null needs to be distinguished)
    else {
      // Because the strategy for deleting any key is to replace it with the smallest node in the right subtree of the deleted node
      // Therefore, when key = h.keey or key > h.keey, ensure that h or H.light is a red node
      // Therefore, the first step is to do the same as delMax, rotateR first
      // Make sure that h or H. light is red before deleting
      if (this.isRed(h.left)) h = this.rotateR(h);

      // When key = h.key and h. light is null
      // delete (h is the red node and H.light is null, so h.ft is null)
      if (key === h.key && h.right === null) return null;

      if(h.right ! = =null) {
        // If key > h.key or key = h.key but h. light is not null
        // We need to make sure that h.light or h.light. right can become a red node before recursive deletion
        if (!this.isRed(h.right) && !this.isRed(h.right.left))
          h = this.moveRedRight(h);

        // When key = h.key and h. light is not null
        // Change h to the smallest node in the subtree
        // Delete the smallest nodes in the h. light subtree
        if (key === h.key) {
          const minKey = this._min(h.right!) ; h.val =this._get(h.right, minKey); // change val first and then key
          h.key = minKey;
          h.right = this._delMin(h.right!) ; }else h.right = this._del(h.right!, key);
      }
    }

    return this.fix(h);
  }
  //#endregion

  //#region util functions
  private isRed(node: RbtNode | null) :boolean {
    if (node === null) return false;
    return node.color === RED;
  }
  private rotateL(h: RbtNode) {
    constx = h.right! ;// H must have a right son when left handed to h

    / / rotation
    h.right = x.left;
    x.left = h;

    // Fix the color
    x.color = h.color;
    h.color = RED;

    return x;
  }
  private rotateR(h: RbtNode) {
    constx = h.left! ;/ / rotation
    h.left = x.right;
    x.right = h;

    // Fix the color
    x.color = h.color;
    h.color = RED;

    return x;
  }
  // To decompose a 4-node, lift the key in the middle of the 4-node to the parent node, so change h to red
  private flipColors(h: RbtNode){ h.color = ! h.color; h.left! .color = ! h.left! .color; h.right! .color = ! h.right! .color; }private fix(h: RbtNode) {
    if (this.isRed(h.right)) h = this.rotateL(h);
    if (this.isRed(h.left) && this.isRed(h.left! .left)) h =this.rotateR(h);
    if (this.isRed(h.left) && this.isRed(h.right)) this.flipColors(h);
    return h;
  }
  //#endregion
}
Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structure & Algorithm/tree/balance tree/red black tree

Red and black tree

1. Insert operations

2. Delete the vm

2.1 Maximum Deletion

2.2 Deleting the Minimum

2.3 Deleting Any

3. Code

Data structure & Algorithm/tree/balance tree/red black tree

Red and black tree

1. Insert operations

2. Delete the vm

2.1 Maximum Deletion

2.2 Deleting the Minimum

2.3 Deleting Any

3. Code

Related Posts

Interviewer: Tell me how Redux handles asynchronous data streams.

Leetcode: Longest continuous sequence

Mobile real machine debugging