前面一章介绍了BST的结构和一些简单的基本功能，例如：insert，findMin，nextLarger等等。这一节主要讲解一些BST的delete node操作还有BST的height的分析以及一些潜在的问题。即本节主要包括以下2个部分；
1，Analysis of deletion
2，Tree height analysis
一：Node deletion
delete node的过程是需要依靠前一章的知识，需要了解nextLarger的过程和含义。然后在此基础之上，我们可以将删除node分为以下几类：
1）node是BST的leaf，即left child和right child 都为NULL；
2）node含有left subtree，但是没有right subtree;
3) node 含有right subtree, 但是没有left subtree;
4) node 含有right subtree和left subtree;
那么这4中情况下，如何删除相应的node，有什么规定需要遵守呢？如何删除的呢？下面2图分别展示了如何在上面的4中情况下删除相应的node
前三种的情况都比较简单，可以直观的了解。第四中情况，即node包含左右2个subtree的时候，情况就比较复杂了，我在这把流程解释一遍。当node包含左右2个subtree的时候，首先第一步是找到这个node的nextLarger，第二步copy nextLarger的key到node，第三步删除这个nextLarger node。至此删除node的操作结束。其具体的实现代码如下：（每个人的实现过程可能都不一样，仅供参考学习交流）
/* *Description: search the node's parent node * *parameters: 1. key //the value which we want to find within the BST 2. node//the node which we want to find out who is its parent node * *return Node * */ Node *BST::searchParent(int key, Node *node){ if (this->root == NULL) {//the BST has not initialzed yet return NULL; }else{ if (node==NULL) {//we have found all the nodes, but no one matches, which means it is not within the BST return NULL; }else if (key == node->getRight()->getKey()||key == node->getLeft()->getKey()) {//we spot on the key, return the node return node; }else if (key < node->getKey()){//the key is smaller than the node, so it is must be in the left subtree. return searchParent(key, node->getLeft()); }else{// the key is bigger than the node, so it is must be in the right subtree. return searchParent(key, node->getRight()); } } } /* *Description: delete a node from BST * * *parameter: * 1: key//the key that you want to delete * * 2：node //the node that we need to delete *return void * */ void BST::deleteNode(int key, Node *node){ Node *parentNode; if (node != this->root) {//node is not the root of the BST parentNode = searchParent(node->getKey(), this->root); }else{//the node is the root of BST parentNode = NULL; } if (node->getLeft() == nullptr && node->getRight() == nullptr) {//The node has not got any leaf if (parentNode->getKey()>node->getKey()) { parentNode->setLeft(NULL); }else{ parentNode->setRight(NULL); } delete(node); node = NULL; }else if (node->getRight() == nullptr){//has left tree if (parentNode->getKey()>node->getKey()) { parentNode->setLeft(node->getLeft()); }else{ parentNode->setRight(node->getLeft()); } delete node; node= NULL; }else if(node->getLeft() == nullptr){//has right tree if (parentNode->getKey()>node->getKey()) { parentNode->setLeft(node->getRight()); }else{ parentNode->setRight(node->getRight()); } delete node; node = NULL; }else{//has two subtrees Node *nextLargerNode = findNextLarger(node); int keyValue = nextLargerNode->getKey(); deleteNode(nextLargerNode->getKey(),nextLargerNode); node->setKey(keyValue); } }