The binary data tree of the java data structure

binary sort tree / binary search tree

nature:

1. If the left subtree is not empty, the values ​​of all nodes on the left subtree are less than the value of its root node.

2. If the right subtree is not empty, the values ​​of all nodes on the right subtree are greater than the values ​​of its root node.

3. The left and right subtrees are also binary sort trees.

4. There are no nodes with the same value.

找步骤:

If the value of the root node is equal to the value of the searched keyword, it succeeds.

Otherwise, if it is less than the key value of the root node, recursively find the left subtree.

If the keyword value is greater than the root node, recursively find the right subtree.

If the subtree is empty, the search is unsuccessful.

定 P(n,i) is the average search length when the number of nodes in its left subtree is i. P(n): The average lookup length with N nodes.

上上图的 P(6, 3) = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 ​​+ 1) * 2 ] / 6

Average lookup length = sum of depths per node / summary points

P(3) = (1+2+2)/ 3 = 5/3

P(2) = (1+2)/ 2 = 3/2

∴ P(n,i)= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n

∴ P(n)=  P(n,i)/ n <= 2(1+I/n)lnn = O(logn)

Insert node:

public BinaryNode insert(int value, BinaryNode node) {
    if (node == null) {
        return new BinaryNode(value, null, null);
    }
    int result = node.getNodeValue().compareTo(value);
    if (result < 0) {
        node.rightNode = insert(value, node.getRightNode());
    } else if (result > 0) {
        node.leftNode = insert(value, node.getLeftNode());
    } else {
        System.out.println("duplicate value , fail to insert");
    }
    return node;
}

Delete node :

// 查找value最小的节点
public BinaryNode findMin(BinaryNode node) {
  if (node == null) {
      return node;
  } else if (node.getLeftNode() != null) {
      // 从左节点开始查找
      node = findMin(node.getLeftNode());
  }
  return node;
}

public BinaryNode delete(Integer value, BinaryNode node) {
    if (node == null) {
        return node;
    }
    // 将要删除的value值与二叉树的节点值比较
    int result = value.compareTo(node.getNodeValue());
    if (result < 0) {
        // 从左子树查找符合删除条件的节点,设置新的左子树
        node.setLeftNode(delete(value, node.getLeftNode()));
    } else if (result > 0) {
        // 从右子树查找符合条件的节点进行删除。设置新的右子树。
        node.setRightNode(delete(value, node.getRightNode()));
    } else if (node.getLeftNode() != null && node.getRightNode() != null) {
        // 左右子树同时不为空,从右子树查找值最小的节点,将它的值与当前父节点的值交换
        int minValue = findMin(node.getRightNode()).getNodeValue();
        node.setNodeValue(minValue);
        // 删除上述从右子树查找值最小的节点,设置新的右子树
        node.setRightNode(delete(node.getNodeValue(), node.getRightNode()));
    } else {
        // 左右子树有一个为空,该节点的子节点替代该节点。
        return node = (node.getLeftNode() != null) ? node.getLeftNode() : node.getRightNode();
    }
    return node;
}