二叉查找树

查找树,小的在左、大的在右

查:用递归含if,在logN内找到元素结点

增:跟查的差不多,增加新结点相当于插入当时的叶子节点,或左或右
(建树就是一直调用增)

删:通过查找到target,判断左右子树是否为空,
若一边为空,直接继承别一边。
若两边都不为空,用右子树的min结点作为继承结点代替target
最后删除继承结点


为了防止一直插入小的/大的元素,导致斜树(单链表)

引出高度平衡的二叉搜索树

AVL:在插入新结点时,判断新节点到根的平衡因子是否合适,
不合适就再判断被插结点是LL,RR,LR,RL的那种,
分别进行右旋/左旋,以保证树的平衡


平衡:

左旋:被插结点的双亲结点变为他的Lc,
被插结点原来的Lc要变成双亲结点的Rc,
P树=被插结点

右旋反之

b-树就是m阶查找树,且符合一定性质

原文地址:https://www.cnblogs.com/mo-jian-ming/p/13922869.html