树形常用算法

二叉搜索树

二叉搜索树具有如下特点

1. 左节点的值比父节点的值小，右节点的值比父节点的值大。根据此特点，可以在 O(logN) 下插入元素和查找元素
2. 二叉搜索树的中序遍历即为升序排序。所以在查询第 K 大（小）的数字时，可以先中序遍历再取值，也可以利用父节点额外存储子节点的个数，以此来查找

但由于在日常使用时，二叉搜索树太依赖于构建树的顺序，如果顺序为 [6,5,4,3,2,1] 来构造二叉搜索树，则和链表没什么区别，完全无法利用二叉搜索树的优势

所以推出别的数据结构，如 平衡二叉搜索树，红黑树，B/B+树

增

按照二叉搜索树的特点，当值比父节点小时，插入左节点，当值比父节点大时，插入右节点

查、改

按照二叉搜索树的特点，当值比父节点小时，向左节点查找，当值比父节点大时，向右节点查找

删

删除节点后，还需要保持二叉搜索树的特性

1. 删除的是叶子节点：可以直接删除
2. 删除的非叶子节点，但只有 1 个子节点：将子节点挪动到父节点为止
3. 删除的非叶子节点，有 2 个子节点：需在左子节点中找到最大值或者右子节点中找到最小值来补足