Binary-Search-Tree

AVL之前写过的二叉排序树（BST）在插入、删除和查找等基本操作的平均时间为O(logN)，但在最坏的情况下，这些基本运算的时间均会增至O(n)（因为退化成了链表）。为了避免这些情况发生，人们研究了许多种动态平衡的方法，使得在树中插入或删除元素时，通过调整树的形态来保持树的“平衡”，使之既保持BST的性质不变又保证树的高度在任何情况下均为O(logN)，从而确保树上的基本运算在最坏情况下的时间也均为O(logN)。下面的AVL就是这样的平衡树。 AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。平衡二叉树递归定义如下： 左右子树的高度差小于等于 1。其每一个子树均为平衡二叉树。基于两点，我们就可以进行判断其一棵树是否为平衡二叉树了。 实现原理算法通过平衡因子（balaced factor，用bf表示）来具体实现上述平衡二叉树的定义。平衡因子的定义：平衡二叉树中每个节点有一个平衡因子，每个节点的平衡因子是该节点的左子树高度减去右子树的高度。从平衡因子的角度说，若一棵二叉树中所有节点的平衡因子的绝对值都小于等于1，即平衡因子取值为0、1或-1，则该二叉树为平衡二叉树。 用C语言定义该节点为： typedef struct node{ KeyType key; int bf; // 平衡因子 InfoType data; struct node *lchild, *rchild; } BSTNode;

题目要求Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.Basically, the deletion can be divided into two stages:Search for a node to remove.If the node is found, delete the node.Note: Time complexity should be O(height of tree).Example:root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \2 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。 ...