学习笔记之二叉查找树

二叉查找树（二叉排序树）

二叉排序树（binary sort tree），又称为二叉查找树（binary search tree）

• 左子树不为空，则左子树所有节点小于根节点值
• 右子树不为空，则右子树所有节点大于根节点值
• 左右子树同时也为二叉排序树

中序遍历可得到有序的序列

---

查找

递归查询左，右子树

插入

1. if the new node's value is lower than the current node's, we go to the left child
2. if the new node's value is greater than the current node's, we go to the right child
3. when the current node is null, we've reached a leaf node and we can insert the new node in that position

删除

删除叶子节点

删除节点只有左子树或只有右子树

节点删除后，左右子树整体移动到删除节点位置

删除节点既有左子树又有右子树

从要被删除的节点的左右子树，找出可以替换当前节点的数值

• 直接前驱，比该节点小的最大值
• 直接后继，比该节点大的最小值

---

二叉查找树的总结

二叉查找树以链式的方式存储，插入和删除只需找到位置后，修改指针即可 - 较好的插入删除性能

查找则依赖于树的深度 - 取决于树的形状， 但二叉排序树的最差情况是斜树。。。

因此期望树的形状是比较平衡的，理想情况深度与完全二叉树相同，\(\lfloor log_2n \rfloor\) +1 , 那么查找的时间复杂度也为 O(\(\lfloor logn \rfloor\)) ; 否则斜树的查找时间复杂度为o(n).

相关

AVL

红黑树

---

代码实现

public static Node searchNode(Node node, int value) {

  if (node == null) {
    return null;
  }

  if (node.getValue() == value) {
    return node;
  }
  return value < node.getValue()
    ?  searchNode(node.getLeft(), value)
    : searchNode(node.getRight(), value);

}

public static Node search(BinaryTree binaryTree, int value) {
  return searchNode(binaryTree.getRoot(), value);
}

public Node addRecursive(Node current, int value) {
  if (current == null) {
    return new Node(value);
  }

  if (value < current.value) {
    current.left = addRecursive(current.left, value);
  } else {
    current.right = addRecursive(current.right, value);
  }
  return current;

}

public void add(int value) {
  root = addRecursive(root, value);
}

public void delete(int value) {
  root = deleteRecursive(root, value);
}

public Node deleteRecursive(Node current, int value) {
  if (current == null) {
    return null;
  }

  if (value == current.value) {
    // case1: no children
    if (current.left == null && current.right == null) {
      return null;
    }

    // case2: only 1 child
    if (current.left == null) {
      return current.right;
    }
    if (current.right == null) {
      return current.left;
    }

    // case3: 2 children (most complex)
    /**
             * 思路: 找出左子树最大或者右子树最小来取代要删除的节点， 然后再删除左子树最大节点或右子树最小节点
             * 这个选择找出右子树最小节点- 最左下位置
             */
    int smallValue = findSmallestValue(current);
    current.value = smallValue;
    current.right = deleteRecursive(current.right, smallValue);
    return current;
  }

  if (value < current.value) {
    current.left = deleteRecursive(current.left, value);
  } else {
    current.right = deleteRecursive(current.right, value);
  }
  return current;

}


private int findSmallestValue(Node root) {
  return root.left == null ? root.value : findSmallestValue(root.left);
}