6-二叉查找树

参考链接

• 一步一步写二叉查找树

二叉查找树（BST）是二叉树的一个重要的应用，它在二叉树的基础上加上了这样的一个性质：对于树中的每一个节点来说，如果有左儿子的话，它的左儿子的值一定小于它本身的值，如果有右儿子的话，它的右儿子的值一定大于它本身的值。

二叉查找树的操作一般有插入、删除和查找，这几个操作的平均时间复杂度都为O(logn)，插入和查找操作很简单，删除操作会复杂一点，除此之外，因为二叉树的中序遍历是一个有序序列，我就额外加上了一个中序遍历操作。

二叉查找树的应用不是很多，因为它最坏的时候跟线性表差不多，大部分会应用到它的升级版，平衡二叉树和红黑树，这两棵树都能把时间复杂度稳定在O(logn)左右。虽然不会用到，但是二叉查找树是一定要学好的，毕竟它是平衡二叉树和红黑树的基础。

接下来一步一步写一个二叉查找树模板。

第一步：节点信息

二叉查找树的节点和二叉树的节点大部分是一样的，不同的是，二叉查找树多了一个值出现的次数。如图1显示了二叉查找树的节点信息。

img

class TreeNode<T> {
    var parent: TreeNode?
    var leftChild: TreeNode?
    var rightChild: TreeNode?
    
    var frequence = 0
    var value: T
    
    init(value: T) {
        self.value = value
    }
}

第二步：二叉查找树类的声明

class BinaryTree<T where T: Comparable> {
    var root: TreeNode<T>?
    var nodeNum = 0
    
    func insert(value: T) {

    }
    
    func find(value: T) -> TreeNode<T>? {
    }
    
    func delete(value: T) {
    }
    
    func travel() {
        
    }
    
    func height() -> Int {
        
    }
}

第三步：插入

根据二叉查找树的性质，插入一个节点的时候，如果根节点为空，就此节点作为根节点，如果根节点不为空，就要先和根节点比较，如果比根节点的值小，就插入到根节点的左子树中，如果比根节点的值大就插入到根节点的右子树中，如此递归下去，找到插入的位置。重复节点的插入用值域中的freq标记。如图2是一个插入的过程。

img

二叉查找树的时间复杂度要看这棵树的形态，如果比较接近一一棵完全二叉树，那么时间复杂度在O(logn)左右，如果遇到如图3这样的二叉树的话，那么时间复杂度就会恢复到线性的O(n)了。

img

平衡二叉树会很好的解决如图3这种情况。

插入函数的代码如下：

private func insert(value: T, under parentNode: TreeNode<T>?) {
        //如果根节点为空，就此节点作为根节点
        if root == nil {
            root = TreeNode(value: value)
            return
        }
        
        //为待插入的元素查找最终插入位置的父节点
        var finalParentNode = parentNode
        var currentNode = parentNode
        repeat {
            finalParentNode = currentNode
            //如果相等,就把频率加1
            if value == currentNode?.value {
                currentNode?.frequence += 1
                return
            }
            
            if value < currentNode?.value {
                currentNode = currentNode?.leftChild
            } else {
                currentNode = currentNode?.rightChild
            }
        } while (currentNode != nil)
        
        let node = TreeNode(value: value)
        node.parent = finalParentNode
        if value < finalParentNode?.value {
            finalParentNode?.leftChild = node
        } else {
            finalParentNode?.rightChild = node
        }
    } 

第四步：查找

查找的功能和插入差不多一样，按照插入那样的方式递归下去，如果找到了，就返回这个节点的地址，如果没有找到，就返回NULL。

代码如下：

func find(value: T) -> TreeNode<T>? {
        var currentNode = root
        while currentNode != nil {
            if value == currentNode?.value {
                return currentNode
            }
            if value < currentNode?.value {
                currentNode = currentNode?.leftChild
            } else {
                currentNode = currentNode?.rightChild
            }
        }
        return nil
    }

第五步：删除

删除会麻烦一点，如果是叶子节点的话，直接删除就可以了。如果只有一个孩子的话，就让它的父亲指向它的儿子，然后删除这个节点。图4显示了一棵初始树和4节点被删除后的结果。先用一个临时指针指向4节点，再让4节点的地址指向它的孩子，这个时候2节点的右儿子就变成了3节点，最后删除临时节点指向的空间，也就是4节点。

img

删除有两个儿子的节点会比较复杂一些。一般的删除策略是用其右子树最小的数据代替该节点的数据并递归的删除掉右子树中最小数据的节点。因为右子树中数据最小的节点肯定没有左儿子，所以删除的时候容易一些。图5显示了一棵初始树和2节点被删除后的结果。首先在2节点的右子树中找到最小的节点3，然后把3的数据赋值给2节点，这个时候2节点的数据变为3，然后的工作就是删除右子树中的3节点了，采用递归删除。

img

我们发现对2节点右子树的查找进行了两遍，第一遍找到最小节点并赋值，第二遍删除这个最小的节点，这样的效率并不是很高。你能不能写出只查找一次就可以实现赋值和删除两个功能的函数呢？

如果删除的次数不是很多的话，有一种删除的方法会比较快一点，名字叫懒惰删除法：当一个元素要被删除时，它仍留在树中，只是多了一个删除的标记。这种方法的优点是删除那一步的时间开销就可以避免了，如果重新插入删除的节点的话，插入时也避免了分配空间的时间开销。缺点是树的深度会增加，查找的时间复杂度会增加，插入的时间可能会增加。

删除函数代码如下：

func delete(value: T) {
        var currentNode = root
        while currentNode != nil {
            if value == currentNode?.value {
                //如果是叶子节点的话，直接删除就可以了
                if currentNode?.leftChild == nil && currentNode?.rightChild == nil {
                    if currentNode === currentNode?.parent?.leftChild {
                        currentNode?.parent?.leftChild = nil
                    } else {
                        currentNode?.parent?.rightChild = nil
                    }
                    currentNode?.cleanup()
                } else {
                    /**
                     *  删除有两个儿子的节点会比较复杂一些。
                     一般的删除策略是用其右子树最小的数据代替该节点的数据并递归的删除掉右子树中最小数据的节点。
                     因为右子树中数据最小的节点肯定没有左儿子，所以删除的时候容易一些。
                     */
                    if currentNode?.leftChild != nil && currentNode?.rightChild != nil {
                        var minNode = currentNode?.rightChild
                        repeat {
                            if minNode?.leftChild != nil {
                                minNode = minNode?.leftChild
                            } else {
                                break
                            }
                        }
                        currentNode?.value = minNode!.value
                        currentNode?.frequence = minNode!.frequence
                        minNode?.parent?.leftChild = nil
                        minNode?.cleanup()
                    } else {
                        //如果只有一个孩子的话，就让它的父亲指向它的儿子，然后删除这个节点。
                        if currentNode?.leftChild != nil {
                            currentNode?.parent?.leftChild = currentNode?.leftChild
                        } else {
                            currentNode?.parent?.rightChild = currentNode?.rightChild
                        }
                        currentNode?.cleanup()
                    }
                }
                return
            }
            if value < currentNode?.value {
                currentNode = currentNode?.leftChild
            } else {
                currentNode = currentNode?.rightChild
            }
        }
    }

第六步：中序遍历

遍历的方法和二叉树的方法一样，写这个方法的目的呢，是输出这个二叉查找树的有序序列。

代码如下：

//中序遍历,输出这个二叉查找树的有序序列。
    func travel() {
        //递归实现
        travel(root)
        
        /*
         中序遍历的非递归实现
         根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历
         非递归的实现思路如下：对于任一节点P，
         
         1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
         2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
         3）若不为空，则重复1）和2）的操作；
         4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
         5）直到当前节点P为NULL并且栈为空，则遍历结束。
         */
        let nodeStack = Stack<TreeNode<T>>()
        var currentNode = root
        while currentNode != nil {
            //如果Cur左孩子不为空，则将其入栈，并置其左孩子为当前节点
            if let leftChild = currentNode?.leftChild {
                nodeStack.push(leftChild)
                currentNode = leftChild
                continue
            } else {
                //如果pCur的左孩子为空，则输出pCur节点，并将其右孩子设为当前节点，看其是否为空
                print(currentNode?.value)
                currentNode = currentNode?.rightChild
                
                //如果为空，且栈不空，则将栈顶节点出栈，并输出该节点，
                //同时将它的右孩子设为当前节点，继续判断，直到当前节点不为空
                while currentNode == nil && !nodeStack.isEmpty() {
                    let parentNode = nodeStack.pop()!
                    print(parentNode.value)
                    currentNode = parentNode.rightChild
                }
            }
        }
    }
    
    func travel(node: TreeNode<T>?) {
        if node != nil {
            travel(node?.leftChild) //先遍历左子树
            print(node?.value)      //输出根节点
            travel(node?.rightChild)//再遍历右子树
        }
    }     

对于二叉查找树不稳定的时间复杂度的解决方案有不少，平衡二叉树、伸展树和红黑树都可以解决这个问题，但效果是不一样的。

中序遍历的非递归实现

根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的中序遍历顺序为：DBEAFC。非递归的实现思路如下：

对于任一节点P，

1. 若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2. 若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3. 若不为空，则重复1）和2）的操作；
4. 若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5. 直到当前节点P为NULL并且栈为空，则遍历结束。

img

下面以上图为例详细分析其中序遍历的非递归实现过程：

1. 首先，从根节点A开始，A的左孩子不为空，根据操作1）将A入栈，接着将B置为当前节点，B的左孩子也不为空，根据操作1），将B也入栈，接着将D置为当前节点，由于D的左子树为空，根据操作2），输出D；
2. 由于D的右孩子也为空，根据操作4），执行出栈操作，将栈顶结点B出栈，并将B置为当前节点，此时输出序列为DB；
3. 由于B的右孩子不为空，根据操作3），将其右孩子E置为当前节点，由于E的左孩子为空，根据操作1），输出E，此时输出序列为DBE；
4. 由于E的右孩子为空，根据操作4），执行出栈操作，将栈顶节点A出栈，并将节点A置为当前节点，此时输出序列为DBEA；
5. 此时栈为空，但当前节点A的右孩子并不为NULL，继续执行，由于A的右孩子不为空，根据操作3），将其右孩子C置为当前节点，由于C的左孩子不为空，根据操作1），将C入栈，将其左孩子F置为当前节点，由于F的左孩子为空，根据操作2），输出F，此时输出序列为：DBEAF；
6. 由于F的右孩子也为空，根据操作4），执行出栈操作，将栈顶元素C出栈，并将其置为当前节点，此时的输出序列为：DBEAFC；
7. 由于C的右孩子为NULL，且此时栈空，根据操作5），遍历结束。