二叉树

二叉树查找

核心：递归判断大小 大走右节点 小走左节点

function find(node, value) {
  if(node === null) return null;
  if(node.value < value) find(node.right, value)
  if(node.value > value) find(node.left, value)
  else return value;
}

遍历二叉树

核心： 中序遍历二叉树

function dfs(node) {
    if(!node) return;
  dfs(node.left);
  console.log(node.value);
  dfs(node.right);
}

二三树

核心： 正常2叉树 都是一个2 节点 二三树引入了三节点 来树 平衡，让树的深度都是一样的， 让查找复杂度都是logn, (二叉树查找复杂度 最差情况下是n 1->2->3->4->5)

红黑树

核心： 将红链 展平就是二三树， 利用一些规则来让树平衡

规则： 如下图

红黑树插入算法实现

function rotate(node,direction) {
    const oppDirection = direction ==='left' ? 'right' : 'left'
    const tempNode = node[oppDirection];
    node[oppDirection] = tempNode[direction];
    tempNode[direction] = node;
    tempNode.color = 'black';
    tempNode[direction].color = 'red';
    return tempNode
}
function isRed(node) {
    return node.color === 'red'
}
function flipColors(node) {
    node.color = 'red'
    node.left.color = 'black'
    node.right.color = 'black'
    return node
}
// 红黑树插入
function redBlackInsert(node, value) {
    if(value > node.value) node.right = redBlackInsert(node.right,value);
    else if(value < node.value) node.left = redBlackInsert(node,value)
    if(isRed(node.right) && !isRed(node.left)) node = rotate(node,"left");
    if(isRed(node.left) && isRed(node.left.left)) node = rotate(node,"right");
    if(isRed(node.right) && isRed(node.left)) node = flipColors(node);
    return node
}