二叉排序树

/*
    二叉排序树的查找：
    函数返回指向关键字为key结点的指针，如果没有，返回NULL
    p指向被查找结点的双亲，方便用来进行插入和删除操作
*/
    理解：
    1.p为什么可以用来方便插入操作？
    原因：如果想插入关键值为key的结点，
    在调用这个函数之后，若函数返回值不为NULL，不需要进行插入操作（这个值已存在）；
    若函数返回值为NULL，那么这个值应该插入在结点*p的下面
    （左右子树根据key和p->data进行判断）

    2.为什么可以方便进行删除操作？
    原因：已找到待删除结点的父节点

BSTNode* BST_Search(BiTree T, ElemType key, BSTNode *&p)
{
    BSTNode *p = NULL;
    while (T != NULL && T->data != key) {
        p = T;
        if (T->data < key)
            T = T->rchild;
        else
            T = T->lchild;
    }
    return T;
}

/*
    二叉排序树的插入
*/
算法思想：
    1.若原二叉排序树为NULL,则直接插入结点
    2.若关键字小余根节点关键词，那么插入左子树
    3.若关键字小余根节点关键字，那么插入右子树

eg.新插入的节点一个是一个叶子节点

bool BST_Insert(BiTree &T, KeyType key)
{
    if (T == NULL) {
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
        return true;
    }
    else if (T->key == key)
        return false;
    else if (key < T->key)
        return BST_Insert(T->lchild);
    else
        return BST_Insert(T->rchild);
}

eg.这里自己理解的时候有一个误区，就是如果传入一个NULL，
那么T=(BiTree)malloc(sizeof(BSTNode))是不是没有用呢？
注意：这里是使用引用传参数，就是传入的是地址，这里的赋值操作相当于是
把对一个结点的引用写入到这个地址当中，是计算机系统基础里面的知识
（因此调用此函数的时候，传入的参数一定是变量，不应该是常量！！）

/*二叉树的构造*/
算法思想：依次输入数据元素，并将它们插入到二叉树适当位置上的过程

void Creat_BST(BiTree &T, KeyType A[], int n)
{
    T = NULL;
    int i = 0;
    for (int i = 0; i < n; i++)
        BST_Insert(T,A[i]);
}

eg.调用Create_BST时候，第一个参数一定要是变量！！

/*二叉排序树的删除*/
1.若被删除的结点是叶子结点，直接删除
2.若被删除的结点*p只有左子树或者只有右子树，则让*p的子树成为*p双亲结点的子树
3.若被删除的结点*p有左右子树，则可以让*p的“直接前驱”或者“直接后继”代替*p,并且删除*p,
之后就可以转换成1或者2的情况。
那么为什么可以转换成1，2的情况呢？因为直接前驱和直接后继一定都不是双分支节点，呃呃呃呃

这里寻找一个满足中序遍历有序的BST的前驱和后继非常的方便

补充知识
补充知识

二叉排序树的效率分析：
1.高度为H的BST，插入和删除的时间复杂度是O（H）
2.BST的平均查找长度，主要取决于二叉树的形态
3.若BST是一个只有左孩子和右孩子的单分支树，平均查找长度为O(n);
  若BST是左右子树高度差不超过1，平均查找长度O(logn)
4.二分查找的判定树唯一，而二叉排序树不唯一，相同的关键词插入顺序不同，树的形态不同
5.对于一个正常的二叉排序树，插入，删除不需要移动节点，时间复杂度O（logn）
  对于二分查找，因为是使用顺序表存储，插入删除需要移动节点，时间复杂度为O（n）
6.有序表是静态查找表：使用顺序表
   有序表是动态查找表：使用BST

那么啥是红黑树呢？

红黑树简介

平衡二叉树

四个方法，只要熟悉了中序线索二叉树的前驱后继，看懂没有问题：LL,RR,LR,RL

1.每次调整最小不平衡子树
2.这里要有一种观点，就是把一个二叉排序树的子树当成一个结点理解，这里是可以的。

image.png
image.png
image.png
image.png

/*平衡二叉树的查找*/
    Nh表示深度为h的平衡二叉树的最少结点数:
    Nh=N（h-1）+N(h-2)+1
    N0=0,N1=1,N2=2
eg.计算给定结点数的平衡二叉树的最多比较次数！！！

哈夫曼树

wpl最小的二叉树

特点：
1.n个初始结点都成为了叶子结点，权值小的结点到根结点的路径最长
2.新建n-1个结点，共计2n-1个结点
3.不存在度为1的结点