在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
经过对代码的更深入的跟踪理解,发现了superobject采用的是平衡二叉树的方式保存数据的。
首先看看保存数据的类 TSuperAvlEntry = class FGt和FLt分别是保存通过比较(比较hash或者比较key的asc)大的保存在Gt,小的保存在Lt,是一个二叉树链表。
先上图 假如有如下Json "assign": { 按照sosmASC排序模式 1.首先插入的是FAreaKey节点, 2.然后插入的是FAreaName时跟Root就是FAreaKey进行比较那他会插入到FAreaKey对应的节点的Gt下图形A1表示 3.然后插入的是FAreaCode跟FAreakey比较时为较小的插入到LT下面如图A2表示 4.A2图已经为平衡二叉树。
再看看按sosmAdd排序模式 按照sosmAdd的模式的话都是排在后面也就是都放在GT位置 1.首先插入的是FAreaKey节点, 2.然后插入的是FAreaName时跟Root就是FAreaKey进行比较那他会插入到FAreaKey对应的节点的Gt下图形A1表示 3.然后插入的是FAreaCode跟FAreakey比较时因为GT位置已经有了FAreaName,此时再跟FAreaName比较也是为大的插入FAreaName的GT下面如图B1表示 4.如图B1表示经过平衡二叉树后变成了B2样式。
这样查找的话,因为sosmAdd的查询时都是查找GT位置,不会查找LT分支,所以查询FAreaKey时会查询不到。 所以简单的办法就是如果安装sosmAdd方式存储是不进行平衡二叉数,这样所有的数据都保存在GT位置。这样就成为了一个链表的方式,这样可以从头查到尾。必然可以查到。
*****深入研究后发现查询时之前的不区分Key的大小写的修改其实很容易做到。
最终的Insert代码为 function TSuperAvlTree.Insert(h: TSuperAvlEntry): TSuperAvlEntry; var unbal, parentunbal, hh, parent: TSuperAvlEntry; depth, unbaldepth: longint; cmp: integer; unbalbf: integer; branch: TSuperAvlBitArray; p: Pointer; begin inc(FCount); h.FLt := nil; h.FGt := nil; h.FBf := 0; branch := []; if (FRoot = nil) then FRoot := h else begin unbal := nil; parentunbal := nil; depth := 0; unbaldepth := 0; hh := FRoot; parent := nil; repeat if (hh.FBf <> 0) then begin unbal := hh; parentunbal := parent; unbaldepth := depth; end; if hh.FHash <> h.FHash then begin if nowSortMode = sosmDefault then begin //original code if hh.FHash < h.FHash then cmp := -1 else if hh.FHash > h.FHash then cmp := 1 else cmp := 0; end else begin // modify by mofen cmp := CompareForSortModeString(h.Name, hh.Name); end; end else cmp := CompareNodeNode(h, hh); if (cmp = 0) then begin Result := hh; //exchange data p := hh.Ptr; hh.FPtr := h.Ptr; h.FPtr := p; doDeleteEntry(h, false); dec(FCount); exit; end; parent := hh; if (cmp > 0) then begin hh := hh.FGt; include(branch, depth); end else begin hh := hh.FLt; exclude(branch, depth); end; inc(depth); until (hh = nil); if (cmp < 0) then parent.FLt := h else parent.FGt := h; depth := unbaldepth; if (unbal = nil) then hh := FRoot else begin if depth in branch then cmp := 1 else cmp := -1; inc(depth); unbalbf := unbal.FBf; if (cmp < 0) then dec(unbalbf) else inc(unbalbf); if cmp < 0 then hh := unbal.FLt else hh := unbal.FGt; if ((unbalbf <> -2) and (unbalbf <> 2)) then begin unbal.FBf := unbalbf; unbal := nil; end; end; if (hh <> nil) then while (h <> hh) do begin if depth in branch then cmp := 1 else cmp := -1; inc(depth); if (cmp < 0) then begin hh.FBf := -1; hh := hh.FLt; end else (* cmp > 0 *) begin hh.FBf := 1; hh := hh.FGt; end; end; // original code // if (unbal <> nil) then if (unbal <> nil) and (nowSortMode <> sosmAdd) then //modify by mofen begin unbal := balance(unbal); if (parentunbal = nil) then FRoot := unbal else begin depth := unbaldepth - 1; if depth in branch then cmp := 1 else cmp := -1; if (cmp < 0) then parentunbal.FLt := unbal else parentunbal.FGt := unbal; end; end; end; result := h; end; |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论