| 1 | ///
|
|---|
| 2 | /// This file is part of ILNumerics Community Edition.
|
|---|
| 3 | ///
|
|---|
| 4 | /// ILNumerics Community Edition - high performance computing for applications.
|
|---|
| 5 | /// Copyright (C) 2006 - 2012 Haymo Kutschbach, http://ilnumerics.net
|
|---|
| 6 | ///
|
|---|
| 7 | /// ILNumerics Community Edition is free software: you can redistribute it and/or modify
|
|---|
| 8 | /// it under the terms of the GNU General Public License version 3 as published by
|
|---|
| 9 | /// the Free Software Foundation.
|
|---|
| 10 | ///
|
|---|
| 11 | /// ILNumerics Community Edition is distributed in the hope that it will be useful,
|
|---|
| 12 | /// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 13 | /// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 14 | /// GNU General Public License for more details.
|
|---|
| 15 | ///
|
|---|
| 16 | /// You should have received a copy of the GNU General Public License
|
|---|
| 17 | /// along with ILNumerics Community Edition. See the file License.txt in the root
|
|---|
| 18 | /// of your distribution package. If not, see <http://www.gnu.org/licenses/>.
|
|---|
| 19 | ///
|
|---|
| 20 | /// In addition this software uses the following components and/or licenses:
|
|---|
| 21 | ///
|
|---|
| 22 | /// =================================================================================
|
|---|
| 23 | /// The Open Toolkit Library License
|
|---|
| 24 | ///
|
|---|
| 25 | /// Copyright (c) 2006 - 2009 the Open Toolkit library.
|
|---|
| 26 | ///
|
|---|
| 27 | /// Permission is hereby granted, free of charge, to any person obtaining a copy
|
|---|
| 28 | /// of this software and associated documentation files (the "Software"), to deal
|
|---|
| 29 | /// in the Software without restriction, including without limitation the rights to
|
|---|
| 30 | /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
|
|---|
| 31 | /// the Software, and to permit persons to whom the Software is furnished to do
|
|---|
| 32 | /// so, subject to the following conditions:
|
|---|
| 33 | ///
|
|---|
| 34 | /// The above copyright notice and this permission notice shall be included in all
|
|---|
| 35 | /// copies or substantial portions of the Software.
|
|---|
| 36 | ///
|
|---|
| 37 | /// =================================================================================
|
|---|
| 38 | ///
|
|---|
| 39 |
|
|---|
| 40 | using System;
|
|---|
| 41 | using System.Collections.Generic;
|
|---|
| 42 | using System.Linq;
|
|---|
| 43 | using System.Text;
|
|---|
| 44 | using keytype = System.Int64;
|
|---|
| 45 |
|
|---|
| 46 | namespace ILNumerics.Data {
|
|---|
| 47 | /// <summary>
|
|---|
| 48 | /// AVL balanced search tree
|
|---|
| 49 | /// </summary>
|
|---|
| 50 | /// <remarks>The tree stores unique keys (type:System.Int64, configurable via build) in a balanced search tree.
|
|---|
| 51 | /// <para>The implementation is optimized for random seek access and consecutive write access - if no matching key found.
|
|---|
| 52 | /// Also, the next higher key for a given query can be returned in O(1).</para>
|
|---|
| 53 | /// <para>The AVL tree class is not intended to be used directly. It supports the ILNumerics infrastructure (ILMemoryPool)
|
|---|
| 54 | /// internally.</para></remarks>
|
|---|
| 55 | internal class ILAVLTree {
|
|---|
| 56 |
|
|---|
| 57 | internal ILAVLTreeNode m_root = getNode();
|
|---|
| 58 | private int m_nodeCount = 0;
|
|---|
| 59 | #if DEBUG
|
|---|
| 60 | internal int m_itemCount = 0;
|
|---|
| 61 | #endif
|
|---|
| 62 |
|
|---|
| 63 | #region caching
|
|---|
| 64 | private static readonly int MAX_STACKSIZE = 50;
|
|---|
| 65 | private static readonly ILAVLTreeNode[] s_stack = new ILAVLTreeNode[MAX_STACKSIZE];
|
|---|
| 66 | private static readonly int[] s_dirs = new int[MAX_STACKSIZE];
|
|---|
| 67 | #endregion
|
|---|
| 68 |
|
|---|
| 69 | #region public interface
|
|---|
| 70 | /// <summary>
|
|---|
| 71 | /// Return number of keys currently existing in the tree
|
|---|
| 72 | /// </summary>
|
|---|
| 73 | public int Count {
|
|---|
| 74 | get { return m_nodeCount; }
|
|---|
| 75 | }
|
|---|
| 76 | /// <summary>
|
|---|
| 77 | /// Check and add a key to the collection
|
|---|
| 78 | /// </summary>
|
|---|
| 79 | /// <param name="key">Key</param>
|
|---|
| 80 | /// <remarks>The function makes sure, the key is stored in the tree.</remarks>
|
|---|
| 81 | public void Add(keytype key) {
|
|---|
| 82 | int depth, added2Side = 0;
|
|---|
| 83 | if (FindNode(key, m_root, s_stack, s_dirs, out depth)) {
|
|---|
| 84 | // nothing to do - key is already there
|
|---|
| 85 | return;
|
|---|
| 86 | } else {
|
|---|
| 87 | // parent is the node where the key should be inserted below
|
|---|
| 88 | ILAVLTreeNode newNode = getNode();
|
|---|
| 89 | newNode.key = key;
|
|---|
| 90 | m_nodeCount++;
|
|---|
| 91 | added2Side = s_dirs[depth--];
|
|---|
| 92 | if (added2Side == -1) { // insert as left child
|
|---|
| 93 | System.Diagnostics.Debug.Assert(s_stack[depth+1] == null);
|
|---|
| 94 | s_stack[depth].left = newNode;
|
|---|
| 95 | s_stack[depth].balance--;
|
|---|
| 96 | } else { // insert as right child
|
|---|
| 97 | System.Diagnostics.Debug.Assert(s_stack[depth+1] == null);
|
|---|
| 98 | s_stack[depth].right = newNode;
|
|---|
| 99 | s_stack[depth].balance++;
|
|---|
| 100 | }
|
|---|
| 101 | }
|
|---|
| 102 | // check balances along 's_stack' path -> up to root
|
|---|
| 103 | // depth is at parent level now
|
|---|
| 104 | ILAVLTreeNode node = s_stack[depth];
|
|---|
| 105 | while (depth > 0) {
|
|---|
| 106 | if (node.balance == 0) {
|
|---|
| 107 | return;
|
|---|
| 108 | }
|
|---|
| 109 | if (node.balance * node.balance == 1) {
|
|---|
| 110 | node = s_stack[--depth];
|
|---|
| 111 | node.balance += s_dirs[depth+1];
|
|---|
| 112 | continue;
|
|---|
| 113 | }
|
|---|
| 114 | if (node.balance == 2) {
|
|---|
| 115 | if (node.right.balance >= 0) {
|
|---|
| 116 | // rebalance RR -> simple left rotation
|
|---|
| 117 | ILAVLTreeNode node2 = node.right;
|
|---|
| 118 | if (s_dirs[depth] == 1) {
|
|---|
| 119 | s_stack[depth-1].right = node2;
|
|---|
| 120 | } else {
|
|---|
| 121 | s_stack[depth-1].left = node2;
|
|---|
| 122 | }
|
|---|
| 123 | if (node2.balance == 0) {
|
|---|
| 124 | node.balance = 1;
|
|---|
| 125 | node2.balance = -1;
|
|---|
| 126 | } else {
|
|---|
| 127 | System.Diagnostics.Debug.Assert (node2.balance == 1);
|
|---|
| 128 | node.balance = 0;
|
|---|
| 129 | node2.balance = 0;
|
|---|
| 130 | }
|
|---|
| 131 | node.right = node2.left;
|
|---|
| 132 | node2.left = node;
|
|---|
| 133 | } else {
|
|---|
| 134 | // rebalance RL -> double left rotation
|
|---|
| 135 | ILAVLTreeNode node2 = node.right;
|
|---|
| 136 | ILAVLTreeNode node3 = node2.left;
|
|---|
| 137 | if (s_dirs[depth] == 1) {
|
|---|
| 138 | s_stack[depth-1].right = node3;
|
|---|
| 139 | } else {
|
|---|
| 140 | s_stack[depth-1].left = node3;
|
|---|
| 141 | }
|
|---|
| 142 | if (node3.balance == -1) {
|
|---|
| 143 | node2.balance = 1;
|
|---|
| 144 | node.balance = 0;
|
|---|
| 145 | } else if (node3.balance == 1) {
|
|---|
| 146 | node2.balance = 0;
|
|---|
| 147 | node.balance = -1;
|
|---|
| 148 | } else {
|
|---|
| 149 | node2.balance = 0;
|
|---|
| 150 | node.balance = 0;
|
|---|
| 151 | }
|
|---|
| 152 | node3.balance = 0;
|
|---|
| 153 |
|
|---|
| 154 | node.right = node3.left;
|
|---|
| 155 | node2.left = node3.right;
|
|---|
| 156 | node3.left = node;
|
|---|
| 157 | node3.right = node2;
|
|---|
| 158 | }
|
|---|
| 159 | } else {
|
|---|
| 160 | System.Diagnostics.Debug.Assert(node.balance == -2);
|
|---|
| 161 | if (node.left.balance <= 0) {
|
|---|
| 162 | ILAVLTreeNode node2 = node.left;
|
|---|
| 163 | // rebalance LL -> simple rotate right
|
|---|
| 164 | if (s_dirs[depth] == 1) {
|
|---|
| 165 | s_stack[depth-1].right = node2;
|
|---|
| 166 | } else {
|
|---|
| 167 | s_stack[depth-1].left = node2;
|
|---|
| 168 | }
|
|---|
| 169 | if (node2.balance == 0) {
|
|---|
| 170 | node.balance = -1;
|
|---|
| 171 | node2.balance = 1;
|
|---|
| 172 | } else {
|
|---|
| 173 | System.Diagnostics.Debug.Assert (node2.balance == -1);
|
|---|
| 174 | node.balance = 0;
|
|---|
| 175 | node2.balance = 0;
|
|---|
| 176 | }
|
|---|
| 177 | node.left = node2.right;
|
|---|
| 178 | node2.right = node;
|
|---|
| 179 | } else {
|
|---|
| 180 | // rebalance LR - double right rotation
|
|---|
| 181 | ILAVLTreeNode node2 = node.left;
|
|---|
| 182 | ILAVLTreeNode node3 = node2.right;
|
|---|
| 183 | if (s_dirs[depth] == 1) {
|
|---|
| 184 | s_stack[depth-1].right = node3;
|
|---|
| 185 | } else {
|
|---|
| 186 | s_stack[depth-1].left = node3;
|
|---|
| 187 | }
|
|---|
| 188 | if (node3.balance == 1) {
|
|---|
| 189 | node2.balance = -1;
|
|---|
| 190 | node.balance = 0;
|
|---|
| 191 | } else if (node3.balance == -1) {
|
|---|
| 192 | node2.balance = 0;
|
|---|
| 193 | node.balance = 1;
|
|---|
| 194 | } else {
|
|---|
| 195 | node2.balance = 0;
|
|---|
| 196 | node.balance = 0;
|
|---|
| 197 | }
|
|---|
| 198 | node3.balance = 0;
|
|---|
| 199 |
|
|---|
| 200 | node.left = node3.right;
|
|---|
| 201 | node2.right = node3.left;
|
|---|
| 202 | node3.right = node;
|
|---|
| 203 | node3.left = node2;
|
|---|
| 204 | }
|
|---|
| 205 | }
|
|---|
| 206 | #if DEBUG
|
|---|
| 207 | //if (!CheckTree()) {
|
|---|
| 208 | // return;
|
|---|
| 209 | //}
|
|---|
| 210 | #endif
|
|---|
| 211 | return;
|
|---|
| 212 | }
|
|---|
| 213 | }
|
|---|
| 214 | /// <summary>
|
|---|
| 215 | /// Remove key from tree
|
|---|
| 216 | /// </summary>
|
|---|
| 217 | /// <param name="key">Key to be removed</param>
|
|---|
| 218 | /// <remarks>The function makes sure, the tree does not contain a node with the given key.</remarks>
|
|---|
| 219 | public void Remove(keytype key) {
|
|---|
| 220 | int depth;
|
|---|
| 221 | if (!FindNode(key, m_root, s_stack, s_dirs, out depth)) {
|
|---|
| 222 | return;
|
|---|
| 223 | }
|
|---|
| 224 | #if DEBUG
|
|---|
| 225 | int remDepth = depth;
|
|---|
| 226 | #endif
|
|---|
| 227 | // last entry in stack is the matching node
|
|---|
| 228 | ILAVLTreeNode cur = s_stack[depth];
|
|---|
| 229 | if (cur.left != null) {
|
|---|
| 230 | if (cur.right != null) {
|
|---|
| 231 | // find replacement node
|
|---|
| 232 | ILAVLTreeNode orig = cur;
|
|---|
| 233 | cur = cur.left;
|
|---|
| 234 | s_stack[++depth] = cur;
|
|---|
| 235 | s_dirs[depth] = -1;
|
|---|
| 236 | while (cur.right != null) {
|
|---|
| 237 | cur = cur.right;
|
|---|
| 238 | s_stack[++depth] = cur;
|
|---|
| 239 | s_dirs[depth] = 1;
|
|---|
| 240 | }
|
|---|
| 241 | // exchange keys with current node
|
|---|
| 242 | orig.key = cur.key;
|
|---|
| 243 | cur = cur.left;
|
|---|
| 244 | } else {
|
|---|
| 245 | cur = cur.left;
|
|---|
| 246 | }
|
|---|
| 247 | } else {
|
|---|
| 248 | if (cur.right != null) {
|
|---|
| 249 | // replace with right child
|
|---|
| 250 | cur = cur.right;
|
|---|
| 251 | } else {
|
|---|
| 252 | // no childs simply delete cur
|
|---|
| 253 | cur = null;
|
|---|
| 254 | }
|
|---|
| 255 | }
|
|---|
| 256 | depth--;
|
|---|
| 257 | ILAVLTreeNode par = s_stack[depth];
|
|---|
| 258 | if (s_dirs[depth+1] == 1) {
|
|---|
| 259 | par.right = cur;
|
|---|
| 260 | par.balance--;
|
|---|
| 261 | } else {
|
|---|
| 262 | par.left = cur;
|
|---|
| 263 | par.balance++;
|
|---|
| 264 | }
|
|---|
| 265 | m_nodeCount--;
|
|---|
| 266 | #if DEBUG
|
|---|
| 267 | if (par.left != null)
|
|---|
| 268 | System.Diagnostics.Debug.Assert(par.left != par);
|
|---|
| 269 | if (par.right != null)
|
|---|
| 270 | System.Diagnostics.Debug.Assert(par.right != par);
|
|---|
| 271 |
|
|---|
| 272 | #endif
|
|---|
| 273 | #region rebalance
|
|---|
| 274 | cur = par;
|
|---|
| 275 | while (depth > 0) {
|
|---|
| 276 | if (cur.balance == 0) {
|
|---|
| 277 | cur = s_stack[--depth];
|
|---|
| 278 | cur.balance -= s_dirs[depth + 1];
|
|---|
| 279 | continue;
|
|---|
| 280 | }
|
|---|
| 281 | if (cur.balance * cur.balance == 1) {
|
|---|
| 282 | break;
|
|---|
| 283 | } else if (cur.balance == 2) {
|
|---|
| 284 | #region needs left rotations
|
|---|
| 285 | if (cur.right.balance >= 0) {
|
|---|
| 286 | // rebalance RR -> simple left rotation
|
|---|
| 287 | ILAVLTreeNode node2 = cur.right;
|
|---|
| 288 | if (s_dirs[depth] == 1) {
|
|---|
| 289 | s_stack[depth - 1].right = node2;
|
|---|
| 290 | } else {
|
|---|
| 291 | s_stack[depth - 1].left = node2;
|
|---|
| 292 | }
|
|---|
| 293 | cur.right = node2.left;
|
|---|
| 294 | node2.left = cur;
|
|---|
| 295 | if (node2.balance == 0) {
|
|---|
| 296 | cur.balance = 1;
|
|---|
| 297 | node2.balance = -1;
|
|---|
| 298 | break;
|
|---|
| 299 | } else {
|
|---|
| 300 | System.Diagnostics.Debug.Assert(node2.balance == 1);
|
|---|
| 301 | cur.balance = 0;
|
|---|
| 302 | node2.balance = 0;
|
|---|
| 303 | }
|
|---|
| 304 | } else {
|
|---|
| 305 | // rebalance RL -> double left rotation
|
|---|
| 306 | ILAVLTreeNode node2 = cur.right;
|
|---|
| 307 | ILAVLTreeNode node3 = node2.left;
|
|---|
| 308 | if (s_dirs[depth] == 1) {
|
|---|
| 309 | s_stack[depth - 1].right = node3;
|
|---|
| 310 | } else {
|
|---|
| 311 | s_stack[depth - 1].left = node3;
|
|---|
| 312 | }
|
|---|
| 313 | if (node3.balance == -1) {
|
|---|
| 314 | node2.balance = 1;
|
|---|
| 315 | cur.balance = 0;
|
|---|
| 316 | } else if (node3.balance == 1) {
|
|---|
| 317 | node2.balance = 0;
|
|---|
| 318 | cur.balance = -1;
|
|---|
| 319 | } else {
|
|---|
| 320 | node2.balance = 0;
|
|---|
| 321 | cur.balance = 0;
|
|---|
| 322 | }
|
|---|
| 323 | node3.balance = 0;
|
|---|
| 324 |
|
|---|
| 325 | cur.right = node3.left;
|
|---|
| 326 | node2.left = node3.right;
|
|---|
| 327 | node3.left = cur;
|
|---|
| 328 | node3.right = node2;
|
|---|
| 329 | }
|
|---|
| 330 | #endregion
|
|---|
| 331 | } else {
|
|---|
| 332 | #region needs right rotation
|
|---|
| 333 | System.Diagnostics.Debug.Assert(cur.balance == -2);
|
|---|
| 334 | if (cur.left.balance <= 0) {
|
|---|
| 335 | ILAVLTreeNode node2 = cur.left;
|
|---|
| 336 | // rebalance LL -> simple rotate right
|
|---|
| 337 | if (s_dirs[depth] == 1) {
|
|---|
| 338 | s_stack[depth - 1].right = node2;
|
|---|
| 339 | } else {
|
|---|
| 340 | s_stack[depth - 1].left = node2;
|
|---|
| 341 | }
|
|---|
| 342 | cur.left = node2.right;
|
|---|
| 343 | node2.right = cur;
|
|---|
| 344 | if (node2.balance == 0) {
|
|---|
| 345 | cur.balance = -1;
|
|---|
| 346 | node2.balance = 1;
|
|---|
| 347 | break;
|
|---|
| 348 | } else {
|
|---|
| 349 | System.Diagnostics.Debug.Assert(node2.balance == -1);
|
|---|
| 350 | cur.balance = 0;
|
|---|
| 351 | node2.balance = 0;
|
|---|
| 352 | }
|
|---|
| 353 | } else {
|
|---|
| 354 | // rebalance LR - double right rotation
|
|---|
| 355 | ILAVLTreeNode node2 = cur.left;
|
|---|
| 356 | ILAVLTreeNode node3 = node2.right;
|
|---|
| 357 | if (s_dirs[depth] == 1) {
|
|---|
| 358 | s_stack[depth - 1].right = node3;
|
|---|
| 359 | } else {
|
|---|
| 360 | s_stack[depth - 1].left = node3;
|
|---|
| 361 | }
|
|---|
| 362 | if (node3.balance == 1) {
|
|---|
| 363 | node2.balance = -1;
|
|---|
| 364 | cur.balance = 0;
|
|---|
| 365 | } else if (node3.balance == -1) {
|
|---|
| 366 | node2.balance = 0;
|
|---|
| 367 | cur.balance = 1;
|
|---|
| 368 | } else {
|
|---|
| 369 | node2.balance = 0;
|
|---|
| 370 | cur.balance = 0;
|
|---|
| 371 | }
|
|---|
| 372 | node3.balance = 0;
|
|---|
| 373 |
|
|---|
| 374 | cur.left = node3.right;
|
|---|
| 375 | node2.right = node3.left;
|
|---|
| 376 | node3.right = cur;
|
|---|
| 377 | node3.left = node2;
|
|---|
| 378 | }
|
|---|
| 379 | #endregion
|
|---|
| 380 | }
|
|---|
| 381 | // populate to parent
|
|---|
| 382 | if (--depth <= 0)
|
|---|
| 383 | break;
|
|---|
| 384 | cur = s_stack[depth];
|
|---|
| 385 | cur.balance -= s_dirs[depth + 1];
|
|---|
| 386 | }
|
|---|
| 387 | #endregion
|
|---|
| 388 | #if DEBUG
|
|---|
| 389 | //if (!CheckTree()) {
|
|---|
| 390 | // return;
|
|---|
| 391 | //}
|
|---|
| 392 | #endif
|
|---|
| 393 | }
|
|---|
| 394 | /// <summary>
|
|---|
| 395 | /// Find next higher key
|
|---|
| 396 | /// </summary>
|
|---|
| 397 | /// <param name="key">Key to find</param>
|
|---|
| 398 | /// <returns>The key with the next higher value compared with <paramref name="key"/>, or -1 if no such key exists</returns>
|
|---|
| 399 | public keytype Next(keytype key) {
|
|---|
| 400 | if (m_root.right == null) {
|
|---|
| 401 | return -1;
|
|---|
| 402 | }
|
|---|
| 403 | int level = 0;
|
|---|
| 404 | if (!FindNode(key, m_root, s_stack, s_dirs, out level) && level > 0)
|
|---|
| 405 | level--;
|
|---|
| 406 | ILAVLTreeNode node = s_stack[level];
|
|---|
| 407 | if (node.key >= key) return node.key;
|
|---|
| 408 | node = NextAsc(s_stack[level], s_stack, s_dirs, level);
|
|---|
| 409 | if (node != null && node.key > key)
|
|---|
| 410 | return node.key;
|
|---|
| 411 | return -1;
|
|---|
| 412 | }
|
|---|
| 413 | /// <summary>
|
|---|
| 414 | /// Clear the tree from all keys
|
|---|
| 415 | /// </summary>
|
|---|
| 416 | internal void Clear() {
|
|---|
| 417 | m_root.right = null;
|
|---|
| 418 | #if DEBUG
|
|---|
| 419 | m_nodeCount = 0;
|
|---|
| 420 | m_itemCount = 0;
|
|---|
| 421 | #endif
|
|---|
| 422 | }
|
|---|
| 423 | #endregion
|
|---|
| 424 |
|
|---|
| 425 | #region private helper
|
|---|
| 426 | private static bool FindNode(keytype key, ILAVLTreeNode cur, ILAVLTreeNode[] path, int[] dirs, out int level) {
|
|---|
| 427 | int depth = 0;
|
|---|
| 428 | while (true) {
|
|---|
| 429 | path[depth] = cur;
|
|---|
| 430 | //if (cur.isNil) {
|
|---|
| 431 | // //Console.Out.WriteLine("Key:{0} depth: {1} {2}",cur.key, depth, s_dirs[depth] );
|
|---|
| 432 | // level = depth;
|
|---|
| 433 | // return false;
|
|---|
| 434 | //}
|
|---|
| 435 | if (cur.key == key) {
|
|---|
| 436 | level = depth;
|
|---|
| 437 | return true;
|
|---|
| 438 | } else {
|
|---|
| 439 | if (key < cur.key) {
|
|---|
| 440 | dirs[++depth] = -1;
|
|---|
| 441 | path[depth] = cur.left;
|
|---|
| 442 | if (cur.left == null) {
|
|---|
| 443 | level = depth;
|
|---|
| 444 | return false;
|
|---|
| 445 | }
|
|---|
| 446 | cur = cur.left;
|
|---|
| 447 | } else { // key > cur.key
|
|---|
| 448 | dirs[++depth] = 1;
|
|---|
| 449 | path[depth] = cur.right;
|
|---|
| 450 | if (cur.right == null) {
|
|---|
| 451 | level = depth;
|
|---|
| 452 | return false;
|
|---|
| 453 | }
|
|---|
| 454 | cur = cur.right;
|
|---|
| 455 | }
|
|---|
| 456 | }
|
|---|
| 457 | }
|
|---|
| 458 | }
|
|---|
| 459 | private static ILAVLTreeNode NextAsc(ILAVLTreeNode node, ILAVLTreeNode[] path, int[] dirs, int level) {
|
|---|
| 460 | ILAVLTreeNode ret = node;
|
|---|
| 461 | if (node.right != null) {
|
|---|
| 462 | node = node.right;
|
|---|
| 463 | while (node.left != null) {
|
|---|
| 464 | node = node.left;
|
|---|
| 465 | }
|
|---|
| 466 | ret = node;
|
|---|
| 467 | } else {
|
|---|
| 468 | while (level > 0) {
|
|---|
| 469 | // dirs[0] is always 0 (dummy root node)
|
|---|
| 470 | if (dirs[level] == -1) {
|
|---|
| 471 | ret = path[--level];
|
|---|
| 472 | break;
|
|---|
| 473 | }
|
|---|
| 474 | level--;
|
|---|
| 475 | }
|
|---|
| 476 | }
|
|---|
| 477 | return ret;
|
|---|
| 478 | }
|
|---|
| 479 | /// <summary>
|
|---|
| 480 | /// check the consistency of the tree
|
|---|
| 481 | /// </summary>
|
|---|
| 482 | /// <returns></returns>
|
|---|
| 483 | internal bool CheckTree() {
|
|---|
| 484 | if (m_root.right == null)
|
|---|
| 485 | return true;
|
|---|
| 486 | ILAVLTreeNode cur = m_root.right;
|
|---|
| 487 | while (cur.left != null)
|
|---|
| 488 | cur = cur.left;
|
|---|
| 489 | keytype key = cur.key;
|
|---|
| 490 | int depth;
|
|---|
| 491 | ILAVLTreeNode node = cur;
|
|---|
| 492 | do {
|
|---|
| 493 | Console.Out.Write("checking node: " + node.key);
|
|---|
| 494 | if (FindNode(node.key, m_root, s_stack, s_dirs, out depth)) {
|
|---|
| 495 | if (s_stack[depth] != node)
|
|---|
| 496 | return false;
|
|---|
| 497 | if (!checkTree(node)) {
|
|---|
| 498 | return false;
|
|---|
| 499 | }
|
|---|
| 500 | node = NextAsc(node, s_stack, s_dirs, depth);
|
|---|
| 501 | } else {
|
|---|
| 502 | return false;
|
|---|
| 503 | }
|
|---|
| 504 | Console.Out.WriteLine("... ok");
|
|---|
| 505 | } while (node != null);
|
|---|
| 506 | return true;
|
|---|
| 507 | }
|
|---|
| 508 | private static ILAVLTreeNode getNode() {
|
|---|
| 509 | var ret = new ILAVLTreeNode();
|
|---|
| 510 | ret.key = -1;
|
|---|
| 511 | ret.balance = 0;
|
|---|
| 512 | //ret.right = ret;
|
|---|
| 513 | return ret;
|
|---|
| 514 | }
|
|---|
| 515 | private bool checkTree(int key) {
|
|---|
| 516 | ILAVLTreeNode[] tmpNodes = new ILAVLTreeNode[50];
|
|---|
| 517 | int[] tmpKeys = new int[50];
|
|---|
| 518 | int level;
|
|---|
| 519 | if (!FindNode(key, m_root, tmpNodes, tmpKeys, out level)) {
|
|---|
| 520 | return false;
|
|---|
| 521 | }
|
|---|
| 522 | return checkTree(tmpNodes[level]);
|
|---|
| 523 | }
|
|---|
| 524 | private static bool checkTree(ILAVLTreeNode root) {
|
|---|
| 525 | // check balance condition
|
|---|
| 526 | int ltree = 0, rtree = 0;
|
|---|
| 527 | if (root.left != null) {
|
|---|
| 528 | ltree = levelTree(root.left);
|
|---|
| 529 | }
|
|---|
| 530 | if (root.right != null) {
|
|---|
| 531 | rtree = levelTree(root.right);
|
|---|
| 532 | }
|
|---|
| 533 | int bal = rtree - ltree;
|
|---|
| 534 | if (root.balance != bal)
|
|---|
| 535 | return false;
|
|---|
| 536 | if (bal * bal > 1) {
|
|---|
| 537 | return false;
|
|---|
| 538 | }
|
|---|
| 539 |
|
|---|
| 540 | return true;
|
|---|
| 541 |
|
|---|
| 542 | }
|
|---|
| 543 | private static int levelTree(ILAVLTreeNode root) {
|
|---|
| 544 | if (root.left == null && root.right == null) {
|
|---|
| 545 | return 1;
|
|---|
| 546 | } else {
|
|---|
| 547 | int ltree = 0, rtree = 0;
|
|---|
| 548 | if (root.left != null) {
|
|---|
| 549 | ltree = levelTree(root.left);
|
|---|
| 550 | }
|
|---|
| 551 | if (root.right != null) {
|
|---|
| 552 | rtree = levelTree(root.right);
|
|---|
| 553 | }
|
|---|
| 554 | return Math.Max(ltree,rtree) + 1;
|
|---|
| 555 | }
|
|---|
| 556 | }
|
|---|
| 557 | #endregion
|
|---|
| 558 | /// <summary>
|
|---|
| 559 | /// an AVL tree node
|
|---|
| 560 | /// </summary>
|
|---|
| 561 | public class ILAVLTreeNode {
|
|---|
| 562 | /// <summary>
|
|---|
| 563 | /// Key
|
|---|
| 564 | /// </summary>
|
|---|
| 565 | public keytype key;
|
|---|
| 566 | /// <summary>
|
|---|
| 567 | /// Right child
|
|---|
| 568 | /// </summary>
|
|---|
| 569 | public ILAVLTreeNode right;
|
|---|
| 570 | /// <summary>
|
|---|
| 571 | /// Left child
|
|---|
| 572 | /// </summary>
|
|---|
| 573 | public ILAVLTreeNode left;
|
|---|
| 574 | /// <summary>
|
|---|
| 575 | /// Balance factor for the node
|
|---|
| 576 | /// </summary>
|
|---|
| 577 | public int balance;
|
|---|
| 578 | /// <summary>
|
|---|
| 579 | /// Rext representation of the node
|
|---|
| 580 | /// </summary>
|
|---|
| 581 | /// <returns>String representation for the node</returns>
|
|---|
| 582 | public override string ToString() {
|
|---|
| 583 | return String.Format("{0} [{1}-{2}]",key,(left == null) ? "*" : left.key.ToString(), (right == null) ? "*" : right.key.ToString());
|
|---|
| 584 | }
|
|---|
| 585 | }
|
|---|
| 586 |
|
|---|
| 587 | }
|
|---|
| 588 | }
|
|---|
