二叉树

定义:二叉,树

性质:左子<父<右子

接口:增删改查,前驱后继

扩充:重复元素,节点的value属性改为可变长数组?

图像直观:从根节点向下,每个节点完成了区间的一次划分。

相邻三个节点的区间:1.一端对其相交 2.不相交

查:根节点出发,判断进入左右子树,每一次下降动作,落入更小的区间范围,实际效果近似为对区间二分搜索点

后继(前驱):两个搜索方向:向下——mix(r-tree);向上——当前区间范围左侧增长,直至开始向右侧增长

增:查,添加区间划分点

max,min  一直向左,向右走

删:取max(left-tree),或min(right-tree),不破坏现有区间划分结构

遍历:中序遍历得到排序

原文地址:https://www.cnblogs.com/qmcj/p/9208386.html