bst的successor

BST（二叉搜索树）的successor是指在该树中，比给定节点的值大的最小节点。具体而言，如果给定节点有右子树，则它的successor是其右子树中最小的节点。如果给定节点没有右子树，则需要沿着BST向上遍历，直到找到一个节点，它是其父节点的左子节点，那么该父节点就是该节点的successor。如果给定节点是该BST中最大的节点，则它没有successor。

相关问题

写一个至少十个数的数组，将其中数依次插入树里，实现BST的增删查改以及successor，注意是五个方法

好的，下面是代码实现：

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self, root=None):
        self.root = root
    
    def insert(self, val):
        if not self.root:
            self.root = Node(val)
        else:
            curr = self.root
            while curr:
                if val < curr.val:
                    if not curr.left:
                        curr.left = Node(val)
                        break
                    curr = curr.left
                else:
                    if not curr.right:
                        curr.right = Node(val)
                        break
                    curr = curr.right
    
    def delete(self, val):
        def get_successor(node):
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr
        
        def remove(node, val):
            if not node:
                return None
            if val == node.val:
                if not node.left and not node.right:
                    return None
                if not node.left:
                    return node.right
                if not node.right:
                    return node.left
                successor = get_successor(node)
                node.val = successor.val
                node.right = remove(node.right, successor.val)
            elif val < node.val:
                node.left = remove(node.left, val)
            else:
                node.right = remove(node.right, val)
            return node
        
        self.root = remove(self.root, val)
    
    def search(self, val):
        curr = self.root
        while curr:
            if val == curr.val:
                return curr
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return None
    
    def update(self, old_val, new_val):
        node = self.search(old_val)
        if node:
            self.delete(old_val)
            self.insert(new_val)
    
    def successor(self, val):
        node = self.search(val)
        if not node:
            return None
        if node.right:
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr.val
        else:
            parent = None
            curr = self.root
            while curr != node:
                if val < curr.val:
                    parent = curr
                    curr = curr.left
                else:
                    curr = curr.right
            return parent.val if parent else None

我们可以测试一下：

# 创建BST
bst = BST()

# 插入元素
arr = [10, 5, 15, 3, 7, 12, 17, 1, 4, 8]
for val in arr:
    bst.insert(val)

# 搜索元素
print(bst.search(7).val)  # 7
print(bst.search(9))  # None

# 找后继
print(bst.successor(7))  # 8
print(bst.successor(12))  # 15
print(bst.successor(17))  # None

# 更新元素
bst.update(7, 9)
print(bst.search(7))  # None
print(bst.search(9).val)  # 9

# 删除元素
bst.delete(10)
print(bst.search(10))  # None

用java写一个至少十个随机数的数组，将其中数依次插入树里，实现BST的增删查改以及successor

好的，下面是Java代码实现：

import java.util.Random;

public class BST {
    private Node root;

    private class Node {
        int val;
        Node left, right;

        Node(int val) {
            this.val = val;
        }
    }

    public void insert(int val) {
        root = insert(root, val);
    }

    private Node insert(Node node, int val) {
        if (node == null) {
            return new Node(val);
        }

        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }

        return node;
    }

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

    private Node delete(Node node, int val) {
        if (node == null) {
            return null;
        }

        if (val < node.val) {
            node.left = delete(node.left, val);
        } else if (val > node.val) {
            node.right = delete(node.right, val);
        } else {
            if (node.left == null && node.right == null) {
                node = null;
            } else if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                Node successor = findMin(node.right);
                node.val = successor.val;
                node.right = delete(node.right, successor.val);
            }
        }

        return node;
    }

    public boolean search(int val) {
        return search(root, val);
    }

    private boolean search(Node node, int val) {
        if (node == null) {
            return false;
        }

        if (node.val == val) {
            return true;
        } else if (val < node.val) {
            return search(node.left, val);
        } else {
            return search(node.right, val);
        }
    }

    public void update(int oldVal, int newVal) {
        delete(oldVal);
        insert(newVal);
    }

    public int successor(int val) {
        Node node = find(root, val);
        if (node == null) {
            return -1;
        }

        if (node.right != null) {
            return findMin(node.right).val;
        } else {
            Node successor = null;
            Node curr = root;
            while (curr != node) {
                if (node.val < curr.val) {
                    successor = curr;
                    curr = curr.left;
                } else {
                    curr = curr.right;
                }
            }
            return successor == null ? -1 : successor.val;
        }
    }

    private Node find(Node node, int val) {
        if (node == null) {
            return null;
        }

        if (node.val == val) {
            return node;
        } else if (val < node.val) {
            return find(node.left, val);
        } else {
            return find(node.right, val);
        }
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public static void main(String[] args) {
        BST bst = new BST();
        Random rand = new Random();
        int[] arr = new int[10];
        System.out.print("原数组: ");
        for (int i = 0; i < 10; i++) {
            arr[i] = rand.nextInt(100);
            System.out.print(arr[i] + " ");
            bst.insert(arr[i]);
        }
        System.out.println();

        System.out.println("插入后的BST: ");
        System.out.println(bst);

        int idx = rand.nextInt(10);
        int val = rand.nextInt(100);
        System.out.println("将第" + idx + "个数 " + arr[idx] + " 修改为 " + val);
        bst.update(arr[idx], val);
        arr[idx] = val;
        System.out.println(bst);

        idx = rand.nextInt(10);
        System.out.println("删除第" + idx + "个数 " + arr[idx]);
        bst.delete(arr[idx]);
        arr[idx] = -1;
        System.out.println(bst);

        idx = rand.nextInt(10);
        System.out.println("查找第" + idx + "个数 " + arr[idx] + " 是否存在: " + bst.search(arr[idx]));

        idx = rand.nextInt(10);
        int successor = bst.successor(arr[idx]);
        System.out.println("第" + idx + "个数 " + arr[idx] + " 的后继: " + successor);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        inOrder(root, sb);
        return sb.toString();
    }

    private void inOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        inOrder(node.left, sb);
        sb.append(node.val).append(" ");
        inOrder(node.right, sb);
    }
}

在 `main` 函数中，先生成一个长度为 10 的随机数组，并用 `insert` 方法将其中的数插入到 BST 中。然后，随机选取一个数，用 `update` 方法将其修改，再随机选取一个数，用 `delete` 方法将其删除。接着，随机选取一个数，用 `search` 方法查找其是否存在，最后随机选取一个数，用 `successor` 方法寻找其后继。