1. //红黑树 ：  10到1的顺序插入验证木得问题了！
    2. class Nil {
    3.     constructor(parent) {
    4.         this.val = null;
    5.         this.parent = parent;
    6.         this.color = 2;
    7.     }
    8. }
    10. class Node {
    11.     constructor(val) {
    12.         this.val = val;
    13.         this.color = 1;  //红为1，黑为2，
    14.         this.parent = null;
    15.         this.left = new Nil(this);
    16.         this.right = new Nil(this);
    17.     }
    18. }
    20. class RedBlackTree {
    21.     constructor(item) {
    22.         this.root = item;
    23.     }
    25.     _search(val, root) {
    26.         const {left, right} = root;
    27.         const node = root.val > val ? left : right;
    28.         if (node instanceof Nil) return root;
    29.         return this._search(val, node);
    30.     }
    32.     search(val) {
    33.         if (this.root) {
    34.             return this._search(val, this.root);
    35.         }
    36.         return null;
    37.     }
    39.     update(node) {
    40.         const {parent, val} = node;   //默认传入的node的颜色都是1
    41.         if (parent) {
    42.             if (parent.color === 2) return;
    43.             const key = parent.val > val ? "left" : "right";
    44.             const sibling = parent[key === "left" ? "right" : "left"];
    45.             const grandP = parent.parent;
    46.             if (grandP) {
    47.                 const key1 = grandP.val > parent.val ? "left" : "right";
    48.                 const uncle = grandP[key === "left" ? "right" : "left"];
    49.                 if (uncle.color === 1) {  //情况3
    50.                     parent.color = 2;
    51.                     uncle.color = 2;
    52.                     grandP.color = 1;
    53.                     this.update(grandP);
    54.                 } else {
    55.                     if (key === "left") {  //情况4
    56.                         const grandPP = grandP.parent;
    57.                         grandP.color = 1;
    58.                         parent.color = 2;
    59.                         parent.right = grandP;
    60.                         grandP.left = sibling;
    61.                         grandP.parent = parent;
    62.                         // console.log(grandPP,'ppppp');
    63.                         if (grandPP) {
    64.                             const key2 = grandPP.val > grandP.val ?
    65.                                 "left" : "right";
    66.                             grandPP[key2] = parent;
    67.                             parent.parent = grandPP;
    68.                         } else {
    69.                             parent.parent = null;
    70.                             this.root = parent
    71.                             // console.log(parent,'ppp',node);
    72.                         }
    73.                     }else{  //情况5
    74.                         grandP[key1] = node
    75.                         node.parent = grandP
    76.                         node.left = parent
    77.                         parent.parent = node
    78.                         this.update(parent)
    79.                     }
    80.                 }
    81.             } else {
    82.                 parent.color = 2
    83.             }
    84.         } else {
    85.             node.color = 2
    86.         }
    87.     }
    89.     insert(val) {
    90.         const parent = this.search(val);
    91.         let node = new Node(val);
    92.         if (parent) {
    93.             const {color} = parent;
    94.             const key = val > parent.val ? "right" : "left";
    95.             if (!parent.parent) {  //2演变
    96.                 node.parent = parent;
    97.                 parent[key] = node;
    98.             } else {
    99.                 if (color === 2) {  //2
    100.                     node.parent = parent;
    101.                     return parent[key] = node;
    102.                 } else {
    103.                     parent[key] = node;
    104.                     node.parent = parent;  //连上node
    105.                     this.update(node);
    106.                 }
    107.             }
    108.         } else { //1
    109.             node.color = 2;
    110.             this.root = node;
    111.         }
    112.     }
    113. }
    115. const rbt=new RedBlackTree()
    116. for (let i=10;i>=0;i--){
    117.     rbt.insert(i)
    118.     console.log(i,rbt.root);
    119. }